Hallo,
durch Delphi-Laie wurde ich auf den Schönhage-Strassen-Algorithmus de.wikipedia.org/wik...Strassen-Algorithmus zur schnellen Multiplikation großer Zahlen hingewiesen. Bevor ich den ansatzweise verstehe, wird es aber noch einiger Arbeit benötigen.
Aus diesem Grund habe ich mir "erst einmal" den Karazuba-Algorithmus de.wikipedia.org/wik...aratsuba-Algorithmus und den Toom-Cook-Algorithmus en.wikipedia.org/wik...3Cook_multiplication vorgenommen, die scheinbar einfacher sind.

Mit Hilfe Gammatesters MP_Arith habe ich nun versucht, beide Algorithmen umzusetzen, und bin ganz schön auf die Nase gefallen.
Meine Lösung ist ungenügend, da die Berechnungszeiten wesentlich länger sind als bei einer normalen Multiplikation. Nach der Theorie müsste es aber gerade entgegengesetzt sein. Das Toom-Cook-Verfahren müsste das schnellste sein (bei Gammatester ist das so) und vor allem, wenn die Zahlen länger werden.

Im Beispielprogramm werden 2 zufällige Zahlen erzeugt und dann mit 6 Verfahren multipliziert:
der klassischen Multiplikation, Gammatesters Karazuba- und Toom-Cook-Algorithmen und meinen eigenen Versuchen zum Karazuba-Verfahren (iterativ und rekursiv) sowie dem Toom-Cook-Verfahren.
Irgendetwas mache ich wieder grundlegend falsch. Zwar entstehen die richtigen Produkte, aber eben nach viel längerer Zeit.

Gammatesters Algorithmen einfach zu kopieren, möchte ich nicht, da ich es eigentlich selbst verstehen möchte.
Vielleicht hat jemand von Euch etwas Zeit auf meine Programmierversuche zu sehen. Für jeden Hinweis bin ich dankbar.

Beste Grüße
Mathematiker

Nur ein paar kurze Kommentare, da ich eigentlich im Urlaub bin, und auch für die nächsten zwei Wochen wohl nicht erreichbar sein werde.

Es ist tödlich, innerhalb von Karatsuba/Toom mp_div, mp_mod, mp_read_decimal_astr zu verwenden! Außerdem wird zB bei
doppelte Arbeit verrichtet: wenn schon div und mod dann beide mit mp_divrem gleichzeitig berechnen. Aber wie gesagt, man sollte (eigentlich muß) auch div/mod ganz verzichteten und auch auf die vielleicht praktische Zerlegung via Zehnerpotenzen. Alles was nicht via shift in mp_digits oder Zweierpotenzen realisiert wird, kann allenfalls didaktische Zwecke erfüllen (vielleicht bei sehr sehr großen Cutoffs auch mal schneller als die Basismultiplikation sein). Möglichst sollten auch rekursive Initialisierungen via mp_init vermieden werden, MPArith verwendet s_mp_fakeinit für die Splits ohne mp_init (ist aber nur geeignet für konstante Parameter!, siehe Gefahrenhinweis im Code.)

Wenn Du wirklich eigene Routine machen willst, solltest Du auf jeden Fall mit mp_digits und Zweierpotenzen arbeiten, wenn's dann läuft, kann man immer noch optimieren.

Gruß Gammatester

Hallo Gammatester,

Gammatester hat folgendes geschrieben :

Aber wie gesagt, man sollte (eigentlich muß) auch div/mod ganz verzichteten und auch auf die vielleicht praktische Zerlegung via Zehnerpotenzen. Alles was nicht via shift in mp_digits oder Zweierpotenzen realisiert wird, kann allenfalls didaktische Zwecke erfüllen.

Vielen Dank für den Hinweis. Ich werde alles auf Zweierpotenzen umbauen, div/mod rauswerfen und mal sehen, was dann noch geht.

Gammatester hat folgendes geschrieben :

Wenn Du wirklich eigene Routine machen willst, ...

Es geht nicht darum, Deine superschnellen Routinen übertreffen zu wollen; das kann ich gar nicht! Ich möchte es einfach nur verstehen und etwas lernen.

Beste Grüße und einen schönen Urlaub
Mathematiker

Bei mir steht das ja auch auf der Erledigungsliste, komme aber derzeit leider kaum zum Programmieren.

Mathematiker hat folgendes geschrieben :

