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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

@kylepw kylepw commented Nov 28, 2019

Why does "2*nby2" trick work?

@Victor-Alexandru

This comment has been minimized.

Copy link

@Victor-Alexandru Victor-Alexandru commented Dec 28, 2019

@booomerang

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

@5war00p 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

This comment has been minimized.

Copy link

@rajashit14 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))

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