分页： 1 / 1
#1 求模有快速算法吗？
发表于 ： 2024年 6月 10日 14:10
由 （ヅ）
特殊的除数,所有二进制位全是1,比如mod 7, mod 15, mod 31这样
发现这个运算非常慢
#2 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 12日 17:21
由 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呢？
#3 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 12日 17:40
由 han6
FoxMe 写了： 2024年 6月 12日 17:21
如果是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呢？
一回事，可以把模設為負一。
#4 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 12日 23:41
由 （ヅ）
FoxMe 写了： 2024年 6月 12日 17:21
如果是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呢？
这个本质上还是做除法，没有减少运算量？
#5 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 13日 00:01
由 （ヅ）
我的代码如下，怎么提速比较好？
def foo():
n = 132049
div = 2 ** n - 1
s = 10
for i in range(n - 2):
s = (s ** 2 - 1) % div
foo()
#6 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 13日 00:41
由 Caravel
（ヅ） 写了： 2024年 6月 10日 14:10
特殊的除数,所有二进制位全是1,比如mod 7, mod 15, mod 31这样
发现这个运算非常慢
需要多快，这个现代计算机一次都是ns级别的吧，
#7 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 13日 00:46
由 （ヅ）
Caravel 写了： 2024年 6月 13日 00:41
需要多快，这个现代计算机一次都是ns级别的吧，
上面那个例子你跑一下啊
我这里慢的很
#8 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 13日 01:33
由 Caravel
（ヅ） 写了： 2024年 6月 13日 00:46
上面那个例子你跑一下啊
我这里慢的很
你为啥要取这么大数字的模？这取完不就等于自己么
#9 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 13日 10:13
由 （ヅ）
Caravel 写了： 2024年 6月 13日 01:33
你为啥要取这么大数字的模？这取完不就等于自己么
被除数也很大唉
#10 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 14日 09:48
由 FoxMe
哪里做除法了？
（ヅ） 写了： 2024年 6月 12日 23:41
这个本质上还是做除法，没有减少运算量？
#11 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 14日 09:53
由 （ヅ）
FoxMe 写了： 2024年 6月 14日 09:48
哪里做除法了？
说得有道理
我跑了例子，这样可以提速到4x
#12 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 14日 12:10
由 （ヅ）
foxme这个办法蛮好，n越大越快
原算法: n = 132049 2939.754820799979
改进后: n = 132049 341.1524356000009
快9倍了
还能提速？
#13 Re: 求模有快速算法吗？
发表于 ： 2024年 6月 14日 12:14
由 （ヅ）
FoxMe 写了： 2024年 6月 12日 17:21
如果是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位