| 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 |
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)).
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)
Why does "2*nby2" trick work?
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 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.
@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
#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))
I think at lines 9 and 11, there should be floor division (//) instead of simple division (/). They should be like:
a = x // 10**(nby2)
c = y // 10**(nby2)
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