Pasted

# Karatsuba Multiplication
# Uses Python3
 
def split(number, side = 0):
    '''Helper function that returns either the first(0) or second(1) half of an integer, divided at index'''
    assert type(number) == int, "non-integer passed to split()"
    assert side in [0,1], "split() passed side not in [0,1]"
    num_string = str(number)
    length = len(num_string)
    index = int(length/2)
    if side == 0:
        return int(num_string[:index])
    else:
        return int(num_string[index:])
 
def karatsuba_mult(x,y):
    '''Takes input of two numbers of length Nx, Ny; Computes the product recursively using Karatsuba method.''' 
    #Uses following expression for product: 
    # x*y = [10^(P_x)a+b]*[10^(P_y)c+d] 
    # x*y = 10^(P_x + P_y)ac + 10^(P_x)ad + 10^(P_y)bc + bd
    # where P_x = len(x)-len(a) and P_y = len(y)-len(c)
 
    #initialization 
    assert type(x) == int, "First Input Wrong Type"
    assert type(y) == int, "Second Input Wrong Type"
    #find the actual lengths of x and y
    Nx = int(len(str(x)))
    Ny = int(len(str(y)))
    #check for base case
    if Nx<=2 and Ny <=2:
        print("answer: ", x*y)
        return x*y
    #recursive computation
    a = split(x,0)
    b = split(x,1)
    c = split(y,0)
    d = split(y,1)
    Px = Nx - len(str(a))
    Py = Ny - len(str(c))
    return (  (10**(Px+Py))*karatsuba_mult(a,c) + 
            (10**(Px))*karatsuba_mult(a,d) + 
            (10**(Py))*karatsuba_mult(b,c) +
            karatsuba_mult(b,d) 
            )