Last active
September 11, 2023 10:18
-
-
Save anirudhjayaraman/5ad211982fd68a88fa37 to your computer and use it in GitHub Desktop.
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Also, using the Gauss trick mentioned in the video (I think) will only work when the inputs are the same size. Which is why some implementations above fail for longer numbers, as somewhere in the recursive calls,
ad
andbc
have different powers of 10.here's an example where the Gauss trick fails
This is because if we expand the Gauss trick, you will see
ad
andbc
have different powers of 10 attached to them.ad + bc = 100*(13*6) + 10*(1*46) = 8260
, which, when added to the rest of the terms, gives the correct product.Here is my implementation btw:
I verified it works using the code below: