CODEWITHSUNDEEP
pythonalgorithmmultiplicationkaratsuba
atr1
atr1

Reputation: 25

Own implementation of Karatsuba algorithm

Hi guys I am trying to come up with my own implementation of Karatsuba multiplication algorithm where the base case is trivial multiplication when one number is a single digit. My code seems to be failing to yield the correct answer and I believe this has something to do with the way z1 is calculated but I can't quite figure it out, please help me with this.

import math
x = input()
y = input()

def suba(x,y):
    if len(x) == 1 or len(y) == 1:
        x = int(x)
        y = int(y)
        return x*y
    else:
        n = int(math.ceil((min(len(x),len(y)))/2))
        h1 = x[0:n]
        l1 = x[n:len(x)]
        h2 = y[0:n]
        l2 = y[n:len(y)]
        z0 = suba(l1,l2)
        z1 = suba(str(int(l1)+int(h1)),str(int(l2)+int(h2)))
        z2 = suba(h1,h2)
        return (z2*10**(n*2))+((z1-z2-z0)*10**(n))+z0

print(suba(x,y))

Upvotes: 0

Views: 140

Answers (1)

trincot
trincot

Reputation: 350252

The problem is in the splitting. You need to split in such a way the size of the low (right) part is n. This is necessary, as the high parts of x and y must be comparable: they must have been extracted by dividing by the same power of 10.

So change the splitting code to this:

    h1 = x[:-n]
    l1 = x[-n:]
    h2 = y[:-n]
    l2 = y[-n:]

Note also that it is not necessary to specify 0 for the start of a range, nor to specify the length for the end of a range, as those are the defaults.

Upvotes: 0

Related Questions