Erstellen Sie mit Python ein Programm, das Millionen von Ziffern paralleler 2er-Wurzeln berechnet. Die Berechnungsmethode verwendet die folgende Newton-Iterationsmethode für inverse Zahlen. Iterativ: x = x + x * (1-x * x / 2) / 2 Das Merkmal dieser Methode ist, dass es keine mehrstellige Unterteilung gibt. Der n-stellige Berechnungsteil in Python lautet wie folgt. def sqrt2(n): bit, dec = 40, 12 d12 = 100001000010000 x = int( math.sqrt(2)(1 << bit) ) while dec <= n: dec = dec << 1 d2 = 1 << (2bit) x0 = (xx) >> 1 x1 = (d2 - x0) >> 1 x2 = (xx1) >> bit x = (x << bit) + x2 + 1 bit = 2bit d12 = d12d12 x = (x*d12) >> bit dec_o = (n // 100)*100 return x
Das Format (x) ist erforderlich, um das Berechnungsergebnis von x = sqrt2 (n) in eine Dezimalzahl umzuwandeln. Die gesamte Python-Version finden Sie im Abschnitt zum Python-Programm unter https://ecc-256.com. Laden Sie sqrt2 herunter und ändern Sie sqrt2.py und den ersten zu importierenden Import. Geben Sie an der Eingabeaufforderung python sqrt2.py ein. Geben Sie als Nächstes die Anzahl der Ausgangsziffern ein. 1000000 für 1 Million Stellen
Die Berechnungszeit von 3 Millionen, 6 Millionen, 12 Millionen für Windows 10-PCs (4 GHz) ist wie folgt. x=sqrt(n) : 6.7, 19.9, 59.7 (s) format(x) : 136, 545, 2180 (s)
Die Dezimalumrechnung für die Ausgabe dauert viel länger als die Berechnung von sqrt (2). sqrt (2) benötigt doppelt so viele Ziffern und dreimal so lange, und die Dezimalkonvertierung dauert viermal so lange. Die Berechnungsmultiplikation ist die Karatsuba-Methode, und die Umrechnungsmultiplikation beruht auf der Definitionsformel.
Selbst in Python kann es beschleunigt werden, indem mit etwa 1000 Dezimalstellen skaliert wird (Wert ist binär int) und eine Hochgeschwindigkeits-Restkonvertierung (FMT) angewendet wird. Das Ziel liegt innerhalb von 3 Minuten auf einem 4-GHz-PC, einschließlich der Berechnung von 100 Millionen Ziffern und der Konvertierung in Dezimalzeichen (Ende Februar).
Recommended Posts