在 Java 中求 BigInteger 的平方根
1. 概述
通常，在處理大數時，我們會受到int和long. Java 透過BigInteger類別提供了一種解決此問題的好方法。然而，有時，API 並不支援我們想要使用的所有算術運算。
求大數的平方根很常見，但往往很棘手。
在本教程中，我們將學習如何執行此操作以及每種方法的優缺點。
2. 計算根
讓我們回顧一下獲得所需計算結果的幾種方法。
2.1. Java 9 BigInteger API
我們將從 Java 9 中引入的最直接的方法開始。從這個版本及更高版本開始， BigInteger提供了兩個有用的方法： sqrt()和sqrtAndReminder().我們回顧一下第一個：
BigInteger integer = new BigInteger(bigDecimalNumber);
BigInteger root = integer.sqrt();第二個類似，但提供了有關提醒的附加資訊：
BigInteger integer = new BigInteger(bigDecimalNumber);
BigInteger[] rootAndReminder = integer.sqrtAndRemainder();這兩種方法都提供了一種簡單且透明的計算根的方法。但是，它需要特定的 Java 版本，這對於某些應用程式可能會出現問題。
2.2. Guava 的BigIntegerMath
另一種在不影響 Java 版本的情況下計算根的方法是使用 Guava 庫：
BigInteger integer = new BigInteger(bigDecimalNumber);
BigInteger root = BigIntegerMath.sqrt(integer, RoundingMode.DOWN);此方法採用RoundingMode來標識舍入邏輯。該庫沒有提供獲取提醒的簡單方法，因此如果我們需要它，我們將不得不執行一些額外的步驟：
BigInteger integer = new BigInteger(bigDecimalNumber);
BigInteger root = BigIntegerMath.sqrt(integer, RoundingMode.DOWN);
BigInteger reminder = integer.subtract(root.multiply(root));2.3.牛頓加法
可以實現自訂解決方案來找到大整數的平方根，但在大多數情況下不建議這樣做。通常，自訂實作可能具有更高的複雜性和更低的吞吐量。有一些簡單但效率低的演算法，例如二分搜尋和牛頓法。
然而， 有一種演算法的效能優於標準 Java 和 Guava 的實作。 NewtonPlus 演算法由Ryan Scott White提出，基於牛頓法。該演算法顯示了從 5 x 10 14以上的數字開始的效能改進。
3. 效能比較
讓我們對 Java、Guava 函式庫、NewtonPlus 和 Newton 方法進行效能測試，以檢查它們之間是否有顯著差異。我們將在三個不同的值上執行測試案例：
private static final String BIG_NUMBER = "1797693130000000000000000000000..." // 309 digits
private static final String VERY_BIG_NUMBER = "32473927492374927934284792..." // 1802 digits
private static final String INSANELY_BIG_NUMBER = "3247392749237492793428..." // 3604 digits執行 JMH 基準測試後，我們得到以下結果：
Benchmark (number) Mode Cnt Score Error Units
BigIntegerSquareRootBenchmark.calculateRootWithNewton BIG_NUMBER thrpt 2668.642 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithJava BIG_NUMBER thrpt 25417.428 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithGuava BIG_NUMBER thrpt 144117.671 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithNewtonPlus BIG_NUMBER thrpt 308933.077 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithNewton VERY_BIG_NUMBER thrpt 33.627 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithJava VERY_BIG_NUMBER thrpt 1376.668 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithGuava VERY_BIG_NUMBER thrpt 5349.748 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithNewtonPlus VERY_BIG_NUMBER thrpt 12283.677 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithNewton INSANELY_BIG_NUMBER thrpt 9.135 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithJava INSANELY_BIG_NUMBER thrpt 553.475 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithGuava INSANELY_BIG_NUMBER thrpt 1713.520 ops/s
BigIntegerSquareRootBenchmark.calculateRootWithNewtonPlus INSANELY_BIG_NUMBER thrpt 3252.308 ops/sNewtonPlus 方法顯示了最佳效能，對於需要大量此類計算的應用程式來說，這可能是一個不錯的選擇。同時，如果在程式碼庫中添加自訂的、高度優化的程式碼不是一個非常有吸引力的想法，我們可以選擇 Guava 的BigIntegerMath ，它具有相對較好的效能。
此外，像牛頓演算法這樣的簡單演算法效率低下，應該避免。一般來說，二分搜尋方法的表現不如牛頓方法，因為它的收斂速度較低。
4。結論
在處理大量數字時，我們需要一種便捷的方法來對它們執行標準數學運算。從數學角度來看，無論數字大小如何，運算都是相同的，但計算機科學設定了一定的限制。這就是為什麼我們需要特定的函式庫和演算法來處理BigIntegers.
根據手頭任務的特殊性，我們可以選擇不同的解決方案，從標準庫到根據應用程式需求進行微調的自訂解決方案。然而，過早的優化從來都不是好事，而且往往是有害的。因此，我們應該理性地做出選擇。
與往常一樣，所有程式碼都可以在 GitHub 上取得。