求模有快速算法吗？

[（ヅ）]

特殊的除数,所有二进制位全是1,比如mod 7, mod 15, mod 31这样

发现这个运算非常慢

[FoxMe]

如果是mod 2^n - 1,把x写成二进制：

x = ... b_{2n-1} ... b_{n+1} b_{n} b_{n-1} ... b_1 b_0

x mod 2^n - 1
= b_{n-1} ... b_1 b_0
+ b_{2n-1} ... b_{n+1} b_{n}
+ ... mod 2^n - 1

应该很方便。我再出个题，如果是mod 2^n + 1呢？

[han6]

如果是mod 2^n - 1,把x写成二进制：

x = ... b_{2n-1} ... b_{n+1} b_{n} b_{n-1} ... b_1 b_0

x mod 2^n - 1
= b_{n-1} ... b_1 b_0
+ b_{2n-1} ... b_{n+1} b_{n}
+ ... mod 2^n - 1

应该很方便。我再出个题，如果是mod 2^n + 1呢？

一回事，可以把模設為負一。

[（ヅ）]

如果是mod 2^n - 1,把x写成二进制：

x = ... b_{2n-1} ... b_{n+1} b_{n} b_{n-1} ... b_1 b_0

x mod 2^n - 1
= b_{n-1} ... b_1 b_0
+ b_{2n-1} ... b_{n+1} b_{n}
+ ... mod 2^n - 1

应该很方便。我再出个题，如果是mod 2^n + 1呢？

这个本质上还是做除法，没有减少运算量？

[（ヅ）]

我的代码如下，怎么提速比较好？

def foo():
n = 132049
div = 2 ** n - 1
s = 10
for i in range(n - 2):
s = (s ** 2 - 1) % div

foo()

[Caravel]

特殊的除数,所有二进制位全是1,比如mod 7, mod 15, mod 31这样

发现这个运算非常慢

需要多快，这个现代计算机一次都是ns级别的吧，

[（ヅ）]

需要多快，这个现代计算机一次都是ns级别的吧，

上面那个例子你跑一下啊

我这里慢的很

[Caravel]

上面那个例子你跑一下啊

我这里慢的很

你为啥要取这么大数字的模？这取完不就等于自己么

[（ヅ）]

你为啥要取这么大数字的模？这取完不就等于自己么

被除数也很大唉

[FoxMe]

哪里做除法了？

这个本质上还是做除法，没有减少运算量？

[（ヅ）]

哪里做除法了？

说得有道理

我跑了例子，这样可以提速到4x

[（ヅ）]

foxme这个办法蛮好，n越大越快

原算法: n = 132049 2939.754820799979
改进后: n = 132049 341.1524356000009

快9倍了

还能提速？

[（ヅ）]

如果是mod 2^n - 1,把x写成二进制：

x = ... b_{2n-1} ... b_{n+1} b_{n} b_{n-1} ... b_1 b_0

x mod 2^n - 1
= b_{n-1} ... b_1 b_0
+ b_{2n-1} ... b_{n+1} b_{n}
+ ... mod 2^n - 1

应该很方便。我再出个题，如果是mod 2^n + 1呢？

b_{n-1} ... b_1 b_0
- b_{2n-1} ... b_{n+1} b_{n}
+ b_{3n-1} ... b_{2n+1} b_{2n}
-... mod 2^n + 1

其实最多就2n位