karatsuba algorithm

Work in Progress

Concept

Karatsuba algorithm

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