Понимание базовой логики/математики для вычисления квадратного корня BigInteger в Java

Question

Я хотел вычислить квадратный корень BigInteger в Java. Во время расследования я нашел эту замечательную ссылку How can I find the Square Root of a Java BigInteger?, заданную ранее в StackOverflow.

Для решения этой проблемы существует два замечательных фрагмента кода. Но основная логика или математика отсутствует.

Это первая одна:

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

взяты из here.

Это второй один:

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

ответил @EdwardFalk.

Может кто-нибудь объяснить или указать основные математические данные или логику, для полноты темы.

Answer 1

Оба являются в основном newton iteration.

Однако первый фрагмент кода имеет некоторые странные повороты, поэтому я бы пошел на второй фрагмент.