python - 如何更快地计算 (x**2-2)%n - Python

Question

x = 2**1000000
n = 2**100000000

(x**2-2)%n太慢了。我找到了 pow() 但我不能使用它，因为我不能减去 2。(pow(x, 2)-2)%n而且(x*x-2)%n速度也很慢。当我测试(x*x-2)它时它很快，但是当我添加模运算符时它很慢。有没有办法计算(x**2-2)%n得更快？

标签： pythonpython-3.x

Answer 1

你在解释器中运行它吗？我做了一些测试，主要的减速似乎来自试图显示结果的解释器。

如果将表达式分配给变量，解释器将不会尝试显示结果，并且会非常快：

x = 2**1000000
n = 2**100000000
result = (x**2-2)%n

附录：

我最初的想法也与 MikeW 的回答相同，如果您希望代码的每一部分都快速，您可以利用 Python 的内部整数基 2 表示并使用按位左移：

x = 1 << 1000000
n = 1 << 100000000

随之而来的警告是，这仅有效，因为x和n是 2 的幂，并且您必须更加小心，以避免犯一个错误的错误。这个答案很好地解释了移位的基本工作原理，但是 Python 与 C、C++ 或 Java 等其他语言有点不同，因为 Python 整数是无限精度的，所以你永远不能像在其他语言中那样完全离开移位.