Instantly share code, notes, and snippets.

# anirudhjayaraman/karatsuba.py

Last active Oct 14, 2021
Karatsuba Multiplication
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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?

### 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%10
n
c=y//10n
d=y%10
n
ac=karatsuba(a,c)
bd=karatsuba(b,d)
return ac
1. `a = x // 10**(nby2)`
1. `c = y // 10**(nby2)`