Hi Felix,
zuerstmal rate ich dir mit Assembler zu arbeiten. Dabei gibt es keine Unterscheidung zwischen 32 Bit Integern mit oder ohne Vorzeichen da intern immer im komplementären Zahlen (bei Vorzeichen) gearbeitet wird. Das Vorzeichen spielt also bei der 32 Bit
ASM Multiplikation keine Rolle, ebenso bei der Addition und Subtraktion.
Als nächstes musst du also die Entscheidung treffen wie deine Langzahlen definiert sind, also wie das Vorzeichen gespeichert wird. Als am sinnvollsten hat sich Signed Magnitude herausgestellt. Dh. das Vorzeichen der Lanhzahl wird extern in einem eigenen zb. Boolean gespeichert. Für Mul/Div ist also das sich ergebende Vorzeichen = Vorzeichen A xor Vorzeichen B.
Die Langzahl selber stellt also immer den Absolutbetrag der Zahl dar.
Nun zu den einzelenen Verfahren:
1.) Schoolboy, das ist das was du schon machst
2.) COMBA. das ist Schoolby aber leicht optimiert, eine Pyramidenförmige Multiplikation bei der die partiellen Zwischenprodukte pyramidenförmig addiert werden und somit besser auf 32 Bit Rechnern optimiert sind.
3.) Karatsuba Multiplikation
4.) TOOM-COOK Multiplikation, das ist wie Karatsuba nur teilt man nicht in 2 Teile sondern in 3,5,7 usw.
5.) FFT, genauer die Schönhage-Strassen-modulare-Fermat-Fast-Fourier-Transformation
Alle dieses Methoden habe ich in meinem DECMath schon implementiert. Die Selektion welche dieser Verfahren dann zur Laufzeit angewendet werden hängt von einer Thesholdtabelle ab, also von der Digitanzahl=Anzahl von 32Bit Werten, der beiden Multilikanten. Diese Breakeven-Tabelle wird für verscheidene Rechnerarchitekturen errechnet. Das ist nötig da zb. die Multiplikation und Addition/Subtrakton bei mir als Low-Low-Level Funktionen als I32 wie auch SSE2 Assembler Funktinen vorliegen. Und da sind wir bei der nächsten Entscheidung: Umsetzung in Assembler in 32 Bit IA32 Code oder SSE2 oder MMX (für zb. Boolsche Operationen XOR, OR, AND usw.) Mit SSE2 kann man dann statt mit 32Bit Digit mit 64Bit Digits arbeiten, man zerlegt also den Langzahl-Speicherbereich nicht in 32Bit Digits sonder 64Bit Digits.
Aber für die Multiplikation von 2x 128Bit Werten kann ich dir jetzt schon sagen das die Schoolboy Methode am effizientesten sein wird. Die COMBA Methode lohnt sich dann nur für ältere Rechner da sie die Speicherzugriffe optimiert und bei neueren Rechnern sind diese kein Problem mehr.
Also würde ich an deiner Stelle mit SSE2 Assembler implementieren, nachdem du eine normale IA32 MUL implementiert hast. Nur das schafft noch einen Performanceboost von Faktor x2. Falls du immer mit fixen 128 Bit Zahlen arbeitest dann dürfte mit SSE2 noch mehr drinnen sein.
Auf SSE2 Rechnern gilt für die Multipliaktion bei meinem DECMath:
Die Karatsuba lohnt erst ab so ca. 42 Digits = 1344 Bit Zahlen.
Toom-Cook-3 bei 7424 Bits.
Die FFT sogar erst ab 177984 Bit großen Zahlen.
Für die Quadrierung, die ca. 1.5mal schneller sein kann als eine Multiplikation gilt:
Karatsuba 2048 Bit Zahlen
Toom-Cook-3 7552 Bit Zahlen
FFT 174784 Bit großen Zahlen
Diese Breakeven's gelten für beide Multiplikanten, jeweils der kleiner zählt. Also zb. 256 Bit * 128 Bit bedeutet das man defakto 2x eine 128 Bit Mul machen muß. Man muß also die 256 Bit große Zahl in 2 Teile a 128 Bit zerlegen und diese dann mit der anderen 128 Bit großen Zahl multiplizieren. Man betrachtet also die 256 Bit große Zahl als eine Zahl mit 2 Digit = 2 Ziffern und die 128 Bit große Zahl als eine mit 1 Digit= 1 Ziffer a 128 Bit Größe.
Daran erkennt man das man nach Möglichkeit die Zwischenresultate eines mathematischen Verfahrens auf gleiche Größe gewichten sollte um die höchste Performance rauszuholen.
Aufbauend auf einer Lanzahl * 1 Digit Multiplikation in Assembler kannst du jede höherwertige Multiplikation programmieren. Es hat sich aber gezeigt das es aus Sicht der Performance auch gut ist wenn man eine Langzahl * Langzahl Schoolboy Multiplikation in purem Assembler implementiert, statt diese aus mehreren Aufrufen der Langzahl * 1 Digit Mul in Hochsprache aufzubauen.
Mein DECMath benutzt ebenfalls ein Signed Magnitude Speicherformat der Langzahlen. Allerdings noch mit Optimierungen im Speichermanagement. Dh. der Speicherbereich der Langzahl wird in bestimmten Schrittweiten immer prealloziert statt für jedes Digit immer neu beim Speichermanager neu zu reallozieren zu müssen. Somit führt die Langzahl-Datenstruktur die reale Größe in Digits und die benutzte Anzahl der Digits als 2 Recordfelder mit, neben dem Vorzeichen als Boolean.
Falls du weiterführende Fragen hast dann frag mich einfach
Gruß Hagen