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;