作者：小傅哥
博客：https://bugstack.cn - 包含: JAVA 基礎(chǔ)，面經(jīng)手冊?.NETty4.x，手寫Spring，用Java實現(xiàn)JVM，重學(xué)Java設(shè)計模式，SpringBoot中間件開發(fā)，IDEA插件開發(fā)，DDD系統(tǒng)架構(gòu)項目開發(fā)，字節(jié)碼編程...
沉淀、分享、成長，讓自己和他人都能有所收獲！一、前言
不知道讀者伙伴用了那么久的 Java Math 函數(shù)，是否有打開它的源碼，看看是如何實現(xiàn)的。比如 Math.pow 函數(shù)計算數(shù)字的次方值，只要你打開它的源碼，你會驚訝到；這在弄啥，這都是啥，這要干啥！
這是啥，這就是一段用于計算次方的算法。簡單來說，它是通過在 Math.pow 中預(yù)先構(gòu)建了一個基于查表的算法，保存了常用的冪的值，然后使用這些值來快速計算冪次方。
其實用于計算次冪的方法還有很多，包括；遞歸、滑動窗口（Sliding-window method）、蒙哥馬利的梯子技術(shù)（Montgomery's ladder technique）、固定底數(shù)（Fixed-base exponent）等方式來計算。接下來小傅哥就給大家分享下這些算法方案。
二、算法實現(xiàn)
其實無論是那樣一種計算次冪的方式，都離不開核心的基礎(chǔ)模型。也就是說，任何一個數(shù)的次冪，都是這個次冪下數(shù)字的乘積累計值。包括使用遞歸、還是通過二進(jìn)制數(shù)字移位，最終都要?dú)w到冪的乘積。
- 這里舉例了2^4次冪遞歸計算和2^10次冪使用二進(jìn)制移位。
- 接下來我們可以看下具體的代碼實現(xiàn)。
public static double pow01(double base, double power) { if (power == 0) { return 1; } if (power % 2 == 0) { double multiplier = pow01(base, power / 2); return multiplier * multiplier; } double multiplier = pow01(base, Math.floor(power / 2)); return multiplier * multiplier * base; }
- 把次方數(shù)不斷的通過除2遞歸，計算乘積值。就和上圖中的左面部分邏輯一致。
public static long pow03(int base, int exponent) { if (exponent == 0) { return 1; } if (exponent == 1) { return base; } long result = 1; long window = base; while (exponent > 0) { if ((exponent & 1) == 1) { result *= window; } window *= window; exponent >>= 1; } return result; }
- 滑動窗口法是一種用于在一個數(shù)列中查找滿足某些條件的子序列的算法。它的基本思路是，使用一個指針指向子序列的左端點，然后通過不斷移動這個指針來擴(kuò)展子序列的右端點，直到找到滿足條件的子序列為止。
public static BigInteger pow04(BigInteger x, BigInteger n) { BigInteger x1 = x; BigInteger x2 = x.multiply(x); for (int i = n.bitLength() - 2; i >= 0; i--) { if (n.TestBit(i)) { x1 = x1.multiply(x2); x2 = x2.multiply(x2); } else { x2 = x1.multiply(x2); x1 = x1.multiply(x1); } } return x1; }
- 蒙哥馬利的梯子技術(shù)（Montgomery's ladder technique）是一種在密碼學(xué)中計算冪次方的算法。它的基本思路是通過不斷地進(jìn)行二次求冪運(yùn)算來計算高次冪。
- 蒙哥馬利的梯子技術(shù)需要使用 BigInteger 類型的數(shù)據(jù)進(jìn)行計算。BigInteger 類是 Java 中的一個用于處理任意精度整數(shù)的類。
public static BigInteger pow05(BigInteger base, BigInteger exponent) { int e = exponent.intValue(); BigInteger result = BigInteger.ONE; BigInteger current = base; while (e > 0) { if ((e & 1) == 1) { result = result.multiply(current); } current = current.multiply(current); e >>= 1; } return result; }
- 固定底數(shù)指數(shù)法（Fixed-base exponentiation）是一種用于快速計算冪次方的算法。它的基本思路是使用預(yù)先計算的冪的表來減少求冪的次數(shù)。
@Test public void test_FastPowering() { System.out.println("測試結(jié)果：" + FastPowering.pow01(2, 4)); System.out.println("測試結(jié)果：" + FastPowering.pow02(2, 10)); System.out.println("測試結(jié)果：" + FastPowering.pow03(2, 4)); System.out.println("測試結(jié)果：" + FastPowering.pow04(BigInteger.valueOf(2), BigInteger.valueOf(10))); System.out.println("測試結(jié)果：" + FastPowering.pow05(BigInteger.valueOf(2), BigInteger.valueOf(10))); }
測試結(jié)果
測試結(jié)果：16.0 測試結(jié)果：1024 測試結(jié)果：16 測試結(jié)果：1024 測試結(jié)果：1024 Process finished with exit code 0
- https://en.wikipedia.org/wiki/Exponentiation_by_squaring
