Python中的模幂算法

Question

我写了一个函数，用来计算很大的模幂运算。我知道Python语言里其实已经有这个功能了。可是我的函数在处理超过17位的数字时出错了，我不知道为什么。希望能得到一些帮助。

from random import randint

def modpow(x,n,m):
  if n == 0:
    return 1
  elif n == 1:
    return x
  elif n%2 == 0:
    return modpow(x*(x%m),n/2,m)%m
  elif n%2 == 1:
    return (x *  modpow(x*(x%m),(n-1)/2,m)%m )%m

for i in range(5,32):
  x = ''
  n = ''
  m = ''
  for j in range(i):
    x += str(randint(0,9))
    n += str(randint(0,9))
    m += str(randint(0,9))
  x = int(x)
  n = int(n)
  m = int(m)
  if pow(x,n,m) != modpow(x,n,m):
    print(i,x,n,m)

示例输出：

17 38508450670424585 67111951647554134 59005802612594983
18 24027200512104766 205942669690724726 816654795945860553
...

我试了好几次，发现从i=17开始就总是出问题，我也不太明白原因。

Answer 1

我猜测Python的pow()函数在内部是用double类型来处理的。第一个出现问题的数字（38508450670424585）的以2为底的对数大约是55，但double类型只有53位的精度，所以大于2的53次方的整数不一定能被准确表示。我猜如果你查看最后一个成功的数字（也就是x=16时的情况），它的以2为底的对数会小于53。