procedure Karatsuba(PA, PB, PR: PInt64Array; d: integer);
var
AL, AR, BL, BR, ASum, BSum, X1, X2, X3: PInt64Array;
i, halfd: integer;
begin
if d <= 100 then
begin
GradeSchoolMult(Pa, Pb, Pr, d);// normal multiplikation, definiert woanders
exit;
end;
halfd := d shr 1;
AR := @PA[0];
AL := @PA[halfd];
BR := @PB[0];
BL := @PB[halfd];
ASum := @PR[d * 5];
BSum := @PR[d * 5 + halfd];
X1 := @PR[0];
X2 := @PR[d];
X3 := @PR[d * 2];
for i := 0 to halfd - 1 do
begin
asum[i] := al[i] + ar[i];
bsum[i] := bl[i] + br[i];
end;
Karatsuba(AR, Br, X1, halfd);
Karatsuba(AL, BL, X2, halfd);
Karatsuba(ASum, BSum, X3, halfd);
for i := 0 to d - 1 do
X3[i] := X3[i] - X1[i] - X2[i];
for i := 0 to d - 1 do
PR[i + halfd] := PR[i + halfd] + X3[i];
end;
begin
Alen := length(self.fDigits);
BLen := Length(I2.fDigits);
iMin := ALen;
iMax := BLen;
if ALen > BLen then
begin
iMin := BLen;
iMax := ALen;
end;
if (iMin < 80) or (imin < Imax shr 4) then
begin
self.Mult(i2);
exit;
end;
d := 1;
while d < iMax do
d := d * 2;
setlength(self.fDigits, d);
setlength(i2.fDigits,d);
PA := @self.fdigits[0];
PB := @i2.fdigits[0];
HR := GlobalAlloc(GMEM_FIXED, d * 6 * Sizeof(int64));
PR := GlobalLock(HR);
FillChar(Pr[0], sizeof(int64) * 6 * d, 0);
Karatsuba(PA, PB, PR, d);
DoCarry(Pr, self.Base, d * 2);
d := 2 * d;
while (d > 0) and (pr[d - 1] = 0) do
Dec(d);
setlength(self.fDigits, d);
setlength(i2.fDigits, BLen); {Changes input variable ?????????? GDD}
move(pr[0], self.fdigits[0], d * sizeof(int64));
self.Trim;
self.Sign := self.Sign * i2.Sign;
GlobalUnlock(HR);
GlobalFree(HR);
end;