重现我是如何相信这一点的步骤:
>>> 2 ** 4324567
如果你厌倦了等待,键盘会中断上面的操作,因为比较操作只需要不到一秒,而上面的操作大约需要 20 秒。
>>> 2 ** 4324567 % 55
您会注意到模数运算的速度更快。唯一可能的方法是使用中国剩余定理之类的东西,对吗?
奇怪的是,如果指数(即 2 的次方)是一个计算值(如 2 * 2162283
或 e
其中 e = 2 * 2162283
) 它似乎没有这样做。有人可以解释这里发生了什么吗?
最佳答案
此处求幂的时间:
>>> 2 ** 4324567
实际上很简短,你可以通过做来验证,例如,
>>> x = 2 ** 4324567
相反。原来的大部分时间实际上是在将内部 400 万位以上的二进制整数转换为十进制字符串进行显示所消耗的。
太贵了。在以 2 为基数和以 10 为基数的表示形式之间进行转换通常需要位数(或数字)的二次方时间。
这也是为什么带有模数运算的显示得更快的原因:只有 2 个小数位可以显示。进展很快。
但是,如果您要进行模幂运算,请改用 pow()
的 3 参数版本。这比先计算一个巨大的幂然后再进行模运算要高效得多。
https://stackoverflow.com/questions/69776682/