Karatsuba Infinite Recursion - Python

Question

Beginner here. I've spent most of the day working on the Karatsuba Algorithm just because I thought it would be fruitful. I've seen similar questions on here, but they are in other languages and seem strangely complex. The following is my code. The minute it hits the recursive call to ac, it just keeps on recursing. It's as if it never hits the base case. If anyone could be so kind as to offer some insight as to where things are going wrong, it would be greatly appreciated. For this code, you should assume I'm multiplying 2, base-10, four-digit numbers.

def karatsuba(x, y):
    if len(str(x)) == 1 or len(str(y)) == 1:
        return (x * y)

    else:
        n = (max(len(str(x)), len(str(y))))

        a = x / 10**(n / 2)
        b = x % 10**(n / 2)
        c = y / 10**(n / 2)
        d = y % 10**(n / 2)

        ac = karatsuba(a, c)
        ad = karatsuba(a, d)
        bc = karatsuba(b, c)
        bd = karatsuba(b, d)

        product = (10**n*(ac) + 10**(n/2)*(ad + bc) + bd)

        return product

print (karatsuba(1234, 5678))

Answer 1

Just fixing your code with integer divisions made it work correctly but here's a slight different version using 3 recursive calls (in base 10):

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

    n = max(len(str(x)), len(str(y))) // 2
    p = 10**n

    a, b = divmod(x, p)
    c, d = divmod(y, p)

    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    abcd = karatsuba(a+b, c+d) - ac - bd

    return (ac*p + abcd)*p + bd

But it is much faster operating in binary and using bit-twiddling:

def karatsuba(x, y):
    if x < 16 or y < 16:
        return x * y

    n = max(x.bit_length(), y.bit_length()) // 2
    mask = (1 << n) - 1

    a, b = x >> n, x & mask
    c, d = y >> n, y & mask

    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    abcd = karatsuba(a+b, c+d) - ac - bd

    return (((ac << n) + abcd) << n) + bd

Answer 2

Do you want integer division? In this case, you should use:

a = x // 10 ** (n / 2)

and

c = y // 10 ** (n / 2)

Otherwise, your program will be feeding through decimals to your function which I assume is not intended.

I'm also a beginner, feel free to correct me.