{{ message }}

Instantly share code, notes, and snippets.

# anirudhjayaraman/karatsuba.py

Last active Feb 22, 2021
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

### ghost 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.

### 5war00p commented Jul 25, 2020 • edited

 @boomerang I agree with you. As @Victor-Alexandru solution is brilliant but I made some update by that we reduce some function calls and it can work with some more large numbers. Find my updated version below: #https://github.com/5war00p/Karatsuba/blob/master/Karatsuba_Mul_rec.py

### rajashit14 commented Sep 11, 2020

 #Here is the right code def karatsuba(x,y): if len(str(x))==1 or len(str(y))==1: return xy else: n=max(len(str(x)),len(str(y)))//2 a=x//10n b=x%10n c=y//10n d=y%10n ac=karatsuba(a,c) bd=karatsuba(b,d) ad_plus_bc=karatsuba(a+b,c+d)-ac-bd return ac10**(2n)+ad_plus_bc10**n+bd x=int(input()) y=int(input()) print(karatsuba(x,y))