Ich wollte NTT für schnelle Quadrierung verwenden (siehe Schnelle bignum-Quadrat-Berechnung ), aber das Ergebnis ist selbst für langsam wirklich große Zahlen .. mehr als 12000 Bits.
Meine Frage ist also:
Dies ist mein (bereits optimierter) Quellcode in C ++ für NTT (er ist vollständig und 100% funktionierend in C ++, ohne Notwendigkeit für Drittanbieter-Bibliotheken und sollte auch Thread-sicher sein. Vorsicht, das Quell-Array wird als temporäres verwendet !!!, kann das Array auch nicht in sich selbst verwandeln).
%Vor%Beispiel für die Verwendung meiner NTT-Klasse:
%Vor%Einige Messungen vor Optimierungen (nicht Klasse NTT):
%Vor%Einige Messungen nach meinen Optimierungen (aktueller Code, kleinere Rekursionsparametergröße / Anzahl und bessere modulare Arithmetik):
%Vor%Überprüfen Sie die NTT mul und NTT sqr mal (meine Optimierungen beschleunigen es etwas mehr als 3x). Es ist nur 1x mal Schleife, so dass es nicht sehr präzise ist (Fehler ~ 10%), aber die Beschleunigung ist auch jetzt bemerkbar (normalerweise loope ich 1000x und mehr, aber mein NTT ist dafür zu langsam).
Du kannst meinen Code frei benutzen ... Halte einfach meinen Nick und / oder Link zu dieser Seite irgendwo (rem in code, readme.txt, über oder was auch immer). Ich hoffe, es hilft ... (Ich habe keine C ++ Quelle für schnelle NTTs gesehen, also musste ich es selbst schreiben). Die Wurzeln der Einheit wurden für alle akzeptierten N getestet, siehe die fourier_NTT::init(DWORD n) Funktion.
S.S .: Weitere Informationen zu NTT finden Sie unter Ссылка . Dieser Code basiert auf meinen Posts in diesem Link.
[edit1:] Weitere Änderungen im Code
Ich habe es geschafft, meine modulare Arithmetik weiter zu optimieren, indem ich ausnutze, dass Modulo Prime immer 0xC0000001 ist und unnötige Aufrufe eliminiert. Die resultierende Beschleunigung ist jetzt atemberaubend (mehr als 40 mal) und NTT Multiplikation ist schneller als Karatsuba nach etwa 1500 * 32 Bits Schwelle. BTW, die Geschwindigkeit meines NTT ist jetzt die gleiche wie meine optimierte DFFT auf 64-Bit-Doppel.
Einige Messungen:
%Vor%Neuer Quellcode für modulare Arithmetik:
%Vor% Wie Sie sehen, werden die Funktionen shl und shr nicht mehr verwendet. Ich denke, dass ModPow weiter optimiert werden kann, aber es ist keine kritische Funktion, weil es nur sehr wenige Male aufgerufen wird. Die kritischste Funktion ist modmul, und das scheint in der bestmöglichen Form zu sein.
Weitere Fragen:
[edit2] Neue Optimierungen
%Vor%Ich habe alle brauchbaren Sachen aus all deinen Kommentaren implementiert (Danke für die Einsicht).
Beschleunigungen:
Tatsächlicher vollständiger Quellcode:
%Vor% Es gibt immer noch die Möglichkeit, weniger Heap-Abfall zu verwenden, indem NTT_fast auf zwei Funktionen getrennt wird. Eins mit WW[] und das andere mit iWW[] , was bei Rekursionsaufrufen zu einem Parameter weniger führt. Aber ich erwarte nicht viel davon (nur 32-Bit-Zeiger) und habe eher eine Funktion für eine bessere Codeverwaltung in der Zukunft. Viele Funktionen ruhen jetzt (zum Testen) wie langsame Varianten, mod und die ältere schnelle Funktion (mit w -Parameter anstelle von *w2,i2 ).
Um Überläufe für große Datenmengen zu vermeiden, begrenzen Sie die Eingabezahlen auf p/4 Bits. Dabei ist p die Anzahl der Bits pro NTT -Element für diese 32-Bit-Version Verwenden Sie max (32 bit/4 -> 8 bit) Eingabewerte.
[edit3] Einfache Zeichenfolge bigint Multiplikation zum Testen
Ich benutze AnsiString 's, also portiere ich es hoffentlich in char* , ich habe keinen Fehler gemacht. Es sieht so aus, als ob es richtig funktioniert (im Vergleich zur AnsiString Version).
sx,sy sind dekadische ganze Zahlen (char*)=sx*sy zurück
Dies ist nur ~ 4 Bit pro 32-Bit-Datenwort, so dass keine Gefahr eines Überlaufs besteht, aber es ist natürlich langsamer. In meinem bignum lib verwende ich eine binäre Darstellung und verwende 8 bit chunks pro 32-Bit WORD für NTT . Mehr als das ist riskant, wenn N groß ist ...
Viel Spaß mit diesem
Zunächst einmal, vielen Dank für die Veröffentlichung und die Nutzung freizugeben. Ich weiß das wirklich zu schätzen.
Ich konnte ein paar Tricks anwenden, um einige Verzweigungen zu eliminieren, die Hauptschleife umzuordnen und die Assembly zu modifizieren, und ich konnte eine 1,35fache Beschleunigung erzielen.
Außerdem habe ich eine Präprozessorbedingung für 64 Bit hinzugefügt, da Visual Studio keine Inline-Assemblierung im 64-Bit-Modus zulässt (danke, Microsoft; fühlen Sie sich frei, sich selbst zu schinden).
Etwas Seltsames ist passiert, als ich die Funktion modsub () optimiert habe. Ich habe es mit Bit-Hacks neu geschrieben wie ich modadd (was schneller war). Aber aus irgendeinem Grund war die bitweise Version von modsub langsamer. Nicht sicher warum. Könnte nur mein Computer sein.
%Vor%Neues Modul
%Vor%[BEARBEITEN] Spektre, aufgrund deines Feedbacks habe ich den modadd & amp; modsub zurück zu ihrem ursprünglichen. Ich erkannte auch, dass ich einige Änderungen an der rekursiven NTT-Funktion vorgenommen hatte, die ich nicht hätte.
[EDIT2] Nicht benötigte if-Anweisungen und bitweise Funktionen wurden entfernt.
[EDIT3] Neue modmul-Inline-Assembly hinzugefügt.
Tags und Links optimization c++ performance modular-arithmetic ntt