Berechnen Quadratwurzel eines BigInteger (System.Numerics.BigInteger)

Question

.NET 4.0 bietet den System.Numerics.BigInteger Typ für beliebig große ganze Zahlen. Ich muss die Quadratwurzel (oder eine vernünftige Approximation - z. B. eine ganze Quadratwurzel) eines BigInteger berechnen. Damit ich das Rad nicht neu implementieren muss, hat jemand eine schöne Erweiterungsmethode dafür?

Answer 1

Der einfachste gangbare Weg eine Quadratwurzel mit beliebiger Genauigkeit zu berechnen ist wahrscheinlich Newton's method.

Answer 2

Ich bin nicht sicher, ob Newton-Verfahren ist der beste Weg zur Berechnung von Quadratwurzeln bignum, weil es Divisionen beinhaltet, die für bignums langsam . Sie können eine CORDIC-Methode verwenden, die (für nicht signierte Ints hier gezeigt) nur zusätzlich und Verschiebungen verwendet

static uint isqrt(uint x) 
{ 
    int b=15; // this is the next bit we try 
    uint r=0; // r will contain the result 
    uint r2=0; // here we maintain r squared 
    while(b>=0) 
    { 
     uint sr2=r2; 
     uint sr=r; 
        // compute (r+(1<<b))**2, we have r**2 already. 
     r2+=(uint)((r<<(1+b))+(1<<(b+b)));  
     r+=(uint)(1<<b); 
     if (r2>x) 
     { 
      r=sr; 
      r2=sr2; 
     } 
     b--; 
    } 
    return r; 
} 

Es gibt eine ähnliche Methode, die nur zusätzlich und Verschiebungen verwendet, ‚Dijkstras Square Root‘ genannt, zum Beispiel hier erklärt:

• http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf

Answer 3

Check if BigInteger is not a perfect square hat Code die ganzzahligen Quadratwurzel einer Java BigInteger zu berechnen. Hier wird es als Erweiterung in C# übersetzt.

public static BigInteger Sqrt(this BigInteger n) 
    { 
     if (n == 0) return 0; 
     if (n > 0) 
     { 
      int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2))); 
      BigInteger root = BigInteger.One << (bitLength/2); 

      while (!isSqrt(n, root)) 
      { 
       root += n/root; 
       root /= 2; 
      } 

      return root; 
     } 

     throw new ArithmeticException("NaN"); 
    } 

    private static Boolean isSqrt(BigInteger n, BigInteger root) 
    { 
     BigInteger lowerBound = root*root; 
     BigInteger upperBound = (root + 1)*(root + 1); 

     return (n >= lowerBound && n < upperBound); 
    } 

Informelle Tests haben ergeben, dass es sich dabei um 75X langsamer als Math.Sqrt, für kleine Zahlen. Der VS-Profiler zeigt auf die Multiplikationen in isSqrt als Hotspots.

Answer 4

Kurze Antwort: (aber Vorsicht, siehe unten für weitere Details)

Math.Pow(Math.E, BigInteger.Log(pd)/2) 

Wo pd die BigInteger darstellt, auf dem Sie die Quadratwurzel Operation ausgeführt werden soll.

Lange Antwort und Erklärung:

Ein anderer Weg, um dieses Problem zu verstehen, ist zu verstehen, wie Quadratwurzeln und Protokolle zu arbeiten.

Wenn Sie die Gleichung haben , für x zu lösen, müssen wir Protokolle verwenden. In diesem Beispiel verwende ich natürliche Protokolle (Protokolle in anderen Basen sind ebenfalls möglich, aber das natürliche Protokoll ist der einfache Weg).

5^x = 25 

Umschreiben, haben wir:

x(ln 5) = ln 25 

x zu isolieren, haben wir

x = ln 25/ln 5 

Wir sehen dies in x = 2 führt. Aber da wir bereits x (x = 2, in 5^2) kennen, ändern wir das, was wir nicht wissen, schreiben eine neue Gleichung und lösen das neue Unbekannte. Sei x das Ergebnis der Wurzeloperation.Dies gibt uns

2 = ln 25/ln x 

x zu isolieren Umschreiben wir

ln x = (ln 25)/2 

haben das Protokoll zu entfernen, verwenden wir jetzt eine besondere Identität des natürlichen Logarithmus und die spezielle Nummer e. Genauer gesagt, e^ln x = x. Umschreiben nun die Gleichung gibt uns

e^ln x = e^((ln 25)/2) 

die linke Seite Vereinfachen, haben wir

x = e^((ln 25)/2) 

wo x wird die Quadratwurzel von 25. Sie sich auch diese Idee zu einer Wurzel oder Zahl erstrecken könnten, und die allgemeine Formel für die yte Wurzel von x wird e^((ln x)/y).

Um dies jetzt speziell auf C#, BigIntegers und diese Frage anzuwenden, implementieren wir einfach die Formel. WARNUNG: Obwohl die Mathematik korrekt ist, gibt es begrenzte Grenzen. Diese Methode bringt Sie nur in die Nachbarschaft mit einem großen unbekannten Bereich (abhängig davon, wie groß eine Nummer ist, auf der Sie arbeiten). Vielleicht hat Microsoft deshalb eine solche Methode nicht implementiert.

// A sample generated public key modulus 
var pd = BigInteger.Parse("101017638707436133903821306341466727228541580658758890103412581005475252078199915929932968020619524277851873319243238741901729414629681623307196829081607677830881341203504364437688722228526603134919021724454060938836833023076773093013126674662502999661052433082827512395099052335602854935571690613335742455727"); 
var sqrt = Math.Pow(Math.E, BigInteger.Log(pd)/2); 

Console.WriteLine(sqrt); 

HINWEIS: Die BigInteger.Log() Methode gibt eine doppelte, so zwei Bedenken bestehen. 1) Die Nummer ist ungenau, und 2) gibt es eine obere Grenze, was Log() für BigInteger Eingaben verarbeiten kann. Um die obere Grenze zu untersuchen, können wir die normale Form für das natürliche Protokoll betrachten, das ist ln x = y. Mit anderen Worten, e^y = x. Da double der Rückgabetyp BigInteger.Log() ist, würde es zu Grunde liegen, die größte BigInteger wäre dann und erhöht auf double.MaxValue. Auf meinem Computer wäre das e^1.79769313486232E+308. Die Ungenauigkeit ist unbehandelt. Wer möchte BigDecimal implementieren und BigInteger.Log() aktualisieren?

Verbraucher Vorsicht, aber es wird Sie in der Nachbarschaft bekommen, und die Quadratur des Ergebnisses erzeugt eine Zahl ähnlich der ursprünglichen Eingabe, bis zu so viele Ziffern und nicht so präzise wie RedGreenCode's Antwort. Glückliche (quadratische) Verwurzelung! ;)

Answer 5

Sie können dies in die Sprache und die Variablentypen Ihrer Wahl konvertieren. Hier ist eine abgeschnittene Quadratwurzel in JavaScript (am frischesten für mich), die 1 + 3 + 5 ... + n-te ungerade Zahl = n^2 nutzt. Alle Variablen sind Ganzzahlen und addieren und subtrahieren nur.

var truncSqrt=function(n){ 
var oddNumber=1; 
var result=0; 
while (n>=oddNumber) { 
    n-=oddNumber; 
    oddNumber+=2; 
    result++; } 
return result; }`