Langzahlarithmeik

[eF-eS]

Hallo,

ich wollte mal fragen, ob von Euch einer schon mal den Karatsuba-Algo (Multiplikation von Langzahlen) gecodet hat und mir den Quelltext zur Einicht mailen könnte.

Vielen Dank!

lg F

[nailor]

findet zwar nix in delphi, aber vllt dennoch interessant für dich (und auch allgemein sehr interessant, die seite): http://koders.com/?s=Karatsuba&_%3Ab...Ala=*&_%3Ali=*

[negaH]

Ja ich habe Karatsuba gecodet in ganz verschiedenen Algorithmen.
Karatsuba ist nur eine spezielle Form eines allgemeineren Verfahrens, dem "Divide & Conquer" -> Teile und Herrsche Verfahren. Karatsuba teilt dabei immer in 2 Hälten um diese dann rekursiv wiederum zu teilen bis hinunter auf einen gewählten Breakeven Point ab dem mit einem einfacheren Verfahren zb. multipliziert wird.
Höherwertige Verfahren der gleichen Methode sind zb. die Toom-Cook Abkömmlinge. Diese teilen das Problem in 3,5,7,9 Hälten auf. Mit Karatsuba muß man nicht nur Multiplizieren sondern es gibt auch Karatsuba Verfahren für die Division oder Wurzelziehen.

Ich persönlich habe in meinem DECMath folgende Karatsubalike Verfahren implementiert
- Karatsuba Multiplikation
- Karatsuba Quadrierung
- Karatsuba Quadrat-Wurzel nach P. Zimmerman
- Karatsuba Division nach Burnickel & Ziegler
- Toom-Cook-3 Multiplikation


DECMath findest du hier in der DP für Delphi 5,6,7 als binäre Distributation.

Suchst du Sourcen so wirst du für Delphi/PASCAL nur wenig fündig werden. Du solltest C/C++ lesen können dann kannst du dir ApFloat, Gimp, GMP, LiDIA usw. anschauen.

Gruß Hagen

[eF-eS]

Zitat von negaH:

Suchst du Sourcen so wirst du für Delphi/PASCAL nur wenig fündig werden. Du solltest C/C++ lesen können dann kannst du dir ApFloat, Gimp, GMP, LiDIA usw. anschauen.

Yüp, Hagen, das habe ich gestern beim googlen auch gemerkt.

Alles klar, werde mich hier mal noch schlau machen.

Wie kann ich diesen Thread schließen?

[TeronG]

Zitat von negaH:

teilen das Problem in 3,5,7,9 Hälten

[klugscheiß] 9 Hälfen nicht eher 9 Teile
einer der wenigen Hagen-Post's die ich komplette verstehe und dann sogar nen Fehler finde!!

[negaH]

@TeronG:

Ja, 9 Teile da haste Recht
Allerdings sind alle Karatsuba-Verfahren rekursive Verfahren. Bevor man in die Rekursion tiefer geht wird X geteilt, dann rekursiv jeder dieser Teile wiederum geteilt und nach Rückkehr aus der Rekursion werden die Teilprodukte wieder zusammengesetzt. Bei diesem Teilen + Zusammensetzen ist es aber so das die korrekte Reihenfolge des Zusammensetzens sehr wichtig ist. Und deshalb sprach ich von Hälten da zb. die Teile No. 6+7+8 stufenweise zusammengesetzt werden müssen, man hat also für diesen Zwischenschritt des Zusammensetzens immer noch Linke und Rechte Hälften.

Gruß Hagen