Karatsuba Multiplication with Recursion

Question

I am trying to implement Karatsuba Multiplication in Python. Unfortunately, my code is failing on 64 digit test cases (curriculum I am working on) because I start yielding negative numbers for my gauss calculations. I included my code below and was wondering if anyone would be able to offer some guidance what I may be missing.

Additionally, I am intentionally storing these large numbers as strings because the whole point of this assignment was to challenge myself calling recursion. I believe Python is able to handle these large numbers automatically, but it would defeat the whole challenging part of this assignment.

The input are both 64 digits.

def karatsuba(input1, input2):
    first_number = len(input1)
    second_number = len(input2)

    # base case
    if first_number <= 2:
        return str(int(input1) * int(input2))

    else:
        # first half
        # changing the divider from round(first_number/2) to first_number // 2 yielded different results.
        if first_number % 2 == 1:
            add_zero = first_number + 1
        else:
            add_zero = first_number

        divider_a = first_number // 2
        a = input1[:divider_a]
        b = input1[divider_a:]
        print("a: " + a)
        print("b: " + b)

        # second half
        divider_b = second_number // 2
        c = input2[:divider_b]
        d = input2[divider_b:]
        print("c: " + c)
        print("d: " + d)

    # recursive
    ac = karatsuba(a, c)
    print("ac: " + ac)

    bd = karatsuba(b, d)
    print("bd: " + bd)

    ad = karatsuba(a, d)
    print("ad: " + ad)
    bc = karatsuba(b, c)
    print("bc: " + bc)

    # for subtraction, you add the negative.

    def addition(input_a, input_b):
        return str(int(input_a) + int(input_b))

    ab_cd = karatsuba(addition(a, b), addition(c, d))
    print("ab_cd: " + ab_cd)

    gauss = addition(addition(ab_cd, "-"+ac), "-"+bd)

    print("gauss: " + gauss)

    merge1 = ac + "0"*add_zero
    print("merge1: " + merge1)
    merge2 = gauss + str(("0"*(add_zero//2)))
    print("merge2: " + merge2)
    merge3 = bd
    return (addition(addition(merge1, merge2), merge3))

if __name__ == '__main__':
    input_a, input_b = map(str, input().split())
    print(karatsuba(input_a, input_b))

Answer 1

When I test your code, it blows up with an ValueError: invalid literal for int() with base 10: '' error. And you can see in your debugging output one issue:

a: 1
b: 02
c: 
d: 2

Empty strings are getting passed around as numbers. And leading zeros are causing incorrect splitting of strings.

I believe your initial, primary problem is splitting the two inputs by different bases from the left. They should be split by the same base from the right. Otherwise, doing math on them makes no sense. you also include the sign of the number in the base calculation!

I also believe your subtration logic is fragile. It works for subtracting a small number from a much larger one, but otherwise, you run the risk of concatenating a "-" on an already negative number, getting results like "--4" that int() can't handle.

Finally, I believe there are mistakes in your math. It's further complicated by values you compute but never use (e.g. ad and bc).

Below is my rework of your code following the explanation of the Karatsuba algorithm in Wikipedia which I tested on their example and a pair of random 64 digit numbers. It is still flawed, e.g. number signs can still effect base calculation, subtraction is still fragile, etc. But basically demonstrates the algorithm:

def karatsuba(input1, input2):
    print("input1: {}, input2: {}".format(input1, input2))
    length1 = len(input1)
    length2 = len(input2)

    # base case
    if length1 <= 2 or length2 <= 2:
        return str(int(input1) * int(input2))

    # first half
    base_length = min(length1, length2) // 2

    divider_a = length1 - base_length
    high1, low1 = input1[:divider_a], input1[divider_a:]

    while len(low1) > 1 and low1[0] == '0':
        low1 = low1[1:]  # remove leading zeros

    print("high1:", high1, "low1:", low1)

    # second half
    divider_b = length2 - base_length
    high2, low2 = input2[:divider_b], input2[divider_b:]

    while len(low2) > 1 and low2[0] == '0':
        low2 = low2[1:]  # remove leading zeros

    print("high2:", high2, "low2:", low2)

    # recursive
    z0 = karatsuba(low1, low2)
    print("z0:", z0)

    z2 = karatsuba(high1, high2)
    print("z2:", z2)

    def addition(input_a, input_b):
        return str(int(input_a) + int(input_b))

    # The four multiplication Babbage solution:
    #
    # z1 = addition(karatsuba(low1, high2), karatsuba(high1, low2))
    # print("z1:", z1)

    # The three multiplication Gauss solution:
    # This approach may cause overflow, see https://en.wikipedia.org/wiki/Karatsuba_algorithm for a work around
    # For subtraction, you add the negative.

    z1 = addition(addition(karatsuba(addition(high1, low1), addition(high2, low2)), f"-{z2}"), f"-{z0}")
    print("z1: ", z1)

    return addition(addition(z2 + "0" * (base_length * 2), z1 + "0" * (base_length * 1)), z0 + "0" * (base_length * 0))

if __name__ == '__main__':
    a = "7392297780844983031173686285210463614020982285096612188770501341"
    b = "4688026175884269750785003351250107609139231296129030834139247897"

    print(karatsuba(a, b))