Karatsuba Multiplication

karatsuba.py

def karatsuba(A, B, n):
    """
    A(x) = a_1 * x + a_0
    B(x) = b_1 * x + b_0
    
    C(x) = a_1 * b_1 * x^2 + (a_1 * b_0 + a_0 * b_1) * x + a_0 * b_0
    
    Rewrite as 
    
    C(x) = a_1 * b_1 * x^2 + ((a_1 + a_0) * (b_0 + b_1) - a_1 * b_1 - a_0 * b_0) * x + a_0 * b_0
    
    Reduce the problem to 3 multiplications
    
    Running time: 
    O(3^log2n) -> O(n^log2(3)) = O(n^1.58)
    
    Master Theorem:
    if T(n) = a * T(ceil(n/b)) + O(n^d)
    constants a > 0,b > 1,d >= 0 then
    if d > logb(a) then O(n^d)
    if d = logb(a) then O(n^d * logn)
    if d < logb(a) then O(n^logb(a))
    
    O(n^d) amount of work on each level from 1 to log2(n)
    """
    product = 1