快速冪演算法

設計一個演算法計算\(x^n\)的值。

根據定義最常見也最能瞬間想到的是如下的演算法：

// 遞歸寫法
public int pow1(int x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;
  return x * pow1(x, n - 1);
}
// 迴圈寫法
public int pow2(int x, int n) {
  int y = 1;
  while (n) {
    y *= x;
    n--;
  }
  return y;
}

但上面的演算法的時間複雜度是\(O(n)\)

下麵採用快速冪演算法來解決這個問題。

在解決它之前先來看一下原理：

所以我們可以對本身要求的\(x^n\)對半分來求，只求一半的數，然後乘以自己本身就可以達到\(x^n\)

但是會出現的情況就是，對半分的時候會出現小數的情況，所以一定要分奇數和偶數的情況。

如果n分半了之後是偶數，那就直接對半分，如果是奇數則在對半分之後還要乘以一個x。

所以可以有下麵的規律：

f(x, n) = {
  f(x, n/2)*f(x, n/2),    // 當n為偶數
  x*f(x, n/2)*f(x, n/2)   // 當n為奇數
}

所以得出快速冪演算法1：

public int qPow1(int x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;
  if (n % 2 == 1) return x*f(x, n/2)*f(x, n/2);
  return f(x, n/2)*f(x, n/2);
}

但是上面的演算法明顯沒有任何增進，因為f(x, n/2)要算兩次，那和之前的\(O(n)\)的演算法沒什麼區別。所以使用一個中間變數去接受一下，就可以提高演算法效率。

public int qPow1(int x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;
  int t = f(x, n/2)
  if (n % 2 == 1) return x * t * t;
  return t * t;
}

上面的快速冪演算法還是比較好理解的，下麵的快速冪演算法就比較的炫技了我覺得，但是也就那樣（原理還是上面的，只是不是對半分而已，而是根據進位數來分）。

下麵採用二進位數來分。

假設我們要計算的是\(x^{10}\)，那麼10的二進位數是1010，所以有如下公式及變換：

即

和上面第一種快速冪的演算法類似，只不過上一種採用的分法是：

那麼不管怎樣分，最後肯定會被分到1，因為\(x^0=1\)，其實上面的分法都隱藏了一個\(x^0\)，即：

所以狀態是怎麼轉移的，即每一次迭代都是怎樣變化的。初始化\(t=x^{2^0}=x^1=x\)，那麼下一代的變化是\(x^{2^1}\)，它是由\(x^{2^0*2}\)變化而來，因為採用的是二進位。所以指數部分要想從\(2^0\)變換到\(2^1\)就需要乘以一個2.那也就是說，\(x\)變到\(x^2\).那麼迭代變化過程就是\(t=t*t\).

\(x^{2^0*2}=(x^{2^0})^2\)

所以得到第二種快速冪演算法代碼：

public int qPow2(int x, int n) {
  int y = 1;
  int t = x;
  while (n > 0) {
    switch (n % 2) {
      case 1: y = y * t;  // 這裡不要寫break
      case 0: t = t * t;
    }
    n = n / 2;
  }
  return y;
}

那麼這個採用二進位的方法分，當然也有三進位的，四進位的，五進位的等等。十六進位就不要搞了，因為不是進位越高就越快。

通過我對上面的二進位寫法的快速冪就可以看出來我還會有其他進位的寫法。那麼下麵就來看一下三進位的寫法，然後四進位的就順其自然就明白了。

那麼三進位的推導過程也是和二進位的推導過程是類似的。假設計算的是\(x^{10}\).

所以從二進位的分法和三進位的分法可以看出，不管怎麼分都是可以合起來達到10.只要能達到10的說明採用什麼進位分法都是可以的。但並不是說採用的進位越高就越好。

那麼初始化\(t=x^{3^0}=x\)，那麼下一代的變化是\(x^{3^1}\)，它是由\(x^{3^0*3}\)變化而來，因為採用的是三進位。所以指數部分要想從\(3^0\)變換到\(3^1\)就需要乘以一個3.那也就是說，\(x\)變到\(x^3\).那麼迭代變化過程就是\(t=t*t*t\).

\(x^{3^0*3}=(x^{3^0})^3\)

對比一下二進位和三進位的區別，所以四進位往後的就不需要我一個個推導了吧。

直接得出演算法代碼：

public int qPow3(int x, int n) {
  int y = 1;
  int t = x;
  while (n > 0) {
    switch (n % 3) {
      case 2: y = y * t;  // 這裡不要寫break
      case 1: y = y * t;  // 這裡不要寫break
      case 0: t = t * t * t;
    }
    n = n / 3;
  }
  return y;
}

直接得出四進位版本的代碼：

public int qPow4(int x, int n) {
  int y = 1;
  int t = x;
  while (n > 0) {
    switch (n % 4) {
      case 3: y = y * t;  // 這裡不要寫break
      case 2: y = y * t;  // 這裡不要寫break
      case 1: y = y * t;  // 這裡不要寫break
      case 0: t = t * t * t * t;
    }
    n = n / 4;
  }
  return y;
}

直接得出五進位版本的代碼：

