Skip to content

Instantly share code, notes, and snippets.

# anirudhjayaraman/karatsuba.py Last active May 21, 2019

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 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 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)).

### priyam4197 commented May 21, 2019

 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 variables a, c, and nby2 are assigned float type. convert them to int: a =int( x / 10**(nby2)) c = int(y / 10**(nby2)) nby2 = int(n/2)
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.