Instantly share code, notes, and snippets.

# anirudhjayaraman/karatsuba.py Last active Mar 27, 2020

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

### wenli-yang 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)

### kylepw commented Nov 28, 2019

 Why does "2*nby2" trick work?

### Victor-Alexandru commented Dec 28, 2019

 Your code does not work on high numbers.Please try this version of karatsuba: https://github.com/alexdarie/Parallel-and-distributed-programming/blob/master/week12/mpi/karatsuba_classical_algorithm.py

### booomerang commented Mar 27, 2020

 Your code does not work on high numbers.Please try this version of karatsuba: https://github.com/alexdarie/Parallel-and-distributed-programming/blob/master/week12/mpi/karatsuba_classical_algorithm.py Your code from the link doesn't work properly too with the large numbers, 64-length * 64-length numbers for example. The problem is in '/' division symbol in python, use '//' instead.