Um das Produkt von 127 und 128 zu berechnen, wählen wir Basis B = 10 und m = 2, das heißt wir zerlegen den Input mit Hilfe der resultiertenden Basis B^m = 100:
127 = 1·100 + 27
128 = 1·100 + 28
Jetzt werden nur 3 Multiplikationen mit kleineren Zahlen benötigt, um die Teilergebnisse zu berechnen:
z_{2} = 1·1 = 1
z_{0} = 27 · 28 = 756
z_{1} = (1 + 27) · (1 + 28) − z_{2} − z_{0} = 28 · 29 − 1 − 756 = 812 − 757 = 55
Jetzt fügen wir diese Teilergebnisse zusammen und shiften die Werte:
Resultat = z_{2} · (B^m)^2 + z_{1} · (B^m)^1 + z_{0} · (B^m)^0
Resultat = 1 · (10^2)^2 + 55 · (10^2)^1 + 756 · (10^2)^0 = 1·10000 + 5500 + 756 = 16256
Das Ergebnis von 127 · 128 ist 16256.
Ein weiteres Beispiel (12345 · 6789) ist auf der englischen Wikipedia zu finden.
Auch wenn es aufwändig aussieht, so ist die Berechnung mittels Computer schneller (n^{log₂3} ≈ n^{1,585}) als klassische Algorithmen mit einer Laufzeit von n^2.
Hier ist der notwendige Code in Javascript, dort kannst du für x und y eigene Werte eintragen:
https://jsfiddle.net/kai_noack/47tmbagx/11/
