在 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/s
NewtonPlus 方法顯示了最佳效能,對於需要大量此類計算的應用程式來說,這可能是一個不錯的選擇。同時,如果在程式碼庫中添加自訂的、高度優化的程式碼不是一個非常有吸引力的想法,我們可以選擇 Guava 的BigIntegerMath
,它具有相對較好的效能。
此外,像牛頓演算法這樣的簡單演算法效率低下,應該避免。一般來說,二分搜尋方法的表現不如牛頓方法,因為它的收斂速度較低。
4。結論
在處理大量數字時,我們需要一種便捷的方法來對它們執行標準數學運算。從數學角度來看,無論數字大小如何,運算都是相同的,但計算機科學設定了一定的限制。這就是為什麼我們需要特定的函式庫和演算法來處理BigIntegers.
根據手頭任務的特殊性,我們可以選擇不同的解決方案,從標準庫到根據應用程式需求進行微調的自訂解決方案。然而,過早的優化從來都不是好事,而且往往是有害的。因此,我們應該理性地做出選擇。
與往常一樣,所有程式碼都可以在 GitHub 上取得。