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 位小数。进展很快。

但是，如果您要进行模幂运算，请改用 3 参数版本的

pow()

。这比先计算巨幂然后再进行模运算要高效得多。

编辑

我不确定它是什么时候添加的，但至少在Python 3.12.3下

str(int)

不再需要二次时间。

x = str(2 ** 4324567)

现在在我的盒子上大约一秒钟即可完成。但是，由于早期的“安全修复”，您首先必须执行

sys.set_int_max_str_digits(0)

，否则尝试转换如此大的整数会引发异常。

这些都没有改变，在适当的时候使用 3 参数

pow()

仍然要好得多。如果您非常关心将大整数转换为十进制的速度，请安装

gmpy2

扩展，在执行此任务时它通常要快得多（通常超过 4 倍）。

Answer 2

这里没有使用中国剩余定理，也没有什么用处。如果您想进行模幂运算，请使用 3 参数

pow

：

pow(2, 4324567, 55)

。

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