Ich habe versucht, Karatsuba-Algorithmus in Java zu implementieren, ohne BigInteger zu verwenden. Mein Code ist nur anwendbar, wenn beide Ganzzahlen gleich sind & amp; haben die gleiche Anzahl von Ziffern. Ich bekomme nicht die richtige Antwort, aber ich bekomme Antwort, die ziemlich nah an der richtigen ist. Zum Beispiel bekomme ich 149 wenn 12 * 12. Ich kann nicht herausfinden, was mit meinem Code falsch ist, da ich glaube, dass ich alles richtig gemacht habe (im Buch). Hier ist mein Code.
%Vor%BEARBEITEN:
Dank Ziyao Wei war das Problem, "dritte" durch "zweite" zu ersetzen. Allerdings habe ich jetzt ein anderes Problem, nämlich:
Wenn Karatsuba (1234,5678) angerufen wird, bekomme ich die richtige Antwort, aber wenn ich Karatsuba (5678,1234) anrufe, bekomme ich nicht die richtige Antwort. Könnte irgendjemand den Grund dafür wissen? Mein aktualisierter Code ist:
%Vor%UPDATE:
Ich habe es geschafft, den Wert für "n / 2" aufzurunden, daher löst es das Problem, aber wenn Zahlen mit mehr als vier Ziffern verwendet werden, treten Fehler auf. Hier ist mein aktualisierter Code:
%Vor%Wenn jemand auf die Lösung für größere Zahlen (mehr als vier Ziffern) kommt, ohne BigInteger zu verwenden, lassen Sie es mich bitte wissen. Danke.
Der letzte Fehler ist, dass Runde (n) 2 * Runde (n / 2) sein sollte. Sie unterscheiden sich offensichtlich für ungerade n.
Betreffend int n=getCount(i); ist das eine Quelle der Dissymetrie, also sollte es geändert werden.
Zur Effizienz sollte es nicht durch max(getCount(i),getCount(j)) ersetzt werden, wie ich oben in einem Kommentar gelesen habe, sondern mit min .
In der Tat macht Karatsuba nur Sinn, wenn man gut ausgewogene Zahlen teilt
Versuchen und zerlegen Sie die durchgeführten Operationen mit max und min um sicher zu gehen ...
Endlich, nach mehreren Stunden des Nachdenkens habe ich die richtige Lösung gefunden:
%Vor%Ich kann nicht erklären, warum n nicht ungerade sein kann , aber im Moment funktioniert die Multiplikation für die vielen Tests, die ich geschrieben habe, richtig. Ich werde dieses Verhalten erklären, sobald ich es herausfinden werde.
Update: Ich nehme Algorhythms: Design and Analysis, Teil 1, Kurs zu Kursen, und habe eine Frage zu diesem Verhalten gestellt. Hier ist eine Antwort von Andrew Patton:
Wie bereits an anderer Stelle erwähnt, besteht der Schlüssel bei der Aufschlüsselung der Eingaben darin, sicherzustellen, dass b und d die gleiche Länge haben, so dass a und c die gleiche Potenz von 10 wie Koeffizienten haben. Was auch immer diese Macht ist, wird dein n / 2; ... Also ist der Wert von n in 10 ^ n nicht die Gesamtlänge Ihrer Eingaben, sondern eher n / 2 * 2.
Also im Falle einer 3-stelligen Nummer, die Ihrem Beispiel folgt:
%Vor%So sollte n in diesem Beispiel gleich n / 2 * 2 = 4 sein.
Hoffe, das macht Sinn.
Sie setzen i = a * B + b und j = c * B + d, wobei B = 10 ^ m und m = n / 2 ist. Dann
%Vor%Aber in der Hälfte der Fälle ist B ^ 2 = 10 ^ (2m) nicht gleich 10 ^ n, da für ungerade n man n = 2 * m + 1 hat, also in diesem Fall B ^ 2 = 10 ^ (n-1).
Ich würde also vorschlagen, einmal m = n / 2 oder besser m=(n+1)/2 , B=(long)Math.pow(10,m) zu definieren und daraus a, b, c, d zu berechnen und in der letzten Summe den Faktor B * B zu verwenden.
Anstatt mit Math.round () abzurunden, addiere ich 1 zum Wert der Eingabegröße (das Minimum der Anzahl der Ziffern in x oder y), wenn die Eingabegröße ungerade ist. Wenn beispielsweise X = 127 & amp; Y = 162, dann Eingabegröße ist 3. Inkrementieren Sie es um 1, um es zu machen 4. Dann, a = X / Math.pow (10, input_size / 2) = 1. b = X% Math.pow (10, input_size / 2) = 27. In ähnlicher Weise, c = 1 und d = 62. Wenn wir nun X * Y = (ac) * Math.pow (10, input_size) + (ad + bc) * Math.pow (10, input_size / 2) + bd; es gibt die richtige Antwort. Denken Sie daran, dass wir die Eingabegröße nur um 1 erhöhen, wenn sie ungerade ist. Die vollständige Implementierung ist hier - Ссылка
Tags und Links algorithm java math multiplication