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

Copy link

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
Copy link

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
Copy link

kylepw commented Nov 28, 2019

Why does "2*nby2" trick work?

@Victor-Alexandru
Copy link

Victor-Alexandru commented Dec 28, 2019

@booomerang
Copy link

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
Copy link

5war00p commented Jul 25, 2020

@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
Copy link

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)
ad_plus_bc=karatsuba(a+b,c+d)-ac-bd
return ac
10**(2n)+ad_plus_bc10**n+bd
x=int(input())
y=int(input())
print(karatsuba(x,y))

@mkhuzaima
Copy link

mkhuzaima commented Sep 22, 2021

I think at lines 9 and 11, there should be floor division (//) instead of simple division (/). They should be like:

  1. a = x // 10**(nby2)
  1. c = y // 10**(nby2)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment