Hallo Hagen,
vielen Dank für die Erklärungen, das kommt schon näher an das was ich suche
Ich schreibe mal ein paar Kommentare dazu
Zitat von
negaH:
Die Breakevenpoints zwischen den verschiednene Algorithmen können sehr unterschiedlich sein.
Je nachdem
1.) ob man quadriert oder multipliziert
2.) welche Algorithmen man implementiert hat
3.) wie man diese implementiert hat
4.) ob man inplaced arbeitet oder nicht
5.) auf welchen Prozessoren man arbeitet
In meinem DECMath habe ich für die Multiplikation verschiedene Algos implementiert, Reichenfolge nach Zahlengrößen vom kleinsten zum größten
Die verschiedenen Algorithmen habe ich erkannt durch die Aufrufdeklarationen. Was 'inplaced' bedeutet ist mir nicht klar. Ich selber arbeite auf einem AMD WinXP 2,4 GHz unter Nutzung des mathematischen Co-Prozessors (ich denke das ist der SSE2 Befehlssatz)
Zitat von
negaH:
1.) Schoolboy Methode bis ca. 10 Digits
2.) Comba Methode bis ca. 38 Digits
3.) Karatsuba bis ca. 108 Digits
4.) Toom-Cook-3 bis 5376 Digits
5.) Schönhage FFT ab 5376 Digits aufwärts
1 Digit sind 4 Bytes, ich rechne intern also meistens mit 32Bit Datentypen.
Datentyp Cardinal, habe ich gesehen, Könnte ich mich daran gewöhnen
Zu meinen Brakevens gleich mehr
Zitat von
negaH:
Die Quadrierung benutzt ebenfalls diese Algortihmen aber in spezial Form, ergo ergeben sich ander Breakeven
1.) Schoolboy Methode bis ca. 12 Digits
2.) Comba Methode bis ca. 62 Digits
3.) Karatsuba bis ca. 174 Digits
4.) Toom-Cook-3 bis 5376 Digits
5.) Schönhage FFT ab 5376 Digits aufwärts
Wie man sieht ist die Quadrierung effiziernter als die Multiplikation wodurch sich die Breakeven Points nach oben verschieben.
Man sieht auch das sich die FFT erst mit "gigantisch" großen Zahlen lohnt >>> 2^172032 !
Das Quadrierung effizienter ist habe ich mir gedacht (und in dem Testlauf zu deiner Bibliothek wird es ja auch schön dargestellt^^). Wie die Karatsuba-Methode aber für die Quadratur verbessert werden soll ist mir unklar. Bei Karatsuba werden die zu multiplizierenden Zahlen ja in Zifferblöcke zerlegt, die auch bei einer Quadratur schon im ersten Rekursionschritt nicht mehr gleich sein müssem. Schon ab dem 1. Rekursionschritt muss ich also auch bei Quadratur schon wieder zur 'normalen' Multiplikation greifen. Ich erhalte deswegen bei der K-Methode in etwa die gleiche Laufzeit bei Multiplikation und bei Quadratur.
Zitat von
negaH:
Nun kommts aber, denn diese Breakeven Points gelten ausschließlich für "lame 486'er". Da ich zb. für > Pentium 4 die SSE2 und MMX Befehle in der Schoolboy und FFT und Toom-Cook benutze verändert sich die Breakevens enorm
Multiplikation:
1.) Schoolboy Methode bis ca. 16 Digits
2.) Comba Methode wird nicht benutzt
3.) Karatsuba bis ca. 64 Digits
4.) Toom-Cook-3 bis 5461 Digits
5.) Schönhage FFT ab 5461 Digits aufwärts
Die Comba Methode wird garnicht mehr benutzt, sie ist nur ein Trick in der Schoolboy Methode die die Teilprodukte anders ausrechnet und hat auf Grund der schlechteren oder besseren ? Pipline Architektur der Pentiums keinen Vorteil mehr.
Die größten Performancesteiergerungen bingt die Toom-Cook-3 Methode sowohl in Richtung Karatsuba und in Richtung FFT. In Beiden Richtungen erweitert sie ihren Breakeven Bereich und wird demzufolge häufiger auf Pentiums benutzt als auf anderen 486 Prozessoren (Pentium 2,3 und älter).
Das liegt hautpsächlich daran das ich eben die SS2 Befehle benutze, also quasi 64 Bit Multiplikationen intern durchführe statt 32 Bit breite.
Tom-Cook-3 Methode habe ich schon vom Namen her gehört aber mich noch nicht näher mit befasst, Ich wollte erst den SchönStrAlg realisieren bevor ich versuche ihn zu optimieren
Die Auswirkungen der verschiedenen Prozessoren ist für mich momentan eher nebensächlich, wie gesagt, ich möchte den Alg auf meinem System programmieren, seine Logik verstehen und einfach selber brauchbar zusammen bekommen.
Zitat von
negaH:
Allerdings muß man das alles relativieren, da eben der Pentium 4 Core im Grunde 2 mal langsammer ist als zb der Pentium 3 Core. Die SSE2 Befehle, die 2 mal schneller sind als normale Befehle, schaffen also erst den realen Performancevorteil eines Pentium 4 im Vergleich zu einem Pentium 3. Ich rede hier NICHT von einem höher getakteten System sondern vergleiche die reale Anzahl der notwendigen Taktzyklen für diese Operationen unabhängig vom Prozessortakt. Der P4 ist also ziemlich lahm.
Klar dürfte auch sein das zb. die Schönhage FFT im innersten Kern auf die Karatsuba Methode und somit wiederum auf die Schoolboy Methode zurückgreift. Das gleiche gilt für Toom-Cook. Sie zerlegt die Zahlen quasi rekursiv bis sie auf diese Teilprodukte die Schoolboy Methode anwendet. Essentiell benötigt man also sehr schnelle Schoolboy Multiplikationen/Quadrierungen und Addtionenen/Subtraktionen/Überlauf/Unterlauf Funktionen.
Gruß Hagen
Das Eine Multipliaktion bei der rekursiven Berechnung abhängig von der aktuellen Ziffernanzahl in die jeweils beste Methode verzweigt ist klar. Für Add/Sub/Mul mit2/Div durch 2 habe ich schnelle Algorithmen auf Assembler-ebene realisiert, ebenso Karatsuba, die sind gut genug für mich. Überlauf/Unterlauf vermute ich benötigst du bei der Verwendung von Variablen dynamischer Digitlänge. Ich habe da dann einen einfachen, statischen Datenblock vorliegen und sollte wegen der Moduloberechnung solche Routinen nicht brauchen. Mein momentanes Brekeven zwischen Karatsuba und FFT liegt momentan übrigens ca. bei 2^21 Bits Ausgangszahllänge (geschätzt), wenn man weiss, das die K-Methode bei dieser Länge mehrere Sekunden braucht zur Multiplikation, kann man sich vorstellen, das meine Implementierung der FFT noch sehr hmmm... rudimentär ist. Zu den speziellen Problemen aber mehr in meinem Fred. Ich habe gesehen, das du dort auch geantwortet hat. Hier erst mal herzlichen Dank für deine ausführlichen Informationen, das hilft mir sehr. insbesondere Tom-Cook-3 werde ich wohl mal suchen und lernen müssen.
mfg
Matthias