/karatsuba.py
Last active May 21, 2019
| 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 |
This comment has been minimized.
This comment has been minimized.
iserlohnarchmage
commented
Dec 22, 2018
You need to make sure that inputs are all int. |
This comment has been minimized.
This comment has been minimized.
priyam4197
commented
May 21, 2019
variables a, c, and nby2 are assigned float type. convert them to int: |
This comment has been minimized.
zarifaziz commentedDec 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