问如何更快地计算(x**2-2)%

EN

你在解释器里运行这个吗？我做了一些测试，主要的放缓似乎来自于试图显示结果的解释器。

如果将表达式赋值给变量，解释器将不会尝试显示结果，它将非常快：

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整数是无限精度，所以您永远不能像在其他语言中那样完全离开shift。

如果x总是2的幂，n总是2的幂，那么您可以使用字节数组上的位操作来轻松、快速地计算它，然后可以将其重构为一个“数字”。

如果2^N是(二进制)1后面是N零，那么(2^N)^2是(二进制)1，后面是2N零。

2^3 squared is b'1000000'

如果你有一个数字2^K (二进制1后面跟着K 0)，那么2^K-2将是K-1 (1)后面是零。

eg 2^4 is 16 =  b'10000', 2^4 - 2 is b'1110'

如果您需要"% 2^M“，那么在二进制文件中，只需选择最后(较低的)M位，而忽略其余的。

9999 is       b'10011100001111'
9999 % 2^8 is       b'00001111'

‘

因此，如果x=2^A和n=2^B组合了各个部分，那么

(X^2-2)%n

将是：(最后B位)(二进制)(2*A-1 '1's后面跟着a '0')

一些模块规则：

1) (a+b)mod(n) = amod(n)+bmod(N)

2) (a.b)mod(n) = amod(n).bmod(n)

所以你可以把你的方程转换成：

(x**2-2)%n ==> (x.x - 2)%n ==> (x%n)(X%n)- (2%n)

如果n总是大于2，则(2%n)等于2本身。

解(x%n)：

如果x和n总是2**值；如果x>n，则(x%n)= 0，如果x

答案要么是0-(2%n)，要么是x**2-(2%n)