我怎样才能计算得更快 (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得更快？

Answer 1

一些模块规则：

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

2) (ab)mod(n) = amod(n).bmod(n)

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

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

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

解决 (x%n) :

如果 x 和 n 总是在 2**value 中；如果 x > n 那么 (x%n)= 0 是答案，如果 x < n (x%n)=x

所以答案是 0-(2%n) 或 x**2-(2%n)

Answer 2

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

如果 2^N 是（二进制）1 后跟 N 个零，则 (2^N)^2 是（二进制）1 后跟 2N 个零。

2^3 squared is b'1000000'

如果您有一个数字 2^K（二进制 1 后跟 K 个零），那么 2^K - 2 将是 K-1 1s（一个）后跟一个零。

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”后跟一个“0”）

Answer 3

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

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

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 整数具有无限精度，因此您永远无法像在其他语言中那样完全左移一点.