3
\$\begingroup\$

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

def karatsuba(x, y):
    if x < 10 or y < 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?

\$\endgroup\$

closed as off-topic by vnp, Janne Karila, Roland Illig, t3chb0t, Graipher Jun 8 '17 at 7:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – vnp, Janne Karila, Roland Illig, t3chb0t, Graipher
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Off topic: not a specific working piece of code. karatsuba() lacks a doc string. \$\endgroup\$ – greybeard Jun 8 '17 at 5:58
  • \$\begingroup\$ @greybeard - Can you please explain the whole doc string in more detail? I looked through the doc but I don't understand why my code requires that? Is it some sort of python convention? \$\endgroup\$ – Zaid Humayun Jun 9 '17 at 1:58
  • \$\begingroup\$ code doesn't require anything - responsible coding does. You may think the code will be read by (machines and) yourself, only - even if that turns out to be true, a later you may be glad to see documented code. Then, code has an annoying tendency to be "quoted" (cut&pasted) out of context: minimise the need for clarifications, keep them close to the needy code, stick to conventions (if for tool support). \$\endgroup\$ – greybeard Jun 9 '17 at 6:04
1
\$\begingroup\$

Errors in the code:

  1. 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

  1. 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 >= min(...)

  1. 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 >> n is the same as x // 2**n and x << n is the same as x * 2**n and these are much more efficient than base 10 operations.

\$\endgroup\$
  • \$\begingroup\$ Why do I need to change the len(str_x) to 2*n_2 and len(str_x) // 2 to n_2 ? Wouldn't those two things be equal? \$\endgroup\$ – Zaid Humayun Jun 9 '17 at 1:56
  • \$\begingroup\$ @ZaidHumayun No. For example, if len(str_x) is odd (then it wouldn't equal 2 * n_2). Or if len(str_y)//2 is less than len(str_x)//2 in which case n_2 would be the former. \$\endgroup\$ – aes Jun 9 '17 at 2:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.