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

Question

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

>>> 2 ** 4324567

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

>>> 2 ** 4324567 % 55

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

奇怪的是，如果指数（即 2 的幂）是一个计算值（如2 * 2162283或ewhere e = 2 * 2162283），它似乎不会这样做。有人能解释一下这是怎么回事吗？

Answer 1

这里进行求幂的时间：

>>> 2 ** 4324567

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

>>> x = 2 ** 4324567

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

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

这也是为什么带有模数运算的显示速度更快：只显示 2 位小数。进展很快。

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

Answer 2

这里没有使用中国剩余定理，也没有什么用处。如果你想进行模幂运算，请使用 3-argument pow: pow(2, 4324567, 55)。

第二行运行得更快，因为第一行中的几乎所有工作实际上都是构建结果的字符串表示形式，而不是执行求幂。第二行产生的数字要小得多，字符串化速度要快得多。