PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Der Algorithmus bei Wikipedia ist falsch!


Gast
2009-05-23, 02:42:29
http://de.wikipedia.org/wiki/Karatsuba-Algorithmus
Unten ist ein JAVA-Beispiel. Der Code ist mit 100 % W'keit falsch.

int n = Math.max (x.bitLength(), y.bitLength());
if (n <= 1500) return x.multiply (y);


Der Abschnitt kommt ja bei langen Zahlen garnicht zum Zug. Der Algorithmus terminiert niemals und die xH und xL werden total klein. Da hat wohl jemand Unsinn fabriziert oder irre ich mich da?

Spasstiger
2009-05-23, 02:53:19
Der Abschnitt kommt ja bei langen Zahlen garnicht zum Zug.
Richtig, so steht es auch im Kommentar des Quelltextes.

Der Algorithmus terminiert niemals und die xH und xL werden total klein. Da hat wohl jemand Unsinn fabriziert oder irre ich mich da?
Der Algorithmus ruft sich bei großen Zahlen rekursiv selbst auf, bei kleinen Zahlen aber entfällt der rekursive Aufruf und es wird direkt das Ergebniss der Multiplikation zurückgegeben. Da die Zahlen mit jedem Rekursionsschritt kleiner werden, ist in jedem Fall irgendwann der Punkt erreicht, an dem der von dir gepostete Abschnitt des Codes greift und kein weiterer Rekursionsschritt mehr erfolgt. Dieser Abschnitt enthält also die Abbruchbedingung.

Gast
2009-05-23, 04:01:17
Ich frage mich aber gerade wie man bei der Abbruchbedinungen: if (n <= 1500)
die Grenze (1500) wählen muss. Darf die auch kleiner sein. Das hat ja mehr Rekursionen zu Folge. Ist das gut?! Das kostet doch unnötig Laufzeit.

Was würde man darunter verstehen:
k-Stufiger rekursiver Karatsuba Algorithmus für 2^k stellige Zahlen x und y?

Ist nun k die Schranke oder was? Ich habe das ganze mal in PHP nachprogrammiert, weil C die ganze Zeit Stress mit Integeroverflow macht, wenn ich 6 stellige Zahle multiplizieren will.

Gast
2009-05-23, 04:43:55
Ach... 2^k sagt nur aus, dass ich 0 2 4 8 16 ..n 2^k stellige Zahlen multipliziere. D.h dass ich 6 stellige, obwohl die Anzahl auch gerade ist, per Definition ausschließe...

Und das ist die eben die Grenze für Abbruchbedingung!

Spasstiger
2009-05-23, 11:38:18
Ich frage mich aber gerade wie man bei der Abbruchbedinungen: if (n <= 1500)
die Grenze (1500) wählen muss. Darf die auch kleiner sein. Das hat ja mehr Rekursionen zu Folge. Ist das gut?! Das kostet doch unnötig Laufzeit.
Die Methode BigInteger.multiply, die bei Gültigkeit der Abbruchbedingung verwendet wird, braucht auch Laufzeit.
Man muss halt die Anzahl von Binärstellen finden, bei der x.multiply(y) gerade schneller ist als karatsuba(x,y).

Und natürlich kannst du auch (binär) 6-stellige Zahlen mit karatsuba multiplizieren, du musst sie dann halt als (binär) 8-stellige Zahlen mit vorangestellten Nullen interpretieren und dein n entsprechend anpassen.
n=2^k Stellen kommt übrigens auch nur daher, dass der gezeigte Java-Code auf binär interpretierten Zahlen arbeitet. Grundsätzlich kannst du auch dezimal arbeiten, dann musst du halt um n Dezimalstellen verschieben, d.h. durch 10^n teilen oder mit 10^n multiplizieren.

Berni
2009-05-23, 14:07:47
Ist nun k die Schranke oder was? Ich habe das ganze mal in PHP nachprogrammiert, weil C die ganze Zeit Stress mit Integeroverflow macht, wenn ich 6 stellige Zahle multiplizieren will.
Integeroverflow heißt ja, dass du über die Grenze des Integers beim Rechnen kommst. Dementsprechend könntest du mal long anstatt int probieren.
Achtung bei PHP: Wenn du dort mit einer Berechnung aus dem Integerbereich rauskommst, wird automatisch in ein float umgewandelt (vgl. http://de.php.net/integer "Integer overflow")! Dementsprechend kann dann aber die Genauigkeit bei Berechnungen (oder auch der Umwandlung ins float) leiden! Um wirklich große Zahlen in PHP zu nutzen musst du die BCMath-Bibliothek nutzen: http://de2.php.net/manual/de/ref.bc.php allerdings sind Berechnungen damit naturgemäß langsamer.

Tiamat
2009-05-24, 22:44:51
Nö der Algorithmus ist nicht falsch, wird ja im Kommentar explizit angegeben. Spasstiger hat das oben sehr gut erläutert.
In C lässt sich der Algorithmus nicht so wirklich einsetzen, da es kein BigInteger dort gibt. Mit Long hat man natürlich mehr Spielraum, klar :=)