Python 中大整数的 Karatsuba 乘法错误

Question

我一直在尝试通过以下方式在 Python3 中实现 Karatsuba algorithm：

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%10**(n/2)
    c = num2//10**(n/2)
    d = num2%10**(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)

虽然该功能适用于小产品，但不适用于超过 18 位的产品。人们可以通过运行看到这一点，比如说

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

如果有人能解释这个问题的根源是什么，我将不胜感激，如果可能的话，如何修改这段代码来修复它。我最好的猜测是 Python 在某些时候犯了一些舍入错误。也就是说，我真的不知道 int 这种语言的基本原理。

Answer 1

使用 n//2 而不是 n/2 以保持 ints 并避免由于 float 值造成的精度损失。

Python 中大整数的 Karatsuba 乘法错误

Karatsuba multiplication error for large integers in Python

python

algorithm

multiplication