Karatsuba-Verfahren implementieren?!

[Ivexx]

Hi!

Ich brauch mal etwas Hilfe. Undzwar bei dem Karatsuba-Verfahren. Ich muss eine TBigInteger.mult-Prozedur durch eine Methode ersetzen, die die Multiplikation gemäß dem Karatsuba-Verfahren implementiert. Kann mir hierbei jmd. weiterhelfen?

Mit freundlichen Grüßen

[marabu]

Hallo,

was ist denn konkret dein Problem? Wie sieht die TBigNumber-Klasse aus?

Grüße vom marabu

[leddl]

Wo genau hängst du?
Wenn ich mir den Algorithmus so anschaue, sieht der auf den ersten Blick nicht sonderlich kompliziert aus...

Du teilst die Zifferfolgen in 2 gleich große Teile (mit führender 0 bei ungerader Zifferanzahl) und hast dann am Schluss eine Formel zur Berechnung des Produktes durch diese "Teilzahlen".
Diese Berechnung geht eben rekursiv immer eine Ebene tiefer, bis du nur noch 1 Ziffer multiplizieren musst.

[Dutch_OnE]

Hallo Leute,

ich muss dieses Verfahren auch implementieren und habe mir dazu mal folgenden Pseudocode besorgt:

Delphi-Quellcode:

PROCEDURE Karatsuba(n: INTEGER; x, y: BigNumber): BigNumber;
VAR
a, b, c, d, x1, x2, x3: BigNumber;
BEGIN
IF n = 1 THEN
RETURN (x * y)
ELSE
"Berechne a, b, c, d";
x1 := Karatsuba(n DIV 2, a, c);
x2 := Karatsuba(n DIV 2, b, d);
x3 := Karatsuba(n DIV 2, a+b, c+d) - (x1 + x2);
RETURN(ShiftLeft(x1, n) + ShiftLeft(x3, n DIV 2) + x2);
END; (* IF *)
END Karatsuba;

Die Frage ist, da ich aus einer anderen Sprache komme, wie ich das am besten in Delphi implementiere ?
Kann mir da jemand zu helfen ?

gruß
Dutch_OnE

[edit=Sharky]Delphi-Tags gesetzt. Mfg, Sharky[/edit]

[mkinzler]

Das ist do schon Delphi(Pascal)-Code

[Dutch_OnE]

Was ich an der Sache nicht verstehe, ist die Gewährleistung der Rekursivität. Wie wird denn n verändert ?

[DeddyH]

n ist ein Eingangsparameter. Und die Rekursion ist durch den Aufruf der Prozedur durch sich selbst gewährleistet (x1 := ...)

[Dutch_OnE]

ist n nicht die Länge des Multiplikators ?

Das mit der Rekursivität habe ich jetzt verstanden. n wird ja immer durch 2 geteilt.