小女孩把快速冪奧秘探索出來了！
本文轉載自微信公眾號「bigsai」，作者大賽。轉載本文請聯系bigsai公眾號。
前言
大家好，我是bigsai，之前有個小老弟問到一個劍指offer一道相關快速冪的題，這里梳理一下講一下快速冪!
快速冪是什么?
顧名思義，快速冪就是快速算底數的n次冪。你可能疑問，求n次冪算n次疊乘不就行了?當n巨大無比時候，如果需要末尾有效尾數值等信息這個可能超出計算機運算范圍。
有多快?
快速冪時間復雜度為 O(log?n)， 與樸素的O(n)相比效率有了極大的提高(int 范圍10位長度數字32次之內就能搞定，long 范圍20位長度數字64次之內也能搞定，你看有多快)。
用的多么?
快速冪屬于數論的范疇，本是ACM經典算法，但現在各廠對算法的要求越來越高，并且快速冪適用場景也比較低多并且相比樸素方法有了非常大的提高，所以掌握快速冪算法已經是一名更合格的工程師必備要求!
下面來詳細看看快速冪算法吧!
快速冪介紹
先看個問題再說：
初探
首先問你一個問題，如果讓你求 (2^10)%1000你可能會這樣寫：
- int va=1;
- for(int i=0;i<10;i++)
- {
- va*=2;
- }
- System.out.println(va%10000);
熟悉的1024沒問題，總共計算了10次。但是如果讓你算 (2^50)%10000呢?
你可能會竊喜，小樣，這就想難住我?我知道int只有32位，50位超出范圍會帶來數值越界的異常，我這次可以用long，long有64位呢!
- long va=1;
- for(int i=0;i<50;i++)
- {
- va*=2;
- }
- System.out.println(va);
- System.out.println(va%10000);
計算50次出了結果正當你暗暗私喜的時候又來了一個要命的問題：讓你算 (2^1e10)%10000 且不許你用Java大數類，你為此苦惱不知所措。這時bigsai小哥哥讓你百度下取模運算，然后你恍然大悟，在紙上寫了幾個公式：
- (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）
你還算聰明一眼發現其中的規律：
- (a * b) % p = (a % p * b % p) % p (3)
- (2*2*2···*2) %1e10=[2*(2*2···*2)]%1e5=(2%1e5)*(2*2···*2%le5)%1e5
憑借這個遞推你明白：每次相乘都取模。機智的你pia pia寫下以下代碼，卻發現另一個問題：怎么跑不出來?
咱們打工人需要對計算機運行速度和數值有一個大致的概念。循環體中不同操作占用時間不同，所以當你的程序循環次數到達1e6或1e7的時候就需要非常非常小心了。如果循環體邏輯或者運算較多可能非常非常慢。
快速冪探索
機智的小女孩不甘失敗，開始研究其數的規律，將這個公式寫在手上、膀子上、小紙條上。吃飯睡覺都在看：
然后小女孩突然發現其中的奧秘，n次冪可以拆分成一個平方計算后就剩余n/2的次冪了：
現在你已經明白了快速冪是怎么回事，但小女孩可能有點上頭，還是給我講了很多內容：
快速冪實現
至于快速冪已經懂了，我們該怎么實現這個算法呢?
說的不錯，確實有遞歸和非遞歸的實現方式，但是遞歸使用的更多一些。在實現的時候，注意一下奇偶性、停止條件就可以了，奇數問題可以轉換為偶數問題：
- 2*2*2*2*2=2 * (2*2*2*2) 奇數問題可以轉化為偶數問題。
這里，遞歸的解法如下：
- long c=10000007;
- public long divide(long a, long b) {
- if (b == 0)
- return 1;
- else if (b % 2 == 0) //偶數情況
- return divide((a % c) * (a % c), b / 2) % c;
- else//奇數情況
- return a % c * divide((a % c) * (a % c), (b - 1) / 2) % c;
- }
非遞歸實現也不難，控制好循環條件即可：
- //求 a^b%1000000007
- long c = 1000000007;
- public long divide(long a, long b) {
- a %= c;
- long res = 1;
- for (; b != 0; b /= 2) {
- if (b % 2 == 1)
- res = (res * a) % c;
- a = (a * a) % c;
- }
- return res;
- }
對于非遞歸你可能有點模糊為啥偶數情況不給res賦值。這里有兩點：
- 為奇數的情況res僅僅是收集相乘那個時候落單的a
- 最終b均會降到1，a最終都會和res相乘，不用擔心會漏掉
- 理想狀態一直是偶數情況，那最后直接獲得a取模的值即可。
如果還是不懂，可以用這個圖來解釋一下：
矩陣快速冪
你以為這就結束了?雖然快速冪主要內容就是以上內容，但是總有很多牛人能夠發現很有趣的規律—矩陣快速冪。如果你沒聽過的話建議仔細看看了解一下。
大家都知道斐波那契數列：的規則：
前幾個斐波那契的數列為：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
斐波那契從遞推式就可以看出是指數級別的增長，所以稍微多幾個數字就是爆炸式增長，所以很多時候也會要求最后幾位的結果。有了前面模運算公式溢出就不成問題，但n如果非常非常大怎么快速計算就成了一個新的問題。
我們看下面一組公式：
- f(n+1) = f(n) + f(n-1)
- f(n) = f(n)
如果拿f(n)和f(n-1)放到一個矩陣中(一行兩列)：[f(n+1),f(n)] 能否找到和[f(n),f(n-1)]之間的什么規律呢?
答案是存在規律的，看上面的公式知道：
- [f(n+1),f(n)]
- =[f(n)+f(n-1),f(n)]
- [1 1]
- =[f(n),f(n-1)] *
- [1 0]
- [1 1] [1 1]
- =[f(n-1),f(n-2)]* *
- [1 0] [1 1]
- =·······
所以現在你可以知道它的規律了吧，這樣一直迭代到f(2),f(1)剛好都為1，所以這個斐波那契的計算為：
而這個矩陣有很多次冪，就可以使用快速冪啦，原理一致，你只需要寫一個矩陣乘法就可以啦,下面提供一個矩陣快速冪求斐波那契第n項的后三位數的模板，可以拿這個去試一試poj3070的題目啦。
- public int Fibonacci(int n)
- {
- n--;//矩陣為兩項
- int a[][]= {{1,1},{1,0}};//進行快速冪的矩陣
- int b[][]={{1,0},{0,1}};//存儲漏單奇數、結果的矩陣，初始為單位矩陣
- int time=0;
- while(n>0)
- {
- if(n%2==1)
- {
- b=matrixMultiplication(a, b);
- }
- a=matrixMultiplication(a, a);
- n/=2;
- }
- return b[0][0];
- }
- public int [][]matrixMultiplication(int a[][],int b[][]){//
- int x=a.length;//a[0].length=b.length 為滿足條件
- int y=b[0].length;//確定每一排有幾個
- int c[][]=new int [x][y];
- for(int i=0;i<x;i++)
- for(int j=0;j<y;j++)
- {
- //需要確定每一個元素
- //c[i][j];
- for(int t=0;t<b.length;t++)
- {
- c[i][j]+=(a[i][t]%10000)*(b[t][j]%10000);
- c[i][j]%=10000;
- }
- }
- return c;
- }
小試牛刀
在力扣(劍指offer16數值的整數次方)上就有一道快速冪的問題，我們用學的東西鞏固一下：
實現 pow(x n) ，即計算 x 的 n 次冪函數(即，x^n)。不得使用庫函數，同時不需要考慮大數問題。
這個簡單題需要考慮一些特殊情況：
- n正負性
- 邊界(int最大和最小)
在實現上首先判斷n正負，將負次冪轉成正次冪。如果中轉一層long處理就不會出現這些問題。
- class Solution {
- public double myPow(double x, int n) {
- if(n==0)
- return 1;
- if(n==1)
- return x;
- if(n<0){
- return (1/x)*myPow((1/x),-(n+1));//不要-n-1會溢出
- }
- if(n%2==0)
- return myPow(x*x,n/2);
- else
- return x*myPow(x*x,(n-1)/2);
- }
- }
結語
這篇到這里就肝完啦，其實快速冪的內容還不止這么多，尤其是矩陣快速冪，會有著各種巧妙的變形，不過跟數學有一些關系，在力扣上比較少，但是在其他OJ上快速冪題目還是很多的可以自行找一下刷一刷。
是不是看完又get一個小知識!
