Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Karatsuba Multiplication
def karatsuba(x,y):
"""Function to multiply 2 numbers in a more efficient manner than the grade school algorithm"""
if len(str(x)) == 1 or len(str(y)) == 1:
return x*y
else:
n = max(len(str(x)),len(str(y)))
nby2 = n / 2
a = x / 10**(nby2)
b = x % 10**(nby2)
c = y / 10**(nby2)
d = y % 10**(nby2)
ac = karatsuba(a,c)
bd = karatsuba(b,d)
ad_plus_bc = karatsuba(a+b,c+d) - ac - bd
# this little trick, writing n as 2*nby2 takes care of both even and odd n
prod = ac * 10**(2*nby2) + (ad_plus_bc * 10**nby2) + bd
return prod
@zarifaziz

This comment has been minimized.

Copy link

zarifaziz commented Dec 4, 2018

Hey, I'm getting the following error when running your code on Python 3.7

Traceback (most recent call last):
File ".\assignment_1.py", line 35, in
karatsuba(1234,5678)
File ".\assignment_1.py", line 26, in karatsuba
ac = karatsuba(a,c)
File ".\assignment_1.py", line 26, in karatsuba
ac = karatsuba(a,c)
File ".\assignment_1.py", line 26, in karatsuba
ac = karatsuba(a,c)
[Previous line repeated 994 more times]
File ".\assignment_1.py", line 15, in karatsuba
if len(str(x)) == 1 or len(str(y)) == 1:
RecursionError: maximum recursion depth exceeded while getting the str of an object

@iserlohnarchmage

This comment has been minimized.

Copy link

iserlohnarchmage commented Dec 22, 2018

Hey, I'm getting the following error when running your code on Python 3.7

Traceback (most recent call last):
File ".\assignment_1.py", line 35, in
karatsuba(1234,5678)
File ".\assignment_1.py", line 26, in karatsuba
ac = karatsuba(a,c)
File ".\assignment_1.py", line 26, in karatsuba
ac = karatsuba(a,c)
File ".\assignment_1.py", line 26, in karatsuba
ac = karatsuba(a,c)
[Previous line repeated 994 more times]
File ".\assignment_1.py", line 15, in karatsuba
if len(str(x)) == 1 or len(str(y)) == 1:
RecursionError: maximum recursion depth exceeded while getting the str of an object

You need to make sure that inputs are all int.
Try karatsuba(int(x),int(y)).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.