Karatsuba算法，略有不准确

Question

我花了一段时间尝试在 Python 中实现 Karatsuba 的算法，虽然当我尝试将两个更大的数字（超过 ~10^15）相乘时，我的结果开始变得越来越接近不准确。我不明白为什么。

附带问题：我的基本情况是否有一种方法是“x 和 y 都（而不是其中之一）严格小于（而不是小于）10”


def karatsuba(x, y):
    # 1. Split ints

    if x <= 10 or y <= 10:
        #Base case
        return x * y

    n_x = ceil(log(x, 10))  # Nb of digits in x
    n_y = ceil(log(y, 10))

    n = max(n_x, n_y)

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

    # 2. Recursive calls

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

    res = ac * (10 ** (2*(n//2))) + (kara - ac - bd) * (10 ** (n//2)) + bd

    return res

示例：

x = 151222321858446622145369417738339374
y = 875336699541236667457869597252254524
karatsuba(x, y)

returns:

132370448112535269852891372864998437604548273605778561898354233338827976

而不是：

132370448112535277024334963430875927265604725663292579898354233338827976

Answer 1

由于 / 个分区，您通过 float 失去了精度。请改用 //。那么你也不需要转换回 int。更好的是，使用 divmod:

    N = 10 ** (n // 2)
    a, b = divmod(x, N)
    c, d = divmod(y, N)

Karatsuba算法，略有不准确

Karatsuba algorithm, slight inaccuracy

python

algorithm

karatsuba