Große ganze Zahlen, Quadratwurzel, Java und C: Was macht diese Zeile?

Question

Ich habe ein wenig Forschung betrieben, um nach einem relativ schnellen Quadratwurzel-Algorithmus zu suchen, der auf großen Ganzzahlen operiert. Ich habe ein paar Routinen hier gefunden. Die erste (unten) wurde in C geschrieben ...

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

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

    return b - 1; 
} 

..., die ich hier gefunden: Looking for an efficient integer square root algorithm for ARM Thumb2

ich implementiert diese Routine aufgrund seiner Einfachheit und effiziente Nutzung von Pufferraum. Wie es jedoch einfach ist, ist die Leistung nicht akzeptabel. Es funktioniert und gibt die richtige Antwort, wenn Sie nur b und nicht b - 1 zurückgeben.

Also in meiner Suche nach einem besseren Algorithmus, stieß ich auf den folgenden Algorithmus in Java geschrieben ...

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

..., die ich auf diese Frage gefunden: How can I find the Square Root of a Java BigInteger?

werde ich gerne gib zu, dass ich Java nicht gut beherrsche. Die Frage, die ich habe, lautet: Was macht die Zeile BigInteger y = div.add(x.divide(div)).shiftRight(1);?

In meinem begrenzten Wissen habe ich eine mögliche Umwandlung der Schleife in das C-Code-Fragment unten, aber ich weiß nicht genug über Java, um sicher zu sein.

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

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

Ist das korrekt?

Answer 1

Ja, es ist korrekt.

Lassen Sie uns übersetzen!

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) 

und der Rest ist ziemlich geradlinig. Du vergleichst nur, um zu sehen, ob y gleich div oder div2 ist, und wenn nicht, mische die Werte und versuche es erneut.