Beginner here. I've spent most of the day working on the Karatsuba Algorithm just because I thought it would be fruitful. I've seen similar questions on here, but they are in other languages and seem strangely complex. The following is my code. The minute it hits the recursive call to ac, it just keeps on recursing. It's as if it never hits the base case. If anyone could be so kind as to offer some insight as to where things are going wrong, it would be greatly appreciated. For this code, you should assume I'm multiplying 2, base-10, four-digit numbers.
def karatsuba(x, y):
if len(str(x)) == 1 or len(str(y)) == 1:
return (x * y)
else:
n = (max(len(str(x)), len(str(y))))
a = x / 10**(n / 2)
b = x % 10**(n / 2)
c = y / 10**(n / 2)
d = y % 10**(n / 2)
ac = karatsuba(a, c)
ad = karatsuba(a, d)
bc = karatsuba(b, c)
bd = karatsuba(b, d)
product = (10**n*(ac) + 10**(n/2)*(ad + bc) + bd)
return product
print (karatsuba(1234, 5678))
Just fixing your code with integer divisions made it work correctly but here's a slight different version using 3 recursive calls (in base 10):
def karatsuba(x, y):
if x < 10 or y < 10:
return x * y
n = max(len(str(x)), len(str(y))) // 2
p = 10**n
a, b = divmod(x, p)
c, d = divmod(y, p)
ac = karatsuba(a, c)
bd = karatsuba(b, d)
abcd = karatsuba(a+b, c+d) - ac - bd
return (ac*p + abcd)*p + bd
But it is much faster operating in binary and using bit-twiddling:
def karatsuba(x, y):
if x < 16 or y < 16:
return x * y
n = max(x.bit_length(), y.bit_length()) // 2
mask = (1 << n) - 1
a, b = x >> n, x & mask
c, d = y >> n, y & mask
ac = karatsuba(a, c)
bd = karatsuba(b, d)
abcd = karatsuba(a+b, c+d) - ac - bd
return (((ac << n) + abcd) << n) + bd