Finding the Square Root of a BigInteger in Java

1. Overview

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.

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

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

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:

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.

2.2. Guava’s BigIntegerMath

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

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:

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

2.3. NewtonPlus Method

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¹⁴.

3. Performance Comparison

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:

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:

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.

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

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.

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.