Below is my python implementation for the Karatsuba multiplication algorithm. This code seems to work for most inputs, but starts failing after the digits grow too large. For example, with the 64 digit inputs
x = 3141592653589793238462643383279502884197169399375105820974944592
y = 2718281828459045235360287471352662497757247093699959574966967627
the algorithm fails. But when I use only the first 35 digits, the algorithm works. Can anyone explain where this implementation is falling short?
from math import floor, ceil
def karatsuba(x, y):
sx = str(x)
sy = str(y)
n = max(len(sx), len(sy))
if len(sx) == 1 and len(sy) == 1:
return x*y
m = ceil(n/2)
a = int(x / (10**m))
b = int(x % (10**m))
c = int(y / (10**m))
d = int(y % (10**m))
ac = karatsuba(int(a), int(c))
bd = karatsuba(int(b), int(d))
adbc = karatsuba(int(a) + int(b), int(c) + int(d)) - ac - bd
return int(str(ac) + '0' * 2 * m) + int(str(adbc) + '0' * m) + bd
a = int(x / (10**m))
c = int(y / (10**m))
These two lines are prone to rounding errors. In python3, the / operator is a floating-point division operator. Just change / to // for integer division.
Try this code to see the problem
x = 2222222222222222222222222222222222
p = 10**17
print(int(x/p))
print(int(x//p))