Entwickler-Ecke :: Thema anzeigen - Karatsuba-Verfahren implementieren?!

Ivexx - Mi 13.06.07 11:25
Titel: Karatsuba-Verfahren implementieren?!

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

Moderiert von Christian S.: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Mi 13.06.2007 um 11:53

Gausi - Mi 13.06.07 11:34

Ich habe keinen Plan, was das ist, aber bei dem Wikipedia-Artikel [http://de.wikipedia.org/wiki/Karatsuba-Algorithmus] dazu gibts auch Beispielcode. Ist zwar in Java, aber das sollte sich doch irgendwie auf deine BigInt-Klasse übertragen lassen, oder?

Dutch_OnE - Sa 29.03.08 19:31

Hallo Leute,

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

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

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 ? Die Klasse aus dem vorherigen Beitrag ist sicherlich richtig, aber für mich so nicht nachvollziehbar.

gruß
Dutch_OnE

Moderiert von Narses: Code-Tags hinzugefügt

Hidden - So 30.03.08 00:26

Hi,

Hier einmal die Wikipedia-Implementation in Java:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

public static BigInteger karatsuba (BigInteger x, BigInteger y)
{
       // Verwende Standard Multiplikation bei kleinen Eingaben
       int n = Math.max (x.bitLength(), y.bitLength());
       if (n <= 1500) return x.multiply (y);

       // teile; x = xH * b^n + xL ,   y = xH * b^n + yL
       n = n / 2;
       BigInteger xH = x.shiftRight (n);
       BigInteger xL = x.subtract   (xH.shiftLeft(n));
       BigInteger yH = y.shiftRight (n);
       BigInteger yL = y.subtract   (yH.shiftLeft(n));

       // berechne die Teilresultate
       BigInteger p1 = karatsuba (xH, yH);
       BigInteger p2 = karatsuba (xL, yL);
       BigInteger p3 = karatsuba (xL.add (xH), yL.add (yH));

       // Setzte die Teile zum Gesamtergebnis zusammen
       return p1.shiftLeft (2*n).add (p3.subtract (p1).subtract (p2).shiftLeft (n)).add (p2);
}

mfG,

F34r0fTh3D4rk - Mi 02.04.08 13:51

hi,
die Delphi-Version, ungetestet:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

procedure Karatsuba(n: integer; x, y: BigNumber): BigNumber;
var
  a, b, c, d, x1, x2, x3: BigNumber;
begin
  if (n = 1) then
  begin
    result := x * y;
    exit;
  end;
  // "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);
  result := (x1 shl n) + (x3 shl (n div 2)) + x2;
end;

mfg

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!