Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # 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)
- )
Add Comment
Please, Sign In to add comment