abbarnes

Karatsuba Multiplication Python3

Jan 21st, 2018
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.45 KB | None | 0 0
  1. # Karatsuba Multiplication
  2. # Uses Python3
  3.  
  4. def split(number, side = 0):
  5.     '''Helper function that returns either the first(0) or second(1) half of an integer, divided at index'''
  6.     assert type(number) == int, "non-integer passed to split()"
  7.     assert side in [0,1], "split() passed side not in [0,1]"
  8.     num_string = str(number)
  9.     length = len(num_string)
  10.     index = int(length/2)
  11.     if side == 0:
  12.         return int(num_string[:index])
  13.     else:
  14.         return int(num_string[index:])
  15.  
  16. def karatsuba_mult(x,y):
  17.     '''Takes input of two numbers of length Nx, Ny; Computes the product recursively using Karatsuba method.'''
  18.     #Uses following expression for product:
  19.     # x*y = [10^(P_x)a+b]*[10^(P_y)c+d]
  20.     # x*y = 10^(P_x + P_y)ac + 10^(P_x)ad + 10^(P_y)bc + bd
  21.     # where P_x = len(x)-len(a) and P_y = len(y)-len(c)
  22.  
  23.     #initialization
  24.     assert type(x) == int, "First Input Wrong Type"
  25.     assert type(y) == int, "Second Input Wrong Type"
  26.     #find the actual lengths of x and y
  27.     Nx = int(len(str(x)))
  28.     Ny = int(len(str(y)))
  29.     #check for base case
  30.     if Nx<=2 and Ny <=2:
  31.         print("answer: ", x*y)
  32.         return x*y
  33.     #recursive computation
  34.     a = split(x,0)
  35.     b = split(x,1)
  36.     c = split(y,0)
  37.     d = split(y,1)
  38.     Px = Nx - len(str(a))
  39.     Py = Ny - len(str(c))
  40.     return (  (10**(Px+Py))*karatsuba_mult(a,c) +
  41.             (10**(Px))*karatsuba_mult(a,d) +
  42.             (10**(Py))*karatsuba_mult(b,c) +
  43.             karatsuba_mult(b,d)
  44.             )
Add Comment
Please, Sign In to add comment