public int qPow5(int x, int n) {
  int y = 1;
  int t = x;
  while (n > 0) {
    switch (n % 5) {
      case 4: y = y * t;  // 這裡不要寫break
      case 3: y = y * t;  // 這裡不要寫break
      case 2: y = y * t;  // 這裡不要寫break
      case 1: y = y * t;  // 這裡不要寫break
      case 0: t = t * t * t * t;
    }
    n = n / 5;
  }
  return y;
}

以此類推。。。就不寫了。

可以去測試一下：

public class Main {
        public static void main(String[] args) {
                System.out.println("計算2的10次方：");
                int x = 2, n = 10;
                Solution s = new Solution();
                showMessage("pow1: ",  s.pow1(x, n));
                showMessage("pow2: ",  s.pow2(x, n));
                showMessage("qPow1: ", s.qPow1(x, n));
                showMessage("qPow2: ", s.qPow2(x, n));
                showMessage("qPow3: ", s.qPow3(x, n));
                showMessage("qPow4: ", s.qPow4(x, n));
                showMessage("qPow5: ", s.qPow5(x, n));
        }
        public static void showMessage(String str, int result) {
                System.out.println("---------------------");
                System.out.println(str + result);
                System.out.println("---------------------");
        }
}

class Solution {
        public int pow1(int x, int n) {
                if (n == 0) return 1;
                if (n == 1) return x;
                return x * pow1(x, n - 1);
        }
        public int pow2(int x, int n) {
                int y = 1;
                while (n > 0) {
                        y = y * x;
                        n--;
                }
                return y;
        }
        public int qPow1(int x, int n) {
                if (n == 0) return 1;
                if (n == 1) return x;
                int t = qPow1(x, n / 2);
                if (n % 2 == 1) return x * t * t;
                return t * t;
        }
        public int qPow2(int x, int n) {
                int y = 1;
                int t = x;
                while (n > 0) {
                        switch (n % 2) {
                                case 1: y = y * t; // 這裡不要寫break
                                case 0: t = t * t;
                        }
                        n = n / 2;
                }
                return y;
        }
        public int qPow3(int x, int n) {
                int y = 1;
                int t = x;
                while (n > 0) {
                        switch (n % 3) {
                                case 2: y = y * t;  // 這裡不要寫break
                                case 1: y = y * t;  // 這裡不要寫break
                                case 0: t = t * t * t;
                        }
                        n = n / 3;
                }
                return y;
        }
        public int qPow4(int x, int n) {
                int y = 1;
                int t = x;
                while (n > 0) {
                        switch (n % 4) {
                                case 3: y = y * t;  // 這裡不要寫break
                                case 2: y = y * t;  // 這裡不要寫break
                                case 1: y = y * t;  // 這裡不要寫break
                                case 0: t = t * t * t * t;
                        }
                        n = n / 4;
                }
                return y;
        }
        public int qPow5(int x, int n) {
                int y = 1;
                int t = x;
                while (n > 0) {
                        switch (n % 5) {
                                case 4: y = y * t;  // 這裡不要寫break
                                case 3: y = y * t;  // 這裡不要寫break
                                case 2: y = y * t;  // 這裡不要寫break
                                case 1: y = y * t;  // 這裡不要寫break
                                case 0: t = t * t * t * t * t;
                        }
                        n = n / 5;
                }
                return y;
        }
}

終端輸出：

計算2的10次方：
---------------------
pow1: 1024
---------------------
---------------------
pow2: 1024
---------------------
---------------------
qPow1: 1024
---------------------
---------------------
qPow2: 1024
---------------------
---------------------
qPow3: 1024
---------------------
---------------------
qPow4: 1024
---------------------
---------------------
qPow5: 1024
---------------------

然後來分析一下它們的執行效率。

一般的\(O(n)\)就不說了，肯定是比\(O(log_2n)\)差的。主要是看是不是進位越高就越好？先給出答案，並不一定是。看著qPow5好像可以更快收到答案，但我們忘了看\(t=t*t*t*t*t\)這段代碼和它上面的那一坨。然後再放大一點看，如果我採用的是十進位的寫法。那會發現狀態轉移是\(t=t*t*t...（10個t）\)那和一般的pow有什麼區別？所以，從這一點可以看出來並不是進位越高就越好。就好像是用\(x^8x^2\)和\(x^2x^8\)比效率一樣。都是一樣的嘛，如果外層迴圈少了，那裡面的乘法就多了。所以得找個平衡的點。那這個平衡的點一般也就是對半的時候（並不是所有情況都是），所以我們折騰了那麼久又回到了二進位的版本。因為電腦底層是二進位，所以我們就採用二進位的版本，然後再採用代碼上的語法優化，這樣應該是更好一點，因為其它進位的版本可優化的點並不多。下麵給出二進位優化的版本。

public int qPow2(int x, int n) {
  int y = 1;
  int t = x;
  while (n > 0) {
    if (n % 2 == 1) y *= t;
    t *= t;
    n >>= 1;
  }
  return y;
}

因為Java語法本身的原因在做位運算的時候不能像C/C++一樣可以用非零當作真。所以if (n % 2 == 1) y *= t;並不改變。但如果是C/C++的話可以採用下麵的版本：

int qPow2(int x, int n) {
  int y = 1;
  while (n) {
    if (n & 1) y *= t;
    t *= t;
    n >>= 1;
  }
  return y;
}

快速冪演算法就先到這裡結束了。