python - Large Kartusba multiplication is failing. What is possibly going wrong?

Question

I have implemented Karatsuba multiplication in Python.

The code and pseudocode are as follow:

def karatsuba(x, y):
    """
    Input: two n-digit positive integers x and y. 
    Output: the product x·y. 
    Assumption: n is a power of 2. (NOT assuming this)

    if n =1  then                   // base case
        compute x·y in one step and return the result
    else 
        a,b := ?rst and second halves of x 
        c,d := ?rst and second halves of y 
        compute p := a + b and q := c + d using grade-school addition 
        recursively compute ac := a·c, bd := b·d, and pq := p·q 
        compute adbc := pqacbd using grade-school addition 
        compute 10n ·ac + 10n/2 ·adbc + bd using grade-school addition and return the result
    """

    str_x = str(x)
    str_y = str(y)
    if len(str_x) == 1 or len(str_y) == 1:
        return x*y
    else:
        n = max(len(str_x), len(str_y))
        n_half = int(n / 2)
        
        a, b = x // 10**n_half, x % 10**n_half
        c, d = y // 10**n_half, y % 10**n_half
        
        p = a + b
        q = c + d
    
        ac = karatsuba(a, c)
        bd = karatsuba(b, c)
        pq = karatsuba(p, q)
        
        adbc = pq - ac - bd
        
        return 10**(2*n_half) * ac + 10**n_half * adbc + bd

When I do the multiplication of very large numbers, my code is failing.

Here is an example:

>>> a = 3141592653589793238462643383279502884197169399375105820974944592
>>> b = 2718281828459045235360287471352662497757247093699959574966967627
>>> mul_karatsuba = karatsuba(a, b)
>>> mul_builtin = a * b
>>> mul_karatsuba == mul_builtin
False
>>> mul_karatsuba
8945653667798941823160787739573304887842903322205621858854691873536479127635014727457078833467629169552143732979528067839403974
>>> mul_builtin
8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184

I am not able to find what exactly is wrong with my code. I have coded everything according to mentioned pseudocode.

Can you please help me?

question from:https://stackoverflow.com/questions/66051071/large-kartusba-multiplication-is-failing-what-is-possibly-going-wrong

Answer 1

Waitting for answers