Guter Algorithmus zum multiplizieren großer Zahlen gesucht

[FAlter]

Hi,

ich multipliziere, die Unterprozedur @@multiply (welche sich an keinerlei Vereinbarungen hält...) multipliziert jeweils einen 32-Bit-Wert mit dem einen der 128-Bit-Werte, also 4 32-Bit-Multiplikationen, welche ja 64-Bit-Ergebnisse liefern, mit entsprechenden Additionen (Überträge). Das Ergebnis ist eine 160-Bit-Zahl, die erste wird gleich im Ergebnis gespeichert, die anderen drei Zwischenwerte werden in den bufX gespeichert. Zum Schluss werden die Ergebnisse versetzt zusammenaddiert. Das entspricht also der schriftlichen Multiplikation, und prinzipiell ist es deinem Verfahren ähnlich. Ich erwende zwar keine Shifts, aber ich addiere versetzt, und dass Versetzen ist ja der Sinn deiner Shifts.
Insbesondere, dass die Überträge aus dem CF und nicht verloren gehen hat mir Sorgen bereitet.

Insgesamt habe ich 16 mal multipliziert. Ich addiere ja nicht eine Zahl, die so groß ist, dass sie in keinen int64 mehr passt, in einer in dieselbe Größenordnung passenden Anzahl mit sich selbst, das dauert dann ja Jahre. Meine Tests, die unter anderem über 100000000 Multiplikationen enthalten, haben etwa 3,5 Minuten gebraucht (Pentium 4, kein HT, derzeit 2533 MHz). Ich will nicht wissen, was die Additionsvariante benötigen würde.

Mfg
FAlter

[Hawkeye219]

Hallo,

hier noch ein Link zum Thema: Multiplikation langer Zahlen

Gruß Hawkeye

[FAlter]

Hi,

Zitat von Hawkeye219:

hier noch ein Link zum Thema: Multiplikation langer Zahlen

Das war ja gar nicht so einfach zu verstehen, aber ich glaube jetzt hab ichs.

Ich habe mir dann auch mal überlegt, was das bedeuten würde, wenn ich zwei 64-Bit-Zahlen damit in 32 Bit zerlegen wurde, um das Produkt zu berechnen. Ich bin von 64 Bit unsigned ausgegangen, also ohne Vorzeichen. [edit]Die Einzelnen 32-bittigen "Ziffern" sind aber eh vorzeichenlos.[/edit]

Der Schritt
v=(q-p)(s-r)
sieht mir problematisch aus.

pq und rs sind ja die einzelnen "Stellen", also 32-Bit-Teile er 64-Bit-Zahlen. Sie sind unsigned Integers und können ALLE Werte von 0 bis 2^32-1 sein.

Da gibt es nun z. B. für q-p folgende Fälle:

q > p --> das Ergebnis ist positiv. Wenn p gar 0 ist und q = 2^32-1, ist es 2^32-1.
q = p --> 0
q < p --> das Ergebnis ist negativ. Im Extremfall ist q = 0 und p=2^32-1.

Das Ergebnis muss also Zahlen von +2^32-1 bis -2^32-1 speichern können und daher ist es mindestens 33 Bit groß, weil Vorzeichen wichtig ist. Das Vorzeichen wird ja auch extra im Text betont.

Das gleiche gilt auch für die andere Differenz.
Diese 33-Bit-Zahlen werden jetzt miteinander multipliziert. Das kann der Prozessor aber nicht, er kann nur 32-Bit-Zahlen multiplizieren. Also müsste man die Zahlen erweitern und z. B. einen Algorithmus verwenden, um Zahlen 64-Bittig miteinander zu multiplizieren. Genau das war aber der gesuchte Fall. (Das Ergebnis der 33-Bit-Multiplikation kann übrigens im schlimmsten Fall nur mit 66 Bits oder mehr dargestellt werden...)

Auch andere Gedanken, die ich mir dazu gemacht habe, wie man dieses "Problem" umgehen könnte (und da hatte ich schon einige Ideen) lassen es mir letztlich als kompliziert erscheinen. Da nehme ich doch lieber meine Schulmethode.

Ich habe mich mal in meinem Testprogrammcode durchgewühlt und dort mit Taschenrechner die Anzahl der Multiplikationen gezählt, die dort mit meinem Algo oben durchgeführt werden. In den 3,5 Minuten schafft mein PC 322 Millionen Multiplikationen. Ich denke mal das reicht mir für meine Zwecke aus, denn die Fälle, in denen ich 128 Bits verwenden möchte, sind ja nicht Fälle wo ich viele Berechnungen nacheinander vornehmen möchte, sondern ich habe vor, große Zahlen zu verwenden.

Mfg
FAlter

[negaH]

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

[negaH]

Zitat von Hawkeye219:

Hallo,

hier noch ein Link zum Thema: Multiplikation langer Zahlen

Gruß Hawkeye

Mir sind par Sachen aufgefallen:

1.) es heist Karatsuba und nicht Karazuba, das das dem Prof der diese Arbeit abgenommen hat nicht aufgefallen ist ?

2.) die Analyse des Aufwandes für den Karatsuba Trick ist einseitig. Sie berücksichtigt nicht die Aufwandsdifferenz zwischen Additonen und Multiplikationen. Wenn zb. eine CPU für die Addition 1 Takt benötigt und für die Multiplikation ebenfalls nur 1 oder 2 Takte dann ist der Karatsuba Trick nicht mehr besser als eine Schoolboy Methode. Nun dieser Unterschied im Aufwand für diese beiden Operationen ist aber essentiell und muß für die jeweilige Rechnerarchitektur berücksichtigt werden. Je weniger Takte eine CPU für eine Multiplikation im Vergleich zu Addition benötigt desto weniger lohnt Karatsuba

3.) die Addition der partiellen Zwischenprodukte wurde links wie rechts mit Nullen erweitert und dann davon ausgehend die Anzahl der Additionen berechnet um den Gesamtaufwand zu errechnen. Das ist natürlich ineffizient und nicht nötig. Normalerweise addiert man zwei Speicherbereiche mit unterschiedlichen Offsets in diese Bereiche und somit auch wirklich nur diejenigen Ziffern die von Relevanz sind.

4.) bei der Karatsuba Methode muß man schon einiges an Intelligenz investieren damit man unnötige Speicherkopierungen vermeidet, also Daten im Speicher hin&her zu kopieren. Diesen Aufwand muß man ebenfalls berücksichtigen und kann mit dem Aufwand der Addition gleichgesetzt werden.

Gruß Hagen