1. Overview

1.概述

Often, while working with big numbers, we are limited by the sizes of int and long. Java provides a good way around it with the BigInteger class. However, sometimes, the API doesn’t support all the arithmetic operations we would like to use.

在处理大数字时，我们常常会受到 int 和 long 大小的限制。Java 通过 BigInteger 类提供了很好的解决方法。但是，有时 API 并不支持我们希望使用的所有算术运算。

Finding a square root of a big number is common but often tricky.

求一个大数的平方根很常见，但往往很棘手。

In this tutorial, we’ll learn how to do this and the pros and cons of each approach.

在本教程中，我们将学习如何做到这一点，以及每种方法的优缺点。

2. Calculating a Root

2.计算根

Let’s review a couple of ways to get the desired calculations.

让我们回顾一下获得理想计算结果的几种方法。

2.1. Java 9 BigInteger API

2.1 Java 9 BigInteger API

We’ll start with the most straightforward approach introduced in Java 9. From this version and above, BigInteger provides two helpful methods: sqrt() and sqrtAndReminder(). Let’s review the first one:

我们将从 Java 9 中引入的最直接的方法开始。从该版本及以上，BigInteger 提供了两个有用的方法：sqrt()和sqrtAndReminder()让我们回顾一下第一个方法：

BigInteger integer = new BigInteger(bigDecimalNumber);
BigInteger root = integer.sqrt();

The second one is similar but provides additional information about the reminder:

第二个选项类似，但提供了有关提醒的更多信息：

BigInteger integer = new BigInteger(bigDecimalNumber);
BigInteger[] rootAndReminder = integer.sqrtAndRemainder();

Both methods provide a simple and transparent way to calculate a root. However, it requires a specific Java version, which might be problematic for some applications.

这两种方法都提供了一种简单、透明的根计算方法。不过，它需要特定的 Java 版本，这对于某些应用程序来说可能会有问题。

2.2. Guava’s BigIntegerMath

2.2.Guava 的 BigIntegerMath.

Another way to calculate the root without bumping the Java version is to use the Guava library:

另一种无需提升 Java 版本即可计算根的方法是使用 Guava 库：

BigInteger integer = new BigInteger(bigDecimalNumber);
BigInteger root = BigIntegerMath.sqrt(integer, RoundingMode.DOWN);

The method takes RoundingMode to identify the rounding logic. The library doesn’t provide a simple way to get the reminder, so if we need it, we’ll have to do some additional steps:

该方法使用 RoundingMode 来识别四舍五入逻辑。该库没有提供获取提醒的简单方法，因此如果我们需要，就必须执行一些额外的步骤：

BigInteger integer = new BigInteger(bigDecimalNumber);
BigInteger root = BigIntegerMath.sqrt(integer, RoundingMode.DOWN);
BigInteger reminder = integer.subtract(root.multiply(root));

2.3. NewtonPlus Method

2.3 牛顿加法</b

It’s possible, but in most cases, not recommended, to implement a custom solution for finding a square root of a big integer. Often, custom implementations might have higher complexity and lower throughput. There are a couple of simple but inefficient algorithms, such as the Binary Search and Newton’s Method.

实现自定义解决方案来查找大整数的平方根是可能的，但在大多数情况下并不推荐。通常情况下，自定义实现可能具有更高的复杂性和更低的吞吐量。有几种简单但效率不高的算法，例如二进制搜索和牛顿法。

However, there’s one algorithm that outperforms both standard Java and Guava’s implementations. The NewtonPlus algorithm was introduced by Ryan Scott White and based on Newton’s method. The algorithm shows performance improvements starting with the numbers above 5 x 10¹⁴.

不过，有一种算法的性能优于标准 Java 和 Guava 的实现。NewtonPlus 算法由Ryan Scott White提出，基于牛顿方法。该算法从 5 x 10¹⁴ 以上的数字开始显示性能改进。

3. Performance Comparison

3.性能比较

Let’s run a performance test for the Java, Guava library, NewtonPlus, and Newton’s methods to check for any significant differences between them. We’ll run the test cases on three different values:

让我们运行 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

After running the JMH benchmarks, we got the following results:

运行 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

The NewtonPlus method shows the best performance, which might be a good option for applications that require a high volume of such computations. At the same time, if adding a custom, highly optimized code to the codebase isn’t a very attractive idea, we can opt for Guava’s BigIntegerMath, which has a relatively good performance.

NewtonPlus 方法显示了最佳性能，对于需要大量此类计算的应用程序来说，这可能是一个不错的选择。同时，如果在代码库中添加高度优化的自定义代码不是一个非常有吸引力的想法，我们可以选择 Guava 的 BigIntegerMath，它具有相对较好的性能。

Also, simple algorithms like Newton’s are inefficient and should be avoided. The Binary Search method, in general, is less performant than Newton’s method as it has a lower rate of convergence.

此外，牛顿法等简单算法效率较低，应避免使用。二进制搜索法的收敛速度较低，因此性能一般不如牛顿法。

4. Conclusion

4.结论

While working with huge numbers, we need a convenient way to perform standard mathematical operations over them. From a mathematical perspective, the operations are the same regardless of the size of a number, but computer science creates certain constraints. That’s why we need specific libraries and algorithms to work with BigIntegers.

在处理庞大的数字时，我们需要一种方便的方法来对它们进行标准数学运算。从数学的角度来看，无论数字的大小如何，运算都是相同的，但计算机科学会产生某些限制。这就是我们需要特定的库和算法来处理 BigIntegers 的原因。

Depending on the specificity of the task at hand, we can opt for a different solution, ranging from standard libraries to custom solutions that are finely tuned to the application requirements. However, premature optimization is never good and often harmful. Thus, we should be reasonable in our choices.

根据手头任务的特殊性，我们可以选择不同的解决方案，从标准库到根据应用需求进行微调的定制解决方案，不一而足。然而，过早优化绝非好事，而且往往有害无益。因此，我们应合理选择。

As usual, all the code is available over on GitHub.

像往常一样，所有代码都可以在 GitHub 上获取。