Can someone explain me this function that finds the square root of an BigInteger in Java?

Question

So I need to sqrt a BigInteger in pre Java 9 and I found below function to do that. I do understand the code, but I don't really get why its there. So I guess I don't really get the math behind it. Like why is (n / 32 + 8) used. Why is mid calculated the way it is. etc.

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

This looks much more efficient: https://stackoverflow.com/questions/4407839/how-can-i-find-the-square-root-of-a-java-biginteger — Adam, Nov 06 '19 at 22:02
@Adam Warning: at least the top voted answer returns wrong values for some small numbers. See comments. — Modus Tollens, Nov 07 '19 at 03:56

VimGoodEmacsBad · Answer 1 · 2019-11-08T20:06:16.480

5

EDIT: James Reinstate Monica Polk is correct, this is not the Babylonian Method but rather the Bisection method. I did not look at the code carefully enough before answering. Please see his answer as it is more accurate than mine.

This looks to be the Babylonian Method for approximating square roots. (n/32 + 8) is just used as a "seed", as providing a sane starting value can provide a better approximation in fewer iterations than just picking any number.

edited Nov 08 '19 at 20:06

answered Nov 06 '19 at 22:21

VimGoodEmacsBad

76
6

1

I disagree, it is *not* the Babylonian method. Rather it is the bisection method. The bisection method converges more slowly than the Babylonian method. – President James K. Polk Nov 07 '19 at 21:52

score 2 · Accepted Answer · answered Nov 07 '19 at 22:09

2

The algorithm is the bisection method applied to finding the zero of the polynomial x² - n = 0. Why is (n / 32 + 8) used as a seed? I have no idea as it is a rather poor approximation. A much better approximation that is almost as cheap to compute is n.shiftRight(n.bitLength()/2);

answered Nov 07 '19 at 22:09

President James K. Polk

40,516
21
95
125

You are correct, I didn't look closely enough at the code before answering, and I wasn't aware of the bisection method before my answer. Thank you for the correction. – VimGoodEmacsBad Nov 08 '19 at 20:07

Can someone explain me this function that finds the square root of an BigInteger in Java?

2 Answers2