karatsuba.py

importrandom
frommathimportceil
frommathimportlog10


defget_digits(n):
ifn>0:
digits=int(log10(n)) +1
elifn==0:
digits=1
else:
digits=int(log10(-n)) +2
returndigits


defkaratsuba(x, y):
# the base case for recursion
ifx<10andy<10:
returnx*y

# n is the number of digits in the highest input number
n=max(get_digits(x), get_digits(y))

n_2=int(ceil(n/2.0))
n=nifn%2==0elsen+1

# split the input numbers
a, b=divmod(x, 10**n_2)
c, d=divmod(y, 10**n_2)

# applying the recursive steps
ac=karatsuba(a, c)
bd=karatsuba(b, d)
ad_bc=karatsuba((a+b), (c+d)) -ac-bd

# performs the multiplication
z2= (10**n) *ac
z1= (10**n_2) *ad_bc
z0=bd
returnz2+z1+z0


deftest():
foriinrange(1000):
x=random.randint(1, 10**5)
y=random.randint(1, 10**5)
expected=x*y
result=karatsuba(x, y)
ifresult!=expected:
returnprint("failed")
returnprint("ok")


if__name__=="__main__":
test()