Большие целые числа, квадратный корень, java и C: Что делает эта линия?

Question

Я занимаюсь некоторыми исследованиями, которые ищут относительно быстрый алгоритм квадратного корня, который работает с большими целыми числами. Здесь я нашел несколько подпрограмм. Первый из них (ниже) была написана в C ...

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

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

    return b - 1; 
} 

... который я нашел здесь: Looking for an efficient integer square root algorithm for ARM Thumb2

Я реализовал эту процедуру из-за своей простоты и эффективности использования буферного пространства. Однако, поскольку это просто, производительность выходит за рамки неприемлемого. Он работает и дает правильный ответ при возвращении только b, а не b - 1.

Так в моих поисках лучшего алгоритма, я наткнулся на следующий алгоритм написанный на 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; 
    } 
} 

... который я нашел на этот вопрос: How can I find the Square Root of a Java BigInteger?

Я буду с удовольствием признать, что я не очень разбираюсь в Java, поэтому вопрос, который у меня есть, - это то, что делает линия BigInteger y = div.add(x.divide(div)).shiftRight(1);?

В моем ограниченном знании, у меня есть возможное преобразование цикла в фрагмент кода C ниже, но я не знаю достаточно о Java, чтобы быть уверенным.

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

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

Это правильно?

Answer 1

Да, это правильно.

Переведем!

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) 

, а остальное довольно прямолинейно. Вы просто сравниваете, видите ли y равно div или div2, и если это не так, перетасуйте значения и повторите попытку.