Hallo Gammatester, Gammatester hat folgendes geschrieben : Aber wie gesagt, man sollte (eigentlich muß) auch div/mod ganz verzichteten und auch auf die vielleicht praktische Zerlegung via Zehnerpotenzen. Alles was nicht via shift in mp_digits oder Zweierpotenzen realisiert wird, kann allenfalls didaktische Zwecke erfüllen. Vielen Dank für den Hinweis. Ich werde alles auf Zweierpotenzen umbauen, div/mod rauswerfen und mal sehen, was dann noch geht.

Ich weiß nicht, ob Zweierpotenzen vorteilhaft ist. Zunächst einmal ist mir jede Zahlenumwandlung in ein anderes Basissystem suspekt: Ist das nicht per se schon arg geschwindigkeitsmindernd? Und dann ausgerechnet auch noch in das Zweier-/Binär-/Dualsystem: Das erzeugt die längsten aller möglichen Zahlen! Binärshifts werden natürlich für Binärzahlen, die in die Prozessorregister passen, blitzschnell ausgeführt, hier geht es jedoch um Riesenzahlen.

Hallo,
ich habe heute nachmittag intensiv Gammatesters Hinweise getestet, mit dem Ergebnis, dass praktisch seine eigenen Routinen entstehen, wie zu erwarten.
Da das mp_int-Format die Zahlen binär/hexadezimal ablegt, ist die Umwandlung in das Dualsystem nicht nötig und das Aufsplitten der Ausgangszahlen sowie die Endkonstrukton des Ergebnisses können durch Bitverschiebung sehr schnell ablaufen. Schneller, als in MP_Arith, wird es wohl nicht gehen.
Obwohl die Theorie aussagt, dass rekursive Anwendung beider Algorithmen besonders schnell ist, geht es mit MP_Arith nicht schneller, d.h. Rekursion ist hier nicht günstig.

Damit ist aber mein eigener Versuch erst einmal zu Ende.
Danke nochmals für die Hinweise.

Beste Grüße
Mathematiker

Mathematiker hat folgendes geschrieben :

Obwohl die Theorie aussagt, dass rekursive Anwendung beider Algorithmen besonders schnell ist, geht es mit MP_Arith nicht schneller, d.h. Rekursion ist hier nicht günstig.

Hallo Mathematiker,

bin mal wieder für ein paar Minuten online. Falls es noch interessiert:

Selbstverständlich benutzt MPArith sowohl Toom-3 als auch Karatsuba rekursiv, und zwar immer, dann wenn der kleinere der beiden Faktoren die vordefinierten Schwellen (in mp_types) überschreitet, mit 31/32-Bit Delphi5+ also standardmäßig bei Toom-3 > 32*31 = 992 Bit und bei Karatsuba 16*31 = 496 Bit. Die Entscheidung wird in der mp_mul-Routine getroffen.

Vielleicht hat Dich der Umstand getäuscht, daß s_mp_toom3_mul bzw. s_mp_karatsuba_mul sich nicht direkt selbst aufrufen. Die Rekursion verläuft über die mp_mul Aurufe dort. Das bedeutet: Wenn die Zahlen groß genug sind werden bei einen Aufruf von mp_mul aus Deinem Programm zuerst rekursiv s_mp_toom3_mul benutzt bis die Länge unter die Toom3-Schwelle fällt, dann rekursiv s_mp_karatsuba_mul bis zur Karatsuba-Schwelle, dann nicht rekursiv s_mp_mul_digs.

Einschub: Diese Beschreibung gilt, wenn die Faktoren ungefähr gleich groß sind; Stichwort 'balanced multiplication', Zitat aus R.P. Brent, P. Zimmermann: Modern Computer Arithmetic: The subquadratic algorithms considered so far (Karatsuba and Toom–Cook) work with equal-size operands. How do we efficiently multiply integers of different sizes with a subquadratic algorithm? This case is important in practice, but is rarely considered in the literature. In diesem Fall arbeitet MPArith blockweise und die Beschreibung gilt für die einzelnen Blocks.

Selbst Deine selbstgeschriebene Karatsuba-Routine verwendet deshalb zB s_mp_toom3_mul wenn die Zahlen groß genug sind: Da allerdings die erste Zahl in Deinem (veröffentlichten) Code viel zu klein ist für Karatsuba/Toom-3 tritt dieser Fall dort nicht ein, aber wenn zB jeweils anz:=random(250)+1000 gesetzt wird. Falls

Wenn man diese Effekte vermeiden will, muß man alle Cutoffs auf große Werte setzen, bei Dir beispielsweise am Anfang von TForm1.Button1Click

Gruß Gammatester