python - python解释器是否隐式使用中国剩余定理？

Question

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

>>> 2 ** 4324567

如果您厌倦了等待，键盘会中断上述操作，因为比较操作需要不到一秒钟，而上述操作需要 20 秒。

>>> 2 ** 4324567 % 55

您会注意到具有模数运算的那个要快得多。这可能的唯一方法是，如果它使用类似中国剩余定理的东西，对吗？

奇怪的是，如果指数（即 2 的幂）是一个计算值（如2 * 2162283或ewhere e = 2 * 2162283），它似乎不会这样做。有人可以解释这里发生了什么吗？

标签： pythonmath

Answer 1

在这里进行幂运算的时间：

>>> 2 ** 4324567

实际上很简短，您可以通过执行来验证，例如，

>>> x = 2 ** 4324567

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

这太贵了。在以 2 为底和以 10 为底的表示之间进行转换通常需要在位数（或位数）上呈二次方的时间。

这也是模数运算出现得更快的原因：只有 2 个十进制数字要显示。那进展很快。

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