Diskussion:Karazuba-Algorithmus

Biografie Karazuba und Transkription des Namens

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)

Das ist in der Zwischenzeit erledigt. Die korrekte deutsche Transkription des Namens erfolgt im Artikel zusammen mit der Korrektur zahlreicher Ungenauigkeiten. -- J1nders (Diskussion) 10:55, 22. Jan. 2014 (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.

Java und Rekursion

Wenn die Implementierung nicht auf Effizienz (sondern offensichtlich genau auf das Gegenteil) ausgelegt ist, warum steht sie dann hier? Vielleicht ist mal jemand mutig, entfernt und verbessert es.

20:22, 31. Jan. 2008 (CET)

Ich habe eine effiziente Implementierung geschrieben. Die ist allerdings mindestens 5 mal so lange. Die hier geschilderte Implementierung ist aber nur 30% (grob) langsamer.

Man muss nicht notwendiger Weise immer wieder neue Zahlen erzeugen, sondern kann immer auf der Zahlendarstellung arbeiten, da man ja immer Teilbereiche der Zahl(en) miteinander multipliziert. Dann wird es allerdings technisch aufwendig, da man die konkrete Zahlendarstellung offenlegen muss. Ich kann die Implementierung mal (hier in die Diskussion) reinstellen wenn du willst.--ThiloHarich 19:49, 2. Feb. 2008 (CET)

Die Implementierung in einer konkreten Sprache ist hier imho nutzlos! Die Angabe in Pseudo-Code ist wesentlich hilfreicher. Es geht hier schließlich auch nicht um die effizienteste Implementierung, sondern um die verständlichste Darstellung! Schon deshalb ist Pseudo-Code viel geeigneter. --Koethnig 22:04, 4. Feb. 2008 (CET)

Ich denke auch die Implementierung in Java ist von daher o.k. da sie beliebig lange Zahlen unterstützt, und die Implentierung trotzdem den Kern des Algorithmus wiedergibt. Vielleicht hätte ich das mit der Effizienz weglassen sollen.

Ich hab das mit der Effizienz im Artikel weggelassen. Verwirrt vermutlich nur. Ist ja bis auf einen konstanten Faktor effizient.--ThiloHarich 22:24, 4. Feb. 2008 (CET)

Das Java-Programm wurde gelöscht, weil es Programmierkenntnisse voraussetzt und weil es nicht mehr Einblick vermittelt als die Formeln im Artikelabschnitt Der Algorithmus im Detail. -- J1nders (Diskussion) 10:55, 22. Jan. 2014 (CET)

Beispiel

Ich würde das Beispiel auf zweistellige (dezimal) Zahlen beschränken. Im englisch Artikel werden auch kürzere Zahlen verwedet. Da kann man leichter nachvollziehen was gemeint ist. Da das dann eh rekursiv weiterläuft machen lange Zahlen auch wenig Sinn. Die verwirren nur, oder?--ThiloHarich 22:40, 4. Feb. 2008 (CET)

Vierstellig wäre schon besser, damit der rekursive Charakter des Algorithmus deutlich wird.--LutzL 10:03, 6. Feb. 2008 (CET)

Veraltete Aussage

"und der aus Sicht der Komplexitätstheorie als schnellster bekannter Algorithmus zur Multiplikation ganzer Zahlen gilt" bezieht sich hier auf den Schönhage-Strassenalgorithmus. Es gibt aber einen weit aus besseren seit 2007. --84.150.129.36 01:37, 25. Jun. 2009 (CEST)

Bitte neue Diskussionen unten anhängen. Theoretisch schneller war schon der Schönhage-Algorithmus von 1982, der aber praktisch nicht verwendet wurde. Wie ich schon bei Toom-Cook schrieb, die Arbeit von Fürer (2007) ist auf der Seite des Schönhage-Strassen-Algorithmus verlinkt. Ist der Algorithmus schon z.B. in gmp implementiert? Welchen Crossover-Point hat er zu den anderen Algorithmen?--LutzL 09:16, 15. Jun. 2009 (CEST)

Der Link im Lemma Schönhage-Strassen-Algorithmus ist nicht mehr aktuell. Im Vorspann dieses Artikels wurde ein Link auf das englische Lemma Fürer's algorithm hergestellt. -- J1nders (Diskussion) 10:55, 22. Jan. 2014 (CET)

anmerkung

Ip schrieb: "…

$P_{3}=$$\!(X_{h}+X_{l})\cdot (Y_{h}+Y_{l})=({\color {Blue}084\,232}+{\color {OliveGreen}332\,233})\cdot ({\color {Red}001\,532}+{\color {Brown}664\,392})=416\,465\ \cdot \ 665\,924=277\,334\,038\,660.$

[Anm. bs 2021-02-09: wäre es nicht einfacher hier Xh*Yl + Xl*Yh zu nehmen und sich das Abziehen von (P1+P2) in der übernächsten Zeile zu sparen?]" hier--ot (Diskussion) 04:55, 9. Feb. 2021 (CET)

Abschnitt „Der Algorithmus im Detail“

Hier wird zunächst von einem Stellenwertsystem zur Basis $b$ gesprochen, danach heißt es für einen Computer mit 32 Bit Wortlänge sei $b=2^{31}$. Das ist kein Widerspruch, mir scheint aber, hier sei etwas anderes gemeint. Wenn ich nämlich den Text z. B. auf das Problem $23_{10}\cdot 994_{10}$ anwende, dann ist dieses Problem „zu klein“, um jede der beiden Zahlen 23 und 994 zu zerlegen, weil sie im System der – sehr großen – Basis $b=2^{31}$ einstellig sind. Der Vorteil des Algorithmus käme also erst bei Zahlen $>2^{31}$ zum Tragen. Anders sähe es aus, wenn diese ins Zweiersystem ($b=2$) umgeschrieben würden, denn dann hätten sie 5 bzw. 10 Binärstellen (10111 und 1111100010). Verwirrend ist auch die Behauptung, bei 32 Bit Wortlänge sei $b=2^{31}$. Dies trifft ja bloß zu, wenn ein Bit nicht oder als Vorzeichenbit benutzt wird. Ich meine, hier gäbe es Klärungsbedarf. --Joachim Schnitter (Diskussion) 16:44, 15. Sep. 2021 (CEST)