Eigentlich glaubt man, schon in der Grundschule alles über Grundrechenarten (addieren, subtrahieren, multiplizieren, dividieren) gelernt zu haben. Aber es gibt da immer noch Überraschungen. Hier drei Methoden zum schriftlichen Multiplizieren von zwei ganzen Zahlen:

  • Das klassische Malnehmen des Musterschülers

    • Schriftliches Multiplizieren zweier Zahlen, Berechnung des Produkts zweier Zahlen


  • Die Faulenzermethode (oder russische Bauernregel)
    •  
    Der Faulenzer beherrscht nur die Multiplikation mit 2 und die Division durch 2.

    Wie man zwei Zahlen mit der russischen Bauernregel multiplizieren

    Anleitung: In der linken Spalte immer halbieren und bei Bedarf nach unten abrunden. Rechts immer verdoppeln. Danach alle Zeilen streichen, die mit einer geraden Zahl anfangen (schwarz). Die übrigen Zeilen rechts addieren (rot).
     
     
  • Methode von Karatsuba (1962 veröffentlicht)

    • Man trenne jeden Faktor in zwei gleich lange Teile
    Multiplikation mit dem Algorithmus von Anatolii Karatsuba, Karatsuba Algorhythmus
    und berechne die folgenden Teilprodukte:
    Karatsuba Multiplikation
    Das Endergebnis erhält man dann so:
    Multiplizieren lernen
Bemerkung
Hinter all dem steckt die Idee, das Multiplizieren auf Produkte von einstelligen Zahlen, also das Einmaleins, zurückzuführen. Auf einem Computer kann die Wahl eines guten Algorithmus die Rechenzeiten erheblich verkürzen — und zwar um einige Tage, wenn es sich um Zahlen mit mehreren Milliarden Stellen handelt! Und das Rechnen mit sehr hohen Zahlen beschäftigt nicht nur Theoretiker, sondern wird auch von Praktikern wie Kryptologen angewendet.
 
Übungsaufgabe
  1. Erkläre, warum die Faulenzermethode funktioniert. Die beiden Faktoren spielen offenbar entgegengesetzte Rollen; welcher sollte am besten welche Rolle übernehmen?
  2. Mithilfe der Karatsuba-Multiplikation berechne man das Produkt 3116 x 1014. Erkläre, warum die Karatsuba-Methode funktioniert.
  3. Wieviele Produkte von einstelligen Zahlen berechnet man beim klassischen Malnehmen, wenn man zwei n-stellige Zahlen multipliziert?
  4. Indem man die Methode von Karatsuba wiederholt (also die Zahlen in zwei, vier, acht, etc. Teile aufspaltet) erhält man einen Algorithmus, den sog. Karatsuba-Algorithmus. Wieviele Produkte von einstelligen Zahlen muss man dabei berechnen, wenn man zwei n-stellige Zahlen multipliziert? Man vergleiche den klassischen Algorithmus mit dem von Karastuba und zeige insbesondere, dass der Algorithmus von Karatsuba eine Laufzeitkomplexität von ungefähr O\left(n^{1,58}\right) hat.
Lösung
Hier sind die Lösungen dieser Übungsaufgaben im pdf-Format.

Zuguterletzt ein Video mit einer anderen Multiplikationsmethode, die nebenbei eine nette Kalligrafie erzeugt — deshalb heisst sie chinesische Multiplikation!

Die Grundidee der chinesischen Multiplikationsmethode ist folgende Tatsache: ein Bündel von n parallelen Geraden schneidet ein anderes Bündel von m parallelen Geraden in genau nxm Punkten.