Diskussion:Karazuba-Algorithmus

Biografie Karatsuba fehlt noch, Link evtl. nicht exakt

Achtung, die Schreibweise des vollständigen (verlinkten) Namens von Karatsuba entspricht möglicherweise nicht den Konventionen hier. Wer sich damit auskennt, möge diese bitte korrigieren. --Coma 09:42, 21. Nov 2005 (CET)

Zu Implementierung und Laufzeitanalyse

$P_{3}=(x_{h}+x_{l})\cdot (y_{h}+y_{l})$ Was ist, wenn $x_{h}$ und $x_{l}$ beide ihren maximalen Wert haben, dann ist die Summe nicht mehr mit n Stellen darstellbar, oder doch?

Das muss natürlich in einer Implementierung beachtet werden, in der Laufzeitanalyse ist das im Term O(n) enthalten. Zwei Zahlen der Länge 2n ergeben in der Summe der Hälften Zahlen der Länge n+1 und in deren Produkt eine Zahl der Länge 2(n+1).--LutzL 14:46, 1. Dez. 2006 (CET)

Warum stimmt dann folgender Satz: "Eine Multiplikation zweier n-stelliger Zahlen wird zurückgeführt auf drei Multiplikationen von je zwei n / 2-stelligen Zahlen". Es sind doch 2 Multiplikation mit n/2 Stellen und 1 Multiplikation mit (n+1)/2 Stellen. Und daraus folgend, warum ist dann T(n) = 3 T(n/2) + ... .

Stimmt, das war mir gar nicht aufgefallen. Aber man kann sich vermutlich so aus der Affäre ziehen (hat LutzL vielleicht auch schon gemeint): Die Multiplikation zweier $k+1$-stelliger Zahlen kann man zurückführen auf die zweier $k$-stelliger plus Zusatzaufwand $O(k)$ (jeweils letzte Ziffer abspalten). Deshalb können wir in der Rekursionsgleichung anstatt 2 Multiplikationen $n/2$-stelliger Zahlen und 1 Multiplikation $(n+1)/2$-stelliger Zahlen auch vereinfacht 3 Multiplikationen $n/2$-stelliger Zahlen annehmen. --Infimum 17:30, 6. Dez. 2006 (CET)

Dieser Spezialfall ist in einer Bemerkung des Master-Theorems abgehandelt.