Wie können wir die schnellstmögliche Bignum-Quadratur erreichen?

Schnelle Bignum-Quadrat-Berechnung

Problem:
Gegeben sind zwei Bigints, die als dynamische Arrays von vorzeichenlosen DWORDs dargestellt werden, Berechnen Sie y = x^2 so schnell wie möglich ohne Präzision Verlust.

Kontext:
Das Problem entsteht im Zusammenhang mit der Beschleunigung von Bignum-Divisionen, bei denen Quadratoperationen von entscheidender Bedeutung sind.

Frage:
Wie man y = x^2 am effizientesten berechnet Art und Weise?

Antwort:
Anfänglicher Ansatz:
Der anfängliche Ansatz verwendet eine Multiplikation y = xx, wodurch mehrfache Multiplikationen durch Reduzieren vermieden werden NN Multiplikationen zu (N 1)*(N/2) Multiplikationen.

Karatsuba-Multiplikation:
Der Karatsuba-Multiplikationsalgorithmus wird verwendet, um Multiplikationsoperationen weiter zu optimieren. Es verwendet Divide-and-Conquer, um die Multiplikation zu beschleunigen, indem es große Zahlen in kleinere Teile zerlegt.

Leistungsmessungen:
Tests haben gezeigt, dass die optimierte Karatsuba-Multiplikation die anfängliche O( N^2) Multiplikationsalgorithmus für größere Zahlen (ca. 32*98 Bit).

Geändert Schönhage-Strassen-Multiplikation für die SQR-Implementierung:
Die modifizierte Schönhage-Strassen-Multiplikation, bekannt als FFT (Fast Fourier Transform), wird implementiert, um SQR-Operationen zu beschleunigen. Aufgrund des Genauigkeitsverlusts gilt es jedoch als unbrauchbar.

NTT-Optimierung:
Die NTT (Number Theoretic Transform) wird zur Optimierung von Multiplikations- und SQR-Operationen verwendet. Es ist schneller als FFT, erfordert jedoch modulare Arithmetik und ist durch die Zahlengröße begrenzt.

Aktueller Status:
Die aktuelle Implementierung verwendet den optimierten Karatsuba-Algorithmus für SQR-Operationen bei der Zahlengröße einen bestimmten Schwellenwert überschreitet und der anfängliche schnelle SQR-Ansatz für kleinere Zahlen.

Hervorragend Fragen:
Der Autor räumt ein, dass es möglicherweise eine trivialere oder effizientere Lösung gibt, die übersehen wurde. Die Suche nach einem besseren Algorithmus geht weiter.

Das obige ist der detaillierte Inhalt vonWie können wir die schnellstmögliche Bignum-Quadratur erreichen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!