karatsuba's integer multiplication algorithm python

Question

This code is not passing all the test cases, can somebody help? I only pass the straight forward test then it loses precision.

import math
import unittest


class IntegerMultiplier:

    def multiply(self, x, y):
        if x < 10 or y < 10:
            return x * y

        x = str(x)
        y = str(y)

        m_max = min(len(x), len(y))
        x = x.rjust(m_max, '0')
        y = y.rjust(m_max, '0')

        m = math.floor(m_max / 2)

        x_high = int(x[:m])
        x_low = int(x[m:])

        y_high = int(y[:m])
        y_low = int(y[m:])

        z1 = self.multiply(x_high, y_high)
        z2 = self.multiply(x_low, y_low)
        z3 = self.multiply((x_low + x_high), (y_low + y_high))
        z4 = z3 - z1 - z2

        return z1 * (10 ** m_max) + z4 * (10 ** m) + z2


class TestIntegerMultiplier(unittest.TestCase):

    def test_easy_cases(self):
        integerMultiplier = IntegerMultiplier()

        case2 = integerMultiplier.multiply(2, 2)
        self.assertEqual(case2, 4)

        case3 = integerMultiplier.multiply(2, 20000)
        self.assertEqual(case3, 40000)

        case4 = integerMultiplier.multiply(2000, 2000)
        self.assertEqual(case4, 4000000)

    def test_normal_cases(self):
        intergerMultiplier = IntegerMultiplier()

        case1 = intergerMultiplier.multiply(1234, 5678)
        self.assertEqual(case1, 7006652)

if __name__ == '__main__':
    unittest.main()

for the first test case, 'test_easy_cases' all are passing for the other two cases, I get error e.g. AssertionError: 6592652 != 7006652

m_max = min(len(x), len(y)) After answering, I think I know what you wanted here - it urgently needs a code comment, as it looks plain wrong without. — greybeard
– greybeard, Commented Jul 21, 2019 at 10:27
You should add at least one non-trivial asymmetric test case like 123, 98. — greybeard
– greybeard, Commented Jul 21, 2019 at 10:36
Two suggestions how to approach this: Firstly, find a small testcase (can yours get any smaller?) that triggers the issue. Then, use a debugger to step through the code and to inspect when exactly its state is not what you expect. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Jul 21, 2019 at 10:47

greybeard · Accepted Answer · 2019-07-21 10:40:16Z

1

In choosing m, you choose a base for all following decompositions and compositions. I recommend one with a representation of length about the average of the factors' lengths.
I have "no" idea why time and again implementing Karatsuba multiplication is attempted using operations on decimal digits - there are two places you need to re-inspect:

when splitting a factor f into high and low, low needs to be f mod m, high f // m
in the composition (last expression in IntegerMultiplier.multiply()), you need to stick with m (and 2×m) - using m_max is wrong every time m_max isn't even.

edited Jul 21, 2019 at 10:40

answered Jul 21, 2019 at 10:25

greybeard

2,6779 gold badges40 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

greybeard Over a year ago

When slicing in Python, a negative number means "from the right end".

Collectives™ on Stack Overflow

karatsuba's integer multiplication algorithm python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related