Square root of BigDecimal in Java

Question

Can we compute the square root of a BigDecimal in Java by using only the Java API and not a custom-made 100-line algorithm?

Answer 1

BigDecimal.valueOf(Math.sqrt(myBigDecimal.doubleValue()));

Answer 2

public static BigDecimal sqrt( final BigDecimal value )
{
    BigDecimal guess = value.multiply( DECIMAL_HALF ); 
    BigDecimal previousGuess;

    do
    {
        previousGuess = guess;
        guess = sqrtGuess( guess, value );
   } while ( guess.subtract( previousGuess ).abs().compareTo( EPSILON ) == 1 );

    return guess;
}

private static BigDecimal sqrtGuess( final BigDecimal guess,
                                     final BigDecimal value )
{
    return guess.subtract( guess.multiply( guess ).subtract( value ).divide( DECIMAL_TWO.multiply( guess ), SCALE, RoundingMode.HALF_UP ) );
}

private static BigDecimal epsilon()
{
    final StringBuilder builder = new StringBuilder( "0." );

    for ( int i = 0; i < SCALE - 1; ++i )
    {
        builder.append( "0" );
    }

    builder.append( "1" );

    return new BigDecimal( builder.toString() );
}

private static final int SCALE = 1024;
private static final BigDecimal EPSILON = epsilon();
public static final BigDecimal DECIMAL_HALF = new BigDecimal( "0.5" );
public static final BigDecimal DECIMAL_TWO = new BigDecimal( "2" );

Answer 3

If you want to calculate square roots for numbers with more digits than fit in a double (a BigDecimal with a large scale) :

Wikipedia has an article for computing square roots: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method

This is my implementation of it:

public static BigDecimal sqrt(BigDecimal in, int scale){
    BigDecimal sqrt = new BigDecimal(1);
    sqrt.setScale(scale + 3, RoundingMode.FLOOR);
    BigDecimal store = new BigDecimal(in.toString());
    boolean first = true;
    do{
        if (!first){
            store = new BigDecimal(sqrt.toString());
        }
        else first = false;
        store.setScale(scale + 3, RoundingMode.FLOOR);
        sqrt = in.divide(store, scale + 3, RoundingMode.FLOOR).add(store).divide(
                BigDecimal.valueOf(2), scale + 3, RoundingMode.FLOOR);
    }while (!store.equals(sqrt));
    return sqrt.setScale(scale, RoundingMode.FLOOR);
}

setScale(scale + 3, RoundingMode.Floor) because over calculating gives more accuracy. RoundingMode.Floor truncates the number, RoundingMode.HALF_UP does normal rounding.

Answer 4

public static BigDecimal sqrt(BigDecimal A, final int SCALE) {
    BigDecimal x0 = new BigDecimal("0");
    BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
    while (!x0.equals(x1)) {
        x0 = x1;
        x1 = A.divide(x0, SCALE, ROUND_HALF_UP);
        x1 = x1.add(x0);
        x1 = x1.divide(TWO, SCALE, ROUND_HALF_UP);

    }
    return x1;
}

This work perfect! Very fast for more than 65536 digits!

Answer 5

If you need to find only integer square roots - these are two methods that can be used.

Newton's method - very fast even for 1000 digits BigInteger:

public static BigInteger sqrtN(BigInteger in) {
    final BigInteger TWO = BigInteger.valueOf(2);
    int c;

    // Significantly speed-up algorithm by proper select of initial approximation
    // As square root has 2 times less digits as original value
    // we can start with 2^(length of N1 / 2)
    BigInteger n0 = TWO.pow(in.bitLength() / 2);
    // Value of approximate value on previous step
    BigInteger np = in;

    do {
        // next approximation step: n0 = (n0 + in/n0) / 2
        n0 = n0.add(in.divide(n0)).divide(TWO);

        // compare current approximation with previous step
        c = np.compareTo(n0);

        // save value as previous approximation
        np = n0;

        // finish when previous step is equal to current
    }  while (c != 0);

    return n0;
}

Bisection method - is up to 50x times slower than Newton's - use only in educational purpose:

 public static BigInteger sqrtD(final BigInteger in) {
    final BigInteger TWO = BigInteger.valueOf(2);
    BigInteger n0, n1, m, m2, l;
    int c;

    // Init segment
    n0 = BigInteger.ZERO;
    n1 = in;

    do {
        // length of segment
        l = n1.subtract(n0);

        // middle of segment
        m = l.divide(TWO).add(n0);

        // compare m^2 with in
        c = m.pow(2).compareTo(in);

        if (c == 0) {
            // exact value is found
            break;
        }  else if (c > 0) {
            // m^2 is bigger than in - choose left half of segment
            n1 = m;
        } else {
            // m^2 is smaller than in - choose right half of segment
            n0 = m;
        }

        // finish if length of segment is 1, i.e. approximate value is found
    }  while (l.compareTo(BigInteger.ONE) > 0);

    return m;
}

Answer 6

Here is very accurate and fast solution, it's based on my BigIntSqRoot solution and the next observation: The square root of A^2B - Is A multiply the root of B. Using this method I can easily calculate the first 1000 digits of square root of 2.

1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472

So here is the source code

public class BigIntSqRoot {
    private static final int PRECISION = 10000;
    private static BigInteger multiplier = BigInteger.valueOf(10).pow(PRECISION * 2);
    private static BigDecimal root = BigDecimal.valueOf(10).pow(PRECISION);
    private static BigInteger two = BigInteger.valueOf(2L);

    public static BigDecimal bigDecimalSqRootFloor(BigInteger x)
            throws IllegalArgumentException {
        BigInteger result = bigIntSqRootFloor(x.multiply(multiplier));
        //noinspection BigDecimalMethodWithoutRoundingCalled
        return new BigDecimal(result).divide(root);
    }

    public static BigInteger bigIntSqRootFloor(BigInteger x)
            throws IllegalArgumentException {
        if (checkTrivial(x)) {
            return x;
        }
        if (x.bitLength() < 64) { // Can be cast to long
            double sqrt = Math.sqrt(x.longValue());
            return BigInteger.valueOf(Math.round(sqrt));
        }
        // starting with y = x / 2 avoids magnitude issues with x squared
        BigInteger y = x.divide(two);
        BigInteger value = x.divide(y);
        while (y.compareTo(value) > 0) {
            y = value.add(y).divide(two);
            value = x.divide(y);
        }
        return y;
    }

    public static BigInteger bigIntSqRootCeil(BigInteger x)
            throws IllegalArgumentException {
        BigInteger y = bigIntSqRootFloor(x);
        if (x.compareTo(y.multiply(y)) == 0) {
            return y;
        }
        return y.add(BigInteger.ONE);
    }

    private static boolean checkTrivial(BigInteger x) {
        if (x == null) {
            throw new NullPointerException("x can't be null");
        }
        if (x.compareTo(BigInteger.ZERO) < 0) {
            throw new IllegalArgumentException("Negative argument.");
        }

        return x.equals(BigInteger.ZERO) || x.equals(BigInteger.ONE);
    }
}