python 中的 karatsuba 算法实现

Question

下面是我对 Karatsuba 乘法算法的 python 实现。此代码似乎适用于大多数输入，但在数字变得太大后开始失败。例如，使用 64 位输入 x = 3141592653589793238462643383279502884197169399375105820974944592 y = 2718281828459045235360287471352662497757247093699959574966967627 算法失败。但是当我只使用前 35 位数字时，该算法有效。谁能解释一下这个实现的不足之处？

from math import floor, ceil
def karatsuba(x, y):
  sx = str(x)
  sy = str(y)
  n = max(len(sx), len(sy))
  if len(sx) == 1 and len(sy) == 1:
    return x*y
  m = ceil(n/2)
  a = int(x / (10**m))
  b = int(x % (10**m))
  c = int(y / (10**m))
  d = int(y % (10**m))
  ac = karatsuba(int(a), int(c))
  bd = karatsuba(int(b), int(d))
  adbc = karatsuba(int(a) + int(b), int(c) + int(d)) - ac - bd
  return int(str(ac) + '0' * 2 * m) + int(str(adbc) + '0' * m) + bd

Answer 1

a = int(x / (10**m))
c = int(y / (10**m))

这两行容易出现舍入误差。在python3中，/运算符是一个浮点除法运算符。只需将 / 更改为 // 即可进行整数除法。

试试这个代码看看问题

x = 2222222222222222222222222222222222
p = 10**17
print(int(x/p))
print(int(x//p))

python 中的 karatsuba 算法实现

karatsuba algorithm implementation in python

algorithm

python-3.x

karatsuba