CODEWITHSUNDEEP
pythonalgorithmrecursionkaratsuba
Ryan
Ryan

Reputation: 1432

Karatsuba Infinite Recursion - Python

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))

Upvotes: 1

Views: 774

Answers (2)

AChampion
AChampion

Reputation: 30258

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

Upvotes: 3

boboquack
boboquack

Reputation: 259

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.

Upvotes: 1

Related Questions