# 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) 
            )