Schriftliche Multiplikation:
Erst mal ein Beispiel:
1234 * 567
-----------
6170
7404
8638
-----------
699678
Dann der allgemeine Fall:
Algorithmus für die Multiplikation zweier "langer" Zahlen
Sei der erste Faktor eine Zahl a mit der Ziffernfolge (ak, ak-1, ak-2, ...., a1, a0)
und der zweite Faktor eine Zahl b mit der Ziffernfolge (bn, bn-1, ...., b1, b0).
Dann erhält man das Produkt a*b, indem man folgendermaßen vorgeht:
Es seien s und p zwei (lange) Hilfszahlen, i ein Index.
Berechne das Produkt aus a und der Ziffer b[n] und lege es in s ab.
Setze i auf n-1.
Solange i >= 0 ist wiederhole
{
Multipliziere a mit der Ziffer b[i] und lege das Ergebnis in p ab.
Verschiebe s um eine Stelle nach links.
Addiere p zu s.
Vermindere i um 1.
}
Das Ergebnis der Multiplikation steht nun in s.
Bemerkungen:
- Die erste "neue" Operation ist die Multiplikation einer langen Zahl mit einer 1-stelligen Zahl ("Ziffer").
- Die zweite "neue" Operation ist die Verschiebung einer Zahl um eine (oder mehrere) Stellen nach links.
- Die Formulierung dieses Algorithmus ist noch nicht maximal elegant, es gibt (wie immer) Alternativen. Man kann ihn z.B. noch kompakter formulieren, indem man eine Schleife mit Abbruchbedingung am Ende benutzt, muss dann aber andere Initialisierungen vornehmen.
- Beachten Sie, dass der Algorithmus wörtlich genau so für alle möglichen Stellenwert-Systeme gilt, also z.B. auch für das Zweier-System oder das 16er-System oder sonst eines!
1. Hilfsprozedur:
Algorithmus für die Multiplikation einer "langen" Zahl mit einer Ziffer
Es ist nun noch zu klären, wie man eine Zahl a mit einer Ziffer z multipliziert.
Es habe a wie oben die Ziffernfolge (ak, ak-1, ak-2, ...., a1, a0).
Dann berechnet man a*z folgendermaßen:
Es seien s eine (lange) Hilfszahl,
p eine 2-stellige Hilfszahl mit den Ziffern p1 und p0,
sowie ü eine einstellige Hilfszahl und i ein Index.
Setze i auf 0.
Setze s auf 0.
Setze ü auf 0.
Solange i <= k ist wiederhole
{
Multipliziere ai mit z und lege das Ergebnis in p ab.
Addiere ü zu p.
Setze si auf den Wert von p0.
Setze ü auf den Wert von p1.
Erhöhe i um 1.
}
Setze sk+1 auf den Wert von ü.
Das Ergebnis der Multiplikation steht nun in s.
Bemerkungen:
- Beachten Sie, dass alle Operationen dieses Algorithmus "elementar" sind: wer das "kleine Einmaleins" seines gewählten Stellenwertsystems beherrscht, kann diesen Algorithmus ausführen.
- Den Puffer s kann man sich ersparen, wenn man das Ergebnis gleich wieder nach a zurückschreibt. Allerdings verschleiert das den Algorithmus ein wenig.
2. Hilfsprozedur:
Verschiebung einer "langen Zahl" um n Stellen nach links
Schließlich brauchen wir noch die Verschiebung einer Zahl a mit der Ziffernfolge (ak, ak-1, ak-2, ...., a1, a0) um n Stellen nach links. Das ist allerdings ganz einfach:
Es sei i ein Index.
Setze i auf k.
Solange i >= 0 ist wiederhole
{
Setze ai+n auf den Wert von ai.
Vermindere i um 1.
}
Setze i auf n-1.
Solange i >= 0 ist wiederhole
{
Setze ai auf 0.
Vermindere i um 1.
}
Bemerkungen:
- Beachten Sie die zweite Schleife! Sie sichert, dass in den neu hinzugekommenen Stellen nur Nullen stehen. Das ist wichtig!
Roland Mechling, 10.02.2005