问Python中的模幂运算算法
EN

Stack Overflow用户

提问于 2014-04-06 06:09:59

回答 1查看 3.7K关注 0票数 2

我已经创建了一个函数来计算大模指数。我知道这个函数内置于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的时候开始失败，我不太确定为什么。

modular-arithmetic

python

algorithm

回答 1

Stack Overflow用户

发布于 2014-04-06 07:18:16

我的猜测是Python的pow()在幕后运行在double上。失败的第一个值(38508450670424585)的以2为底的对数大约是55，但double的精度只有53位，因此不一定能精确地表示大于2^53的整数。我的猜测是，如果你检查最后一个成功的数字(即x=16)的以2为底的对数，它将小于53。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/22887498

复制

相似问题

问Python中的模幂运算算法
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Python中的模幂运算算法EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Python中的模幂运算算法
EN