1

I've been doing some research looking for a relatively fast square root algorithm that operates on big integers. I found a couple of routines on here. The first one (below) was written in C...

int isqrt(int n)
{
  int b = 0;

  while(n >= 0)
  {
    n = n - b;
    b = b + 1;
    n = n - b;
  }

  return b - 1;
}

...which I found here: Looking for an efficient integer square root algorithm for ARM Thumb2

I implemented this routine due to its simplicity and efficient use of buffer space. However, as it is simple, the performance is beyond unacceptable. It does work and gives the correct answer when returning just b and not b - 1.

So in my quest of a better algorithm, I came across the following algorithm written in Java...

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;
    }
}

...which I found on this question: How can I find the Square Root of a Java BigInteger?

I will gladly admit that I am not well versed in Java, so the question that I have is what does the line BigInteger y = div.add(x.divide(div)).shiftRight(1); do?

In my limited knowledge, I have a possible conversion of the loop to the C code fragment below, but I don't know enough about Java to be sure.

while (1)
{
    x /= div;
    div += x;
    y = x >> 1;

    if (y == div || y == div2) return(y);
    div2 = div;
    div = y;
}

Is this correct?

Community
  • 1
  • 1
Daniel Rudy
  • 1,411
  • 12
  • 23

1 Answers1

3

Yes, it is correct.

Let us translate!

BigInteger y = div.add(x.divide(div)).shiftRight(1);
//becomes
long int y = (div + (x / div)) >> 1;
//this also applies to Java (you don't 'need' BigInteger or its fancy methods)

and the rest is pretty straight-forward. You're just comparing to see if y is equal to div or div2, and if it's not, shuffle the values over and try again.

Yidna
  • 452
  • 4
  • 12
  • That worked. Thanks. In looking at the C rendition, it looks like the Newton's method of square root calculation. Using this method, it went from about 92s to 113us. Big improvement. – Daniel Rudy Jul 19 '16 at 06:37
  • I'm pretty sure that **is** the Newton method. It is probably faster if you start with a good guess, instead of `1/div`. In my BigInteger `sqrt()` calculation, I shift `div` right by half its bitsize as a first approximate. Of course that makes more sense with a huge BigInteger than with a simple int. – Rudy Velthuis Jul 19 '16 at 14:57