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 1014.
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.
As usual, all the code is available over on GitHub.
