时间戳

首页 > 解决方案 > python中的karatsuba算法实现

python-3.x - python中的karatsuba算法实现

问题描述

下面是我对 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

标签： python-3.xalgorithmkaratsuba

解决方案

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

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

试试这段代码看看问题

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

推荐阅读