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