karatsuba algorithm
Concept
Karatsuba algorithm
- divide & conquer on integer multiplication
Karatsuba(x, y):
n = max(bitLength(x), bitLength(y))
if n <= small threshold:
return direct multiplication of x and y
m = ceil(n / 2)
a = floor(x / 2^m)
b = x mod 2^m
c = floor(y / 2^m)
d = y mod 2^m
z2 = Karatsuba(a, c)
z0 = Karatsuba(b, d)
z1 = Karatsuba(a + b, c + d)
middle = z1 - z2 - z0
return z2 * 2^(2m) + middle * 2^m + z0
Runtime