快速冪原理解析與其他方法回顧

目錄：一.回顧樸素法與使用庫(kù)函數(shù)，分析利弊。

二.引例：指數(shù)的分解，即快速冪的原理。

三.源代碼。

正文：

　一.回顧

　　1.1.已知的方法

　　關(guān)于求a的n次方，有幾種做法吶？對(duì)于初學(xué)者來(lái)說(shuō)有兩種。如下所示

1 void poww1(int a, int b){2     long long ans = 1;3     for(register int i = 0; i < b; i++)4         ans *= a;5     return ans;6 }
1 　#include <cmath>//poww22     ans = (long long) pow(a, b);//調(diào)用cmath庫(kù)的pow函數(shù)，但是注意返回值不是longlong/int型，是double型
　　觀察poww1，一個(gè)明顯的問(wèn)題便是它的時(shí)間復(fù)雜度比較高，是O(n)的復(fù)雜度，即n次方需要乘n次才可得到結(jié)果，較慢。
　　觀察poww2，更加明顯的問(wèn)題在于其函數(shù)的返回值是個(gè)浮點(diǎn)數(shù)，這是一個(gè)定時(shí)炸彈，有可能使用pow(10, 4)時(shí)得到9999的答案，讓你調(diào)試后欲哭無(wú)淚。
 
　　1.2. 測(cè)試對(duì)比
　　測(cè)試程序如下：
 1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 using namespace std; 5 int main(){    6      int n = 0;   7      for(int i = 0; i <= 4; i++)   8          n += (i+1)*(int)pow(10, 5-i);   9      cout << n << endl;  10      return 0;  11 }
 
　　使用Dev-C++ 5.4.0 與Smart c++ 2013分別運(yùn)行，得到測(cè)試數(shù)據(jù)：
　　由于精度問(wèn)題，結(jié)果不同。
　　有人會(huì)說(shuō)："不要強(qiáng)轉(zhuǎn)成int啊，用long long 就不會(huì)丟失精度啦。"
　　那么將循環(huán)改成——
1 for(int i = 0; i <= 4; i++)  2     n += kong[i]*(long long)pow(10, 5-i); 
　　測(cè)試結(jié)果如下：
　　根本就沒(méi)有變哎！
 
　　1.3.對(duì)比兩種方法運(yùn)行的時(shí)間與準(zhǔn)確性
　　利用循環(huán)次數(shù)更大的測(cè)試程序如下：
1     int i;  2     long long n = 0;  3     for(i = 0; i <= 10; i++){4         n += (i+3)*(long long)pow(5, 11-i);  5     }6     cout << n << endl;  
 1 long long poww(int a, int b){ 2     long long ans = 1; 3     for(int i = 0; i < b; i++) 4         ans *= a; 5     return ans; 6 } 7 int main(){   8     int i;   9     long long n = 0;  10     for(i = 0; i <= 10; i++){11         n += (i+3)*(long long)pow(5, 11-i);  12     }13     cout << n << endl;  14     return 0;  15 }
　　運(yùn)行結(jié)果如下：
　　（上下分別是方法二與方法一）
 
　　1.4. 結(jié)論
　　兩者優(yōu)劣一目了然：方法一相對(duì)較快且保證在不超范圍內(nèi)一定正確，不過(guò)要多打幾行代碼；方法二短，但是坑。
　　若選擇以上兩種方法，自己選吧。。。
　　那么我們的目標(biāo)便是繼承方法一的優(yōu)點(diǎn)，改良其缺點(diǎn)：即保持準(zhǔn)確性的情況下降低時(shí)間復(fù)雜度。
 
　二.快速冪引理
　　2.1.先看效果：
　　答案一致，時(shí)間不到方法一的1/2，并且在當(dāng)次方數(shù)極大的時(shí)候，時(shí)間會(huì)遠(yuǎn)小于方法一,原因便是因?yàn)槠鋾r(shí)間復(fù)雜度為O(logn)（logn通常指log2n）。
 
　　2.2引理的數(shù)學(xué)形式
　　引理：? 取X∈N*皆可被分解為形如X = 2^a+2^b+...+2^k(a != b !=  ……  != k);
　　設(shè)2^0+2^1+2^2+…+2^n = m;……(1)式
　　2^1+2^2+2^3+…+2^(n+1) = 2*m;……(2)式
　　(2)式-(1) 式= (1)式 = 2^(n+1)-2^0 = 2^(n+1)-1……(*)
　　當(dāng)X != 2^m時(shí)
　　∵int X > 0;
　　∴ X = 2^m - 1 - k(int k >= 0);
　　if(x%2 == 1)　　k %2 == 0;
　　else k%2 == 1;
　　∵2^m - 1 = 2^0 + 2^1 + … +2^(m-1);
　　∴若原式成立，則k可分解為2某些次方的和。
　　當(dāng)k%2 == 1時(shí)，必有2^0,減掉，k為偶數(shù);
　　那么現(xiàn)在X 就縮小為了正偶數(shù)。
　　觀察2 4 8 16 ……我們會(huì)發(fā)現(xiàn)一點(diǎn)，即第i個(gè)數(shù)后面的數(shù)都2^i有作為因數(shù)，而它前面的數(shù)因數(shù)中則沒(méi)有2^i，通過(guò)這個(gè)便可以確定k的分解。
　　利用遞歸的思想……X縮小為4的倍數(shù)，8的倍數(shù)……
 
　　2.3例子：
　　舉個(gè)例子 : k = 17的分解，按照以下步驟。
　　int cnt = 1;
　　while (k){
　　　if(k%(2^cnt) != 0) {
　　　　k得到新的分解 : 2^(cnt-1);
　　　　k -= 2^(cnt-1);
　　　　//此時(shí)k%2(cnt) == 0
　　　　cnt ++;
　　}
　}
　　17%2 == 1; =>　17 = 2^0 + m;　17-1 = 16;
　　16%2 == 0; =>　16/2 = 8　
　　……
　　1%2 == 1; =>17 = 2^0 +2^4;
 　　1/2 == 0 終止循環(huán)； 
　　那么這種東東對(duì)做冪運(yùn)算有什么用呢？
　　答案便是 —— 將指數(shù)按照此方法分解。
　　例如：求6^11
　　我們已知 6^0 == 1 ,a ==  6^1 == 6;
　　11 == 2^0 + 2^1 + 2^3;
　　所以 6^11 == 6^1 * 6^2 * 6^8;
　　我們還知道 a^2 == 36;
　　那么我們將上述分解指數(shù)的步驟加入乘法以獲得最終解：
　　curr = 6;ans = 1;
　　11 % 2 == 1 => ans *= 6^0;curr = 6^2
　　5 %2 == 1 => ans *= 6^2;curr = 6^4;
　　2%2 == 0 =>curr = 6^8;
　　1%2 == 0 ans *=curr; ans = 6^11;
　　一共用了ceil(log(2)11) = 4 步
　　每次curr自我平方一次，以準(zhǔn)備下一次的使用。而當(dāng)k%2 == 1 時(shí)，就意味著需要使用curr將指數(shù)進(jìn)行分解。
 
　　2.4.源代碼 
　　那么給出源代碼:
 1 void poww(int a, int b){ 2     int cnt = 0; 3     long long curr = a,ans = 1, last; 4     while (b){ 5         if(b%2)    ans *= curr; 6         curr *= curr; 7         b /= 2; 8         cnt ++; 9     }10     return ;11 }
　　步驟與上面一模一樣。
　　由此，快速冪便完成了。　
　　箜瑟_qi 2016.02.08