今天又学习了一个算法,断断续续的花了两个小时给搞懂了,不得不感叹,算法真的太强了,简化超级多的步骤,太强了,太强了,太强了👍
首先说下,快速幂解决的是什么问题,核心问题是解决计算机“受不了的数”问题,试想一个场景,如果让你算下 2^{120}
的后三位的值
,你会咋办?可能你会说 so easy,你的解法是硬算、巧算、还是智算。请听我细细道来:
1、幂函数 硬算
使用 pow 函数硬算代码如下:
#include<cmath> int main(){ long long int x; x = pow(2,120); cout<<x<<endl; cout<<x%1000<<endl; return 1; } // 打印 // -9223372036854775808 // -808
咦,为什么出现这种结果呢?那就的说下int 数据类型的大小了,具体可看这篇文章介绍。64位编译器下,int 一 般是占用 4 个字节,long long int 占用 8 个字节,除去首位的符号标志位,所能容纳的最大 2^{8*8-1}-1=9223372036854775807
,而 2^{120}
远远的超过这个数,所以累死电脑也算不出来的,更不用说怎么算它的后三位了。
来来改进一下,使用一波取模定理来优化优化
2、取模定理 巧算
取模运算解决的多个大数相乘所得结果过大(计算机不支持)而取不了后几位的问题,取模定理我也是第一次听,看了之后发现是真的牛,不亏是数学定理。这里就不细说了,具体可看我的==另一篇文章==,取模定理具体内容:
(a + b) % p = (a % p + b % p) % p (1) (a - b) % p = (a % p - b % p ) % p (2) (a * b) % p = (a % p * b % p) % p (3) a ^ b % p = ((a % p)^b) % p (4)
这里仅需看这里面的(3), (a * b) % p = (a%p * b%p) % p
,这个就厉害了,乘积的取模等于各个因子取模相乘然就在取模,相当于把数都控制在 p-1 位,这计算数量就超级小了,有木有~
使用取模运算的代码:
int main(){ long long int result=1; // x = pow(2,120); clock_t start_time = clock(); for(int i=0;i<120;++i){ result = result*2%1000; } result = result % 1000; clock_t end_time = clock(); cout<<result<<endl; cout<<"计算花费时间:"<<double(end_time - start_time)/CLOCKS_PER_SEC<<endl; // start_time和end_time的差值计算的是 CPU 运行程序所花费的时钟单元数量,然后在除以CLOCK_PER_SEC(是:CPU 每秒有多少时钟单元数。) return 1; } // 打印 // 576 // 计算花费时间3e-06
这速度也太6了吧,而且还算出结果了,数学定理真的太强了,不负我一直爱着它😂,虽然人生中最重要的考试都是数学考砸了。
感受到数学定理的威力了吧,但这就满足了?取模定理仅仅是将数据都给控制在一定位数以内,让数可以计算出来,但是并没有简化计算次数(还是120次),要是有简化计算步骤的算法就更好了。俗话说没有最快只有更快😆,有请今天的主角,缩短计算次数的快速幂算法登场:
3、快速幂算法 智算
当我看到这个算法的讲解时,拍案而起,仿佛看到一个新的世界向我招手,那就是算法。算法真的太强了,能把一个复杂的问题,化简成一个个小的问题,循环解决,而且速度还很快。
好了,废话不多说,写正事。先说下,我写文章是为了锻炼自己的写作能力,并且加深对知识的理解,可能我的讲解不太清楚。如看不懂的朋友,可以直接看文章底部的参考文章,大佬写的这个快速幂算法更详细,有需要的可以去看看。
3.1、什么是快速幂算法?
快速幂算法又称为二进制取幂(Binary Exponentiation),能够大幅度的减少计算步骤,从而提升运算速度,是一个在log_n
的时间内计算 的小技巧,而暴力的计算需要 n
的时间。
3.2、算法描述
例如我们计算:a^n
,就相当于是 a^{n1}*a^{n2}……*a^{ns}
,其中n = n1 + n2 +......+ ns
。但是当 n 特别大的时候,计算量就很大,所谓的”指数爆炸“。这里我们可以简化下,a^{2b}=({a^b})^2
,瞬间计算量就小了,例如:2^{400}=4^{200}=16^{100}=……
,计算一下子少了200步,300步……,效率有木有。
知道了取平方可以缩短计算次数,所以我们可以按照 二进制 来表示幂。那我们来看看幂和二进制之间的关系,还是举个例子讲解:例如:3^{13}=3^{(1101)_2}=3^8*3^4*3^1
。
是不是发现,这里面只有二进制位是1的才乘到里面,是0的跳过。所以我们只需要用10进制转2进制的方法(不断÷2的余数,直到商为0),即可得到幂数对应的二进制数。如果某一二进制位是1,那就将对应的数乘到结果里面,并且底数也翻倍;如果是0,则底数也翻倍。可看下面的推导过程,这个地方有点绕,跟着过一遍就懂了。
# 1、指数(power)13 对一个二进制,底数(base)为3 13/2 = 6 余1 # base变成3*3=9 result=result*3,base=base*base 6/2 = 3 余0 # base变成9*9=81 base=base*base 3/2 = 1 余1 # base变成81*81=6561 result=result*3,base=base*base 1/2 = 0 余1 # base变成6561*6561 result=result*3,base=base*base # 所以对应的二进制是 1101 # 2、对应计算代码 Python def quick(base, power): result = 1 b = power while(b>0): if b&1: # 相当于是if b%2 == 1: 为奇数 result = result * base base = base * base b >>= 1 # 相当于是 b = b/2 b取一半 print(result) quick(3, 13) # 打印 # 1594323
你以为这样就结束了吗?还差一步呢,快速幂只是缩短了计算次数,但是并没有解决计算高幂次的数后三位的问题(如:2^{120}
)。可能你会想到,如果加上之前的取模运算,那岂不是把数都给缩小了,就可以计算出结果了。
没错,就是这样,快速幂算法+取模定理一个完美的cp搭配,来一波 c++ 代码:
#include<iostream> #include<ctime> using namespace std; int main(){ long long int result=1; int base = 2,power=120; clock_t start_time = clock(); while(power>0){ if(power & 1){ result = result*base%1000; } base = (base*base)%1000; power >>= 1; } result = result%1000; clock_t end_time = clock(); cout<<result<<endl; cout<<"计算花费时间:"<<double(end_time - start_time)/CLOCKS_PER_SEC<<endl; cout<<"CPU每秒时钟数:"<<CLOCKS_PER_SEC<<endl; return 1; } // 打印 // 576 // 计算花费时间:1e-06 // CPU每秒时钟数:1000000
哇,终于写完了,好头疼呀😂~
总结:
算法是真的强,效率很高,爱了,努力学习算法中~
参考文章:
可以