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