[[416359]]

本文轉(zhuǎn)載自微信公眾號「bigsai」，作者大賽。轉(zhuǎn)載本文請聯(lián)系bigsai公眾號。

前言

大家好，我是bigsai，之前有個小老弟問到一個劍指offer一道相關(guān)快速冪的題，這里梳理一下講一下快速冪!

快速冪是什么?

顧名思義，快速冪就是快速算底數(shù)的n次冪。你可能疑問，求n次冪算n次疊乘不就行了?當n巨大無比時候，如果需要末尾有效尾數(shù)值等信息這個可能超出計算機運算范圍。

有多快?

快速冪時間復雜度為 O(log?n)， 與樸素的O(n)相比效率有了極大的提高(int 范圍10位長度數(shù)字32次之內(nèi)就能搞定，long 范圍20位長度數(shù)字64次之內(nèi)也能搞定，你看有多快)。

用的多么?

快速冪屬于數(shù)論的范疇，本是ACM經(jīng)典算法，但現(xiàn)在各廠對算法的要求越來越高，并且快速冪適用場景也比較低多并且相比樸素方法有了非常大的提高，所以掌握快速冪算法已經(jīng)是一名更合格的工程師必備要求!

下面來詳細看看快速冪算法吧!

快速冪介紹

先看個問題再說：

初探

首先問你一個問題，如果讓你求 (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位超出范圍會帶來數(shù)值越界的異常，我這次可以用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次出了結(jié)果正當你暗暗私喜的時候又來了一個要命的問題：讓你算 (2^1e10)%10000 且不許你用Java大數(shù)類，你為此苦惱不知所措。這時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） 

你還算聰明一眼發(fā)現(xiàn)其中的規(guī)律：

(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寫下以下代碼，卻發(fā)現(xiàn)另一個問題：怎么跑不出來?

咱們打工人需要對計算機運行速度和數(shù)值有一個大致的概念。循環(huán)體中不同操作占用時間不同，所以當你的程序循環(huán)次數(shù)到達1e6或1e7的時候就需要非常非常小心了。如果循環(huán)體邏輯或者運算較多可能非常非常慢。

快速冪探索

機智的小女孩不甘失敗，開始研究其數(shù)的規(guī)律，將這個公式寫在手上、膀子上、小紙條上。吃飯睡覺都在看：

然后小女孩突然發(fā)現(xiàn)其中的奧秘，n次冪可以拆分成一個平方計算后就剩余n/2的次冪了：

現(xiàn)在你已經(jīng)明白了快速冪是怎么回事，但小女孩可能有點上頭，還是給我講了很多內(nèi)容：

快速冪實現(xiàn)

至于快速冪已經(jīng)懂了，我們該怎么實現(xiàn)這個算法呢?

說的不錯，確實有遞歸和非遞歸的實現(xiàn)方式，但是遞歸使用的更多一些。在實現(xiàn)的時候，注意一下奇偶性、停止條件就可以了，奇數(shù)問題可以轉(zhuǎn)換為偶數(shù)問題：

2*2*2*2*2=2 * (2*2*2*2) 奇數(shù)問題可以轉(zhuǎn)化為偶數(shù)問題。 

這里，遞歸的解法如下：

long c=10000007; 
public  long divide(long a, long b) { 
        if (b == 0) 
            return 1; 
        else if (b % 2 == 0) //偶數(shù)情況 
            return divide((a % c) * (a % c), b / 2) % c; 
    else//奇數(shù)情況 
            return a % c * divide((a % c) * (a % c), (b - 1) / 2) % c; 
    } 

非遞歸實現(xiàn)也不難，控制好循環(huán)條件即可：

//求 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; 
} 

對于非遞歸你可能有點模糊為啥偶數(shù)情況不給res賦值。這里有兩點：

• 為奇數(shù)的情況res僅僅是收集相乘那個時候落單的a
• 最終b均會降到1，a最終都會和res相乘，不用擔心會漏掉
• 理想狀態(tài)一直是偶數(shù)情況，那最后直接獲得a取模的值即可。

如果還是不懂，可以用這個圖來解釋一下：

矩陣快速冪

你以為這就結(jié)束了?雖然快速冪主要內(nèi)容就是以上內(nèi)容，但是總有很多牛人能夠發(fā)現(xiàn)很有趣的規(guī)律—矩陣快速冪。如果你沒聽過的話建議仔細看看了解一下。

大家都知道斐波那契數(shù)列：的規(guī)則：

前幾個斐波那契的數(shù)列為：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

斐波那契從遞推式就可以看出是指數(shù)級別的增長，所以稍微多幾個數(shù)字就是爆炸式增長，所以很多時候也會要求最后幾位的結(jié)果。有了前面模運算公式溢出就不成問題，但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)]之間的什么規(guī)律呢?

答案是存在規(guī)律的，看上面的公式知道：

[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]   
 
=·······           

所以現(xiàn)在你可以知道它的規(guī)律了吧，這樣一直迭代到f(2),f(1)剛好都為1，所以這個斐波那契的計算為：

而這個矩陣有很多次冪，就可以使用快速冪啦，原理一致，你只需要寫一個矩陣乘法就可以啦,下面提供一個矩陣快速冪求斐波那契第n項的后三位數(shù)的模板，可以拿這個去試一試poj3070的題目啦。

public int Fibonacci(int n) 
    { 
        n--;//矩陣為兩項 
        int a[][]= {{1,1},{1,0}};//進行快速冪的矩陣 
        int b[][]={{1,0},{0,1}};//存儲漏單奇數(shù)、結(jié)果的矩陣，初始為單位矩陣 
        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數(shù)值的整數(shù)次方)上就有一道快速冪的問題，我們用學的東西鞏固一下：

實現(xiàn) pow(x n) ，即計算 x 的 n 次冪函數(shù)(即，x^n)。不得使用庫函數(shù)，同時不需要考慮大數(shù)問題。

這個簡單題需要考慮一些特殊情況：

• n正負性
• 邊界(int最大和最小)

在實現(xiàn)上首先判斷n正負，將負次冪轉(zhuǎn)成正次冪。如果中轉(zhuǎn)一層long處理就不會出現(xiàn)這些問題。

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); 
    } 
} 

結(jié)語

這篇到這里就肝完啦，其實快速冪的內(nèi)容還不止這么多，尤其是矩陣快速冪，會有著各種巧妙的變形，不過跟數(shù)學有一些關(guān)系，在力扣上比較少，但是在其他OJ上快速冪題目還是很多的可以自行找一下刷一刷。

是不是看完又get一個小知識!