karatsuba.py

"""Multiply two numbers using Karatsuba algorithm"""


defkaratsuba(a: int, b: int) ->int:
"""
 >>> karatsuba(15463, 23489) == 15463 * 23489
 True
 >>> karatsuba(3, 9) == 3 * 9
 True
 """
iflen(str(a)) ==1orlen(str(b)) ==1:
returna*b

m1=max(len(str(a)), len(str(b)))
m2=m1//2

a1, a2=divmod(a, 10**m2)
b1, b2=divmod(b, 10**m2)

x=karatsuba(a2, b2)
y=karatsuba((a1+a2), (b1+b2))
z=karatsuba(a1, b1)

return (z*10** (2*m2)) + ((y-z-x) *10** (m2)) + (x)


defmain():
print(karatsuba(15463, 23489))


if__name__=="__main__":
main()