Karatsuba multiplication error for large integers in Python-CodePudding

I've been trying to implement the Karatsuba algorithm in Python3 in the following way:

def karatsuba(num1,num2):
    n_max = max(len(str(int(num1))), len(str(int(num2))))
    if n_max == 1:
        return int(num1*num2)

    n = n_max   n_max%2

    a = num1//10**(n/2)
    b = num1**(n/2)
    c = num2//10**(n/2)
    d = num2**(n/2)

    t1 = karatsuba(a,c)
    t3 = karatsuba(b,d)
    t2 = karatsuba(a b,c d) - t1 - t3

    return int(t1*10**n   t2*10**(n/2)   t3)

While the function works for small products, it fails for ones that exceed 18 digits. One can see this by running, say,

import random

for i in range(1,12):
    a = random.randint(10**i, 10**(i 1)-1)
    b = random.randint(10**i, 10**(i 1)-1)
    print(f"{len(str(a*b))} digits, error: {abs(a*b - karatsuba(a,b))}")

I would appreciate if someone could explain what is the root of this problem and, if possible, how could this code be modified to fix it. My best guess is that some round-off error is committed by Python at some point. That said, I don't really know how int fundamentally works in this language.

CodePudding user response：

Use n//2 instead of n/2 to stay with ints and avoid that precision loss due to that float value.