+1 Daumen
597 Aufrufe

Ich habe mir jetzt schon mehrere Seiten durchgelese, um zu verstehen, wie man mit der Methode von Karazuba rechnet, aber irgendwie steh ich bei der Rechnung komplett auf dem Schlauch.

Multiplizieren von 127 und 128 mittels der Methode von Karazuba. Gehe davon aus, dass die Rückgabewerte aus der (ersten) Rekursion bekannt sind.

von

1 Antwort

0 Daumen

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:


von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community