1. Multiplikation durch Addition
2. Binäre Multiplikation
3. Parallele Multiplikation
4. Karatsuba-Multiplikation
Auch scheinbar einfache Algorithmen lassen sich oft noch optimieren.
In dieser Präsentation untersuchen wir, ob die aus der Schule bekannte
schriftliche Multiplikation noch Verbesserungspotenzial hat.
Falls Sie sich noch an das schriftliche Rechnen in der Schule erinnern oder jemals in die Verlegenheit kamen, nur mit Bleistift und Papier eine größere Multiplikation durchzuführen, werden Sie sich erinnern, dass Multiplizieren viel aufwendiger ist als Addieren. Woran liegt das?
Nehmen Wir einmal an, Sie können das kleine Einmaleins auswendig
und damit zwei einstellige Zahlen ebenso schnell multiplizieren wie addieren.
Nun probieren Sie bitte einmal, zwei vierstellige Zahlen schriftlich
zu addieren und zu multiplizieren.
Sieht Ihr Zettel etwa so aus:
1234 1234·5678 +5678 ───────── ──── 9872 6912 8638 7404 6170 ───────── 7006652
Wie verhält sich die Rechenzeit zur Größe der Zahlen beim schriftlichen Multiplizieren?
Wir haben jede Ziffer des linken Faktors
mit jeder Ziffer des rechten Faktors multipliziert.
Im Beispiel haben wir 4·4 = 16 Einzelmultiplikationen durchgeführt.
Für das Produkt zweier n-stelliger Zahlen brauchen wir also n²
einzelne Multiplikationen. Dazu kommt noch das Aufaddieren am Ende, das aber
am gesamten Rechenaufwand bei großen Zahlen kaum eine Rolle spielt.
Die Zeit ist demnach proportional zum Produkt der Längen beider Zahlen.
Zum Vergleich: Beim schriftlichen Addieren zweier n-stelliger Zahlen
braucht man nur n Additionen von einzelnen Ziffern (und maximal noch einmal
so viele Additionen für die Überträge).
Die Rechenzeit steigt hier also nur linear mit n an!
Die relative Einfachheit der Addition schlägt sich auch in der Geschichte
der mechanischen Rechenmaschinen nieder. Bevor in den siebziger Jahren des
20. Jahrhunderts der Taschenrechner seinen Siegeszug antrat, waren preiswerte
mechanische Additionshilfen weit verbreitet, während Maschinen,
die auch multiplizieren konnten, sehr teuer und langsam waren.
Das nebenstehende Bild zeigt meine erste, vom Taschengeld erworbene
Rechenmaschine.
Das Geheimnis dieser Addiatoren war eine Doppelzahnstange (links im Bild blau eingezeichnet), in die ein Stift gesteckt wurde, um die Ziffern zu verschieben. Um z.B. im linken Bild 30 zu addieren, steckt man den Stift in das mit 3 markierte Loch der hervorgehobenen Zehnerstange und zieht in bis zum unteren Ende. Wenn wir aber z.B. 70 addieren möchten, ist das entsprechende Loch rot markiert. Das bedeutet, dass wir nicht nach unten schieben (sonst kämen wir aus dem erlaubten Ziffernbereich heraus, sondern nach oben. Statt 70 zu addieren, subtrahieren wir also 30 (=100-70) und müssen den Fehler korrigieren, indem wir anschließend 100 addieren. Das geht aber in einem Rutsch, indem man oben einfach dem umgebogenen Weg folgt!
Wegen der Unerschwinglichkeit von Multiplikationsmaschinen hat man sich früher beholfen, indem man die Multiplikation mit Hilfe von Logarithmen auf die Addition zurückgeführt hat.
Die folgende Abbildung zeigt das Prinzip:Statt die Multiplikation x·y direkt durchzuführen, berechnet man die Logarithmen von x und y, addiert diese und wendet auf die Summe die Umkehrfunktion (Exponentialfunktion) an, um das Ergebnis zu erhalten.
In der Praxis wurden deshalb
Logarithmentafeln
zur Basis 10 gedruckt.
Hier sehen Sie einen Auszug aus einer vierstelligen Logarithmentafel:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|
300 | 4771 | 4773 | 4774 | 4776 | 4777 | 4778 | 4780 | 4781 | 4783 | 4784 |
301 | 4786 | 4787 | 4789 | 4790 | 4791 | 4793 | 4794 | 4796 | 4797 | 4799 |
302 | 4800 | 4802 | 4803 | 4804 | 4806 | 4807 | 4809 | 4810 | 4812 | 4813 |
303 | 4814 | 4816 | 4817 | 4819 | 4820 | 4822 | 4823 | 4824 | 4826 | 4827 |
304 | 4829 | 4830 | 4832 | 4833 | 4834 | 4836 | 4837 | 4839 | 4840 | 4842 |
305 | 4843 | 4844 | 4846 | 4847 | 4849 | 4850 | 4852 | 4853 | 4854 | 4856 |
306 | 4857 | 4859 | 4860 | 4861 | 4863 | 4864 | 4866 | 4867 | 4869 | 4870 |
307 | 4871 | 4873 | 4874 | 4876 | 4877 | 4878 | 4880 | 4881 | 4883 | 4884 |
308 | 4886 | 4887 | 4888 | 4890 | 4891 | 4893 | 4894 | 4895 | 4897 | 4898 |
309 | 4900 | 4901 | 4902 | 4904 | 4905 | 4907 | 4908 | 4909 | 4911 | 4912 |