| Autor |
Beitrag |
Ivexx
Hält's aus hier
Beiträge: 6
|
Verfasst: Mi 13.06.07 11:25
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
 
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mi 13.06.07 11:34
Ich habe keinen Plan, was das ist, aber bei dem Wikipedia-Artikel dazu gibts auch Beispielcode. Ist zwar in Java, aber das sollte sich doch irgendwie auf deine BigInt-Klasse übertragen lassen, oder? _________________ We are, we were and will not be.
|
|
Luckie
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Mi 13.06.07 11:46
Könnten wir uns irgendwie auf ein Forum einigen oder zumindest gegenseitig verlinken?
www.delphipraxis.net...+implementieren.html
|
|
Horst_H
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mi 13.06.07 12:00
Hallo,
Dort home.netsurf.de/wolf...t/misc_en.html#mpint in der Zipdatei ist eine mp_base.pas, in der auf die Art von Karatsuba multipliziert wird.
Gruß Horst
|
|
Dutch_OnE
Hält's aus hier
Beiträge: 1
|
Verfasst: 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
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: 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, _________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
F34r0fTh3D4rk
Beiträge: 5284
Erhaltene Danke: 27
Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
|
Verfasst: 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;
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
|
|
|
