Karatsuba Algorithm in Python I implemented a Karatsuba algorithm in Python but it doesn't give me the exact answer. 

def karatsuba(x, y):
    if x &lt; 10 or y &lt; 10:
        return x*y

    #making the two numbers strings here
    str_x = str(x)
    str_y = str(y)

    #finding the mid point for each number here
    n = max(len(str(x)), len(str(y)))
    n_2 = int(n / 2)

    #higher bits of each number
    x_h = int(str_x[:n_2])
    y_h = int(str_y[:n_2])

    #lower bits for each number here
    x_l = int(str_x[n_2:])
    y_l = int(str_y[n_2:])

    a = karatsuba(x_h, y_h)
    d = karatsuba(x_l, y_l)
    e = karatsuba(x_h + x_l, y_h + y_l) - a - d

    return a*10**len(str_x) + e*10**(len(str_x) // 2) + d


result = karatsuba(1234, 8765)
print(result)


I think its because I am taking integer values and ignore decimals of floating point values. 

When I run the above program my answer is 10,402,010 whereas the actual answer is 10,816,010

How can I improve this?
Errors in the code:


When you split str_x[:n_2] and str_y[:n_2] you're taking the same number of digits from the most significant part of each number. You need to instead take the same number of digits from the least significant part of each number.


For example, the cross multiplication step of karatsuba(12 + 34, 87 + 65) goes wrong:

You get x = 46 and y = 152 so n_2 = 1 and str_x[:n_2] = '4' and str_y[:n_2] = '1'. These are not offset by the same amount!

Instead you could set

#higher bits of each number
x_h = int(str_x[:-n_2])
y_h = int(str_y[:-n_2])

#lower bits for each number here
x_l = int(str_x[-n_2:])
y_l = int(str_y[-n_2:])


Negative indices count from the end, and this is just what you want so that you pull out the same number of powers of ten from each. Then str_x[:-n_2] = str_x[:-1] = all but the last n_2 = 1 digit of x which is 4, and str_y[:-n_2] = str_x[:-1] = all but the last n_2 = 1 digit of x which is 15. This works the way it should


With or without the above fix, your code will crash when both numbers > 10 and one of them is twice (or more) as many digits as the other. Then one of the slices will be the empty string, and int('') throws an error as opposed to (as you would want) returning 0.


A quick fix to this would be to make the higher part and lower part each a function, and check for the empty string. Alternatively, you could have a special case in karatsuba when n_2 &gt;= min(...)


Finally, there's a bug in the return computation. Instead of len(str_x) you want 2 * n_2 and instead of len(str_x) // 2 you want n_2.


Some quick comments on issues other than the errors

Using str(x) is not very efficient, and does a lot of extra work in what is supposed to be an implementation of an efficient way to multiply. For getting the basic ideas of the algorithm down, though, it's fine for a start and I won't complain too much.

But you should at least be aware that a better way would be to split the number into two pieces in base 2 and use bit string operations. This would be a good follow-up exercise. Specifically x &gt;&gt; n is the same as x // 2**n and x &lt;&lt; n is the same as x * 2**n and these are much more efficient than base 10 operations.