0

I wanted to calculate the square root of BigInteger in Java. While investigating, I found this great link How can I find the Square Root of a Java BigInteger?, asked earlier on StackOverflow.

There are two great code snippets given to solve this. But the underlying logic or maths is missing.

This is the first one :

BigInteger sqrt(BigInteger n) {
  BigInteger a = BigInteger.ONE;
  BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
  while(b.compareTo(a) >= 0) {
    BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
    if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE);
    else a = mid.add(BigInteger.ONE);
  }
  return a.subtract(BigInteger.ONE);
}

taken from here.

This is the second one : 

public static BigInteger sqrt(BigInteger x) {
    BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);
    BigInteger div2 = div;
    // Loop until we hit the same value twice in a row, or wind
    // up alternating.
    for(;;) {
        BigInteger y = div.add(x.divide(div)).shiftRight(1);
        if (y.equals(div) || y.equals(div2))
            return y;
        div2 = div;
        div = y;
    }
}

answered by @EdwardFalk.

Can anyone please explain or point to the underlying maths or logic, for the completeness of the topic.

Community
  • 1
  • 1
Naveen
  • 7,944
  • 12
  • 78
  • 165

1 Answers1

0

Both are basically a newton iteration.

However the first code snippet has some strange twists, so I would go for the second snippet.

Henry
  • 42,982
  • 7
  • 68
  • 84
  • Thanks I understood the iteration rule and the second code seems more obvious. But I don't understand what the line `BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);` is doing? Is it setting `div=1`? – Naveen Oct 24 '15 at 06:17
  • It creates a starting point for the iteration that is near the square root, i.e. a number halve the length of `x` by setting a single bit at this position. – Henry Oct 24 '15 at 06:20
  • Half the length, literally or mathematically? – Naveen Oct 24 '15 at 06:34
  • half the number of (binary) digits. – Henry Oct 24 '15 at 06:50