python - python解释器是否隐含地使用了中国余数定理？

Question

重现我是如何相信这一点的步骤:

>>> 2 ** 4324567

如果你厌倦了等待，键盘会中断上面的操作，因为比较操作只需要不到一秒，而上面的操作大约需要 20 秒。

>>> 2 ** 4324567 % 55

您会注意到模数运算的速度更快。唯一可能的方法是使用中国剩余定理之类的东西，对吗？

奇怪的是，如果指数(即 2 的次方)是一个计算值(如 2 * 2162283 或 e 其中 e = 2 * 2162283) 它似乎没有这样做。有人可以解释这里发生了什么吗？

Answer 1

此处求幂的时间:

>>> 2 ** 4324567

实际上很简短，你可以通过做来验证，例如，

>>> x = 2 ** 4324567

相反。原来的大部分时间实际上是在将内部 400 万位以上的二进制整数转换为十进制字符串进行显示所消耗的。

太贵了。在以 2 为基数和以 10 为基数的表示形式之间进行转换通常需要位数(或数字)的二次方时间。

这也是为什么带有模数运算的显示得更快的原因:只有 2 个小数位可以显示。进展很快。

但是，如果您要进行模幂运算，请改用 pow() 的 3 参数版本。这比先计算一个巨大的幂然后再进行模运算要高效得多。