Guter Algorithmus zum multiplizieren großer Zahlen gesucht

[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