Computing the square root of big numbers is a problem for computers. The way computations happen, computers don’t really like the huge numbers some scientists like to put out. Even if For several applications you can easily go from int to long or from float to double, there are times when even those aren’t enough.
Java has a few classes that deal with large numbers. They are BigInteger and BigDecimal. Between the two you’ll probably get almost everything you need for big number computation.
Although the way to do operations with the BigInteger and BigDecimal can be counter-intuitive in mathematical terms, it is correct in an object oriented way. The only thing that I found lacking until now is a method to calculate square roots in BigDecimals… That is annoying.
I searched around the internet and found an elegant (and fast) implementation for BigDecimals of the square root by Michael Gilleland. I’m copying is code here at the end of this post for the sake of preservation (I hate sites going away and these things being lost).
Java code for large number computing of square roots
The code bellow for computing the square root of large numbers works very well. You just need to remember to set the scale (the number of digits you want in the fractional part) to 100 or more. Yes, that’s the kind of precision one sometimes needs and that’s why I can’t convert to doubles, do sqrt, and go back to BigDecimal.
The class BigSquareRoot for computing large numbers square roots in Java. Next step: Compute the number PI as a large number computation with the same precision.
//----------------------------------------------------------
// Compute square root of large numbers using Heron's method
//----------------------------------------------------------
import java.math.*;
public class BigSquareRoot {
private static BigDecimal ZERO = new BigDecimal("0");
private static BigDecimal ONE = new BigDecimal("1");
private static BigDecimal TWO = new BigDecimal("2");
public static final int DEFAULT_MAX_ITERATIONS = 50;
public static final int DEFAULT_SCALE = 10;
private BigDecimal error;
private int iterations;
private boolean traceFlag;
private int scale = DEFAULT_SCALE;
private int maxIterations = DEFAULT_MAX_ITERATIONS;
// ---------------------------------------
// The error is the original number minus
// (sqrt * sqrt). If the original number
// was a perfect square, the error is 0.
// ---------------------------------------
public BigDecimal getError() {
return error;
}
// -------------------------------------------------------------
// Number of iterations performed when square root was computed
// -------------------------------------------------------------
public int getIterations() {
return iterations;
}
// -----------
// Trace flag
// -----------
public boolean getTraceFlag() {
return traceFlag;
}
public void setTraceFlag(boolean flag) {
traceFlag = flag;
}
// ------
// Scale
// ------
public int getScale() {
return scale;
}
public void setScale(int scale) {
this.scale = scale;
}
// -------------------
// Maximum iterations
// -------------------
public int getMaxIterations() {
return maxIterations;
}
public void setMaxIterations(int maxIterations) {
this.maxIterations = maxIterations;
}
// --------------------------
// Get initial approximation
// --------------------------
private static BigDecimal getInitialApproximation(BigDecimal n) {
BigInteger integerPart = n.toBigInteger();
int length = integerPart.toString().length();
if ((length % 2) == 0) {
length--;
}
length /= 2;
BigDecimal guess = ONE.movePointRight(length);
return guess;
}
// ----------------
// Get square root
// ----------------
public BigDecimal get(BigInteger n) {
return get(new BigDecimal(n));
}
public BigDecimal get(BigDecimal n) {
// Make sure n is a positive number
if (n.compareTo(ZERO) <= 0) {
throw new IllegalArgumentException();
}
BigDecimal initialGuess = getInitialApproximation(n);
trace("Initial guess " + initialGuess.toString());
BigDecimal lastGuess = ZERO;
BigDecimal guess = new BigDecimal(initialGuess.toString());
// Iterate
iterations = 0;
boolean more = true;
while (more) {
lastGuess = guess;
guess = n.divide(guess, scale, BigDecimal.ROUND_HALF_UP);
guess = guess.add(lastGuess);
guess = guess.divide(TWO, scale, BigDecimal.ROUND_HALF_UP);
trace("Next guess " + guess.toString());
error = n.subtract(guess.multiply(guess));
if (++iterations >= maxIterations) {
more = false;
} else if (lastGuess.equals(guess)) {
more = error.abs().compareTo(ONE) >= 0;
}
}
return guess;
}
// ------
// Trace
// ------
private void trace(String s) {
if (traceFlag) {
System.out.println(s);
}
}
// ----------------------
// Get random BigInteger
// ----------------------
public static BigInteger getRandomBigInteger(int nDigits) {
StringBuffer sb = new StringBuffer();
java.util.Random r = new java.util.Random();
for (int i = 0; i < nDigits; i++) {
sb.append(r.nextInt(10));
}
return new BigInteger(sb.toString());
}
// -----
// Test
// -----
public static void main(String[] args) {
BigInteger n;
BigDecimal sqrt;
BigSquareRoot app = new BigSquareRoot();
app.setTraceFlag(true);
// Generate a random big integer with a hundred digits
n = BigSquareRoot.getRandomBigInteger(100);
// Build an array of test numbers
String testNums[] = { "9", "30", "720", "1024", n.toString() };
for (int i = 0; i < testNums.length; i++) {
n = new BigInteger(testNums[i]);
if (i > 0) {
System.out.println("----------------------------");
}
System.out.println("Computing the square root of");
System.out.println(n.toString());
int length = n.toString().length();
if (length > 20) {
app.setScale(length / 2);
}
sqrt = app.get(n);
System.out.println("Iterations " + app.getIterations());
System.out.println("Sqrt " + sqrt.toString());
System.out.println(sqrt.multiply(sqrt).toString());
System.out.println(n.toString());
System.out.println("Error " + app.getError().toString());
}
}
} |
//----------------------------------------------------------
// Compute square root of large numbers using Heron's method
//----------------------------------------------------------import java.math.*;public class BigSquareRoot {private static BigDecimal ZERO = new BigDecimal("0");
private static BigDecimal ONE = new BigDecimal("1");
private static BigDecimal TWO = new BigDecimal("2");
public static final int DEFAULT_MAX_ITERATIONS = 50;
public static final int DEFAULT_SCALE = 10;private BigDecimal error;
private int iterations;
private boolean traceFlag;
private int scale = DEFAULT_SCALE;
private int maxIterations = DEFAULT_MAX_ITERATIONS;// ---------------------------------------
// The error is the original number minus
// (sqrt * sqrt). If the original number
// was a perfect square, the error is 0.
// ---------------------------------------public BigDecimal getError() {
return error;
}// -------------------------------------------------------------
// Number of iterations performed when square root was computed
// -------------------------------------------------------------public int getIterations() {
return iterations;
}// -----------
// Trace flag
// -----------public boolean getTraceFlag() {
return traceFlag;
}public void setTraceFlag(boolean flag) {
traceFlag = flag;
}// ------
// Scale
// ------public int getScale() {
return scale;
}public void setScale(int scale) {
this.scale = scale;
}// -------------------
// Maximum iterations
// -------------------public int getMaxIterations() {
return maxIterations;
}public void setMaxIterations(int maxIterations) {
this.maxIterations = maxIterations;
}// --------------------------
// Get initial approximation
// --------------------------private static BigDecimal getInitialApproximation(BigDecimal n) {
BigInteger integerPart = n.toBigInteger();
int length = integerPart.toString().length();
if ((length % 2) == 0) {
length--;
}
length /= 2;
BigDecimal guess = ONE.movePointRight(length);
return guess;
}// ----------------
// Get square root
// ----------------public BigDecimal get(BigInteger n) {
return get(new BigDecimal(n));
}public BigDecimal get(BigDecimal n) {// Make sure n is a positive numberif (n.compareTo(ZERO) <= 0) {
throw new IllegalArgumentException();
}BigDecimal initialGuess = getInitialApproximation(n);
trace("Initial guess " + initialGuess.toString());
BigDecimal lastGuess = ZERO;
BigDecimal guess = new BigDecimal(initialGuess.toString());// Iterateiterations = 0;
boolean more = true;
while (more) {
lastGuess = guess;
guess = n.divide(guess, scale, BigDecimal.ROUND_HALF_UP);
guess = guess.add(lastGuess);
guess = guess.divide(TWO, scale, BigDecimal.ROUND_HALF_UP);
trace("Next guess " + guess.toString());
error = n.subtract(guess.multiply(guess));
if (++iterations >= maxIterations) {
more = false;
} else if (lastGuess.equals(guess)) {
more = error.abs().compareTo(ONE) >= 0;
}
}
return guess;}// ------
// Trace
// ------private void trace(String s) {
if (traceFlag) {
System.out.println(s);
}
}// ----------------------
// Get random BigInteger
// ----------------------public static BigInteger getRandomBigInteger(int nDigits) {
StringBuffer sb = new StringBuffer();
java.util.Random r = new java.util.Random();
for (int i = 0; i < nDigits; i++) {
sb.append(r.nextInt(10));
}
return new BigInteger(sb.toString());
}// -----
// Test
// -----public static void main(String[] args) {BigInteger n;
BigDecimal sqrt;
BigSquareRoot app = new BigSquareRoot();
app.setTraceFlag(true);// Generate a random big integer with a hundred digitsn = BigSquareRoot.getRandomBigInteger(100);// Build an array of test numbersString testNums[] = { "9", "30", "720", "1024", n.toString() };for (int i = 0; i < testNums.length; i++) {
n = new BigInteger(testNums[i]);
if (i > 0) {
System.out.println("----------------------------");
}
System.out.println("Computing the square root of");
System.out.println(n.toString());
int length = n.toString().length();
if (length > 20) {
app.setScale(length / 2);
}
sqrt = app.get(n);
System.out.println("Iterations " + app.getIterations());
System.out.println("Sqrt " + sqrt.toString());
System.out.println(sqrt.multiply(sqrt).toString());
System.out.println(n.toString());
System.out.println("Error " + app.getError().toString());
}}}
bigsquareroot class in java how to find big square root of a big number in java using biginteger java biginteger square root sqrt big sqrt long java
