Die Geheimnisse des Multiplizierens

[Mondkalb]

Wer hätte gedacht, dass sich das Vorgehen bei der Multiplikation zweier Zahlen noch verbessern lässt?
Mathematik: Das Malnehmen zweier Zahlen lässt sich verbessern. | Nachrichten auf ZEIT ONLINE

[irony]

Wer hätte gedacht, dass sich das Vorgehen bei der Multiplikation zweier Zahlen noch verbessern lässt?
Mathematik: Das Malnehmen zweier Zahlen lässt sich verbessern. | Nachrichten auf ZEIT ONLINE

Ist schon irgendwie interessant (na ja, nicht wirklich ), aber ich habe mir zumindest mal den Karatsuba-Algorithmus - Wikipedia angeschaut.

Wenn ich es richtig verstehe, schneidet man zwei 2n-stellige Zahlen x und y in der Mitte durch und kriegt

x = A1 * 10^n + A2 und y = B1 10^n + B2

wobei A1 aus den ersten n Ziffen und A2 aus den letzten n Ziffern von x gebildet wird usw.

Also z.B. x = 4896 = 48 * 100 + 96

Dann multipliziert man folgende Klammern

x y

= (A1 * 10^n + A2) ( B1 * 10^n + B2 )

= A1*B2 10^2n + ( A1 B2 + A2 B1 ) 10^n + A2 B2

D.h man multpliziert jetzt nur noch n-stellige Zahlen (A1, A2, usw) miteinander, was wohl deutlich günstiger ist wenn n richtig groß ist. Erstaunlich ist, dass diese einfache Methode erst 1960 von Karatsuba publiziert worden sein soll .

Mehr als das Distributivgesetz steckt doch da kaum drin.

Wie die anderen noch fortgeschritterenen Verfahren funktionieren, lasse ich mir lieber von jemand anders erklären .

[Cordess]

Viel eher würde mich interessieren, ab wievielen Stellen der zu multiplizierenden Zahlen werden diese Verfahren eingesetzt bzw. macht es Sinn diese am Computer einzusetzen.
Insbesondere im Hinblick darauf, daß moderne Computer Multiplikationseinheiten in Hardware enthalten um Multiplikationsberechnungen mit einer begrenzten Genauigkeit schnell durchzuführen.

Bei großen aber noch hinreichend kleinen Zahlen könnte eine Softwarelösung der oben genannten schnellen Verfahren also in der Praxis an einem Computer dennoch langsamer sein als die in Hardware gegossene Multiplikationseinheit des Computers.

Mit SSE2 kann man z.B. Gleitkommazahlen mit doppelter Genauigkeit (64 Bit Präzision) in AFAIK ca. 1-3 Schritten multiplizieren. Für MMX gibt es ähnliches in Ganzzahlgenauigkeit und 64 Bit Genauigkeit in 3 CPU Zyklen.


Damit obige Verfahren also in der Praxis für den Anwendungsbereich des normalen Users etwas bringen, braucht man schon sehr große Zahlen, ich würde mal sagen mindestens > 2^64 oder eben solche Werte, bei denen der Genaugikeitsbereich der SSE* bzw. MMX Hardwareeinheiten nicht mehr ausreicht.