Karatsuba recursive code is not working correctly

Question

I want to implement Karatsuba multiplication algorithm in python.But it is not working completely.

The code is not working for the values of x or y greater than 999.For inputs below 1000,the program is showing correct result.It is also showing correct results on base cases.

#Karatsuba method of multiplication.

f = int(input()) #Inputs
e = int(input())

def prod(x,y):
    r = str(x)
    t = str(y)
    lx = len(r)  #Calculation of Lengths
    ly = len(t)

    #Base Case

    if(lx == 1 or ly == 1):
        return x*y

    #Other Case

    else:
        o = lx//2
        p = ly//2

        a = x//(10*o)   #Calculation of a,b,c and d.
        b = x-(a*10*o)  #The Calculation is done by
        c = y//(10*p)   #calculating the length of x and y
        d = y-(c*10*p)  #and then dividing it by half.
                        #Then we just remove the half of the digits of the no.

        return (10**o)*(10**p)*prod(a,c)+(10**o)*prod(a,d)+(10**p)*prod(b,c)+prod(b,d)

print(prod(f,e))

I think there are some bugs in the calculation of a,b,c and d.

Answer 1

a = x//(10**o)
b = x-(a*10**o)
c = y//(10**p)
d = y-(c*10**p)

You meant 10 to the power of, but wrote 10 multiplied with.

You should train to find those kinds of bugs yourself. There are multiple ways to do that:

• Do the algorithm manually on paper for specific inputs, then step through your code and see if it matches
• Reduce the code down to sub-portions and see if their expected value matches the produced value. In your case, check for every call of prod() what the expected output would be and what it produced, to find minimal input values that produce erroneous results.
• Step through the code with the debugger. Before every line, think about what the result should be and then see if the line produces that result.