我很好奇是否有一個很好的方法可以做到這一點。我當前的代碼是這樣的：def factorialMod(n, modulus): ans=1 for i in range(1,n+1): ans = ans * i % modulus return ans % modulus但是似乎很慢！我也無法計算n！然后應用素數模數，因為有時n太大以至于n！顯式計算只是不可行。我還遇到了http://en.wikipedia.org/wiki/Stirling%27s_approximation，想知道是否可以在某種程度上使用它？或者，如何在C ++中創建一個遞歸的，記憶化的函數？
3 回答
慕尼黑5688855
TA貢獻1848條經驗 獲得超2個贊
將我的評論擴展為答案：
是的，有更有效的方法可以做到這一點。但是它們非?；靵y。
因此，除非您確實需要額外的性能，否則我建議您不要嘗試實現這些性能。
關鍵是要注意，模數（本質上是一個除法）將成為瓶頸操作。幸運的是，有一些非?？焖俚乃惴梢宰屇啻螆绦邢嗤螖档哪怠?/p>
使用乘法按不變整數進行除法
蒙哥馬利減少
這些方法之所以快速，是因為它們基本上消除了模量。
單獨使用這些方法應該可以使您獲得適度的加速。為了真正高效，您可能需要展開循環以實現更好的IPC：
像這樣：
ans0 = 1
ans1 = 1
for i in range(1,(n+1) / 2):
ans0 = ans0 * (2*i + 0) % modulus
ans1 = ans1 * (2*i + 1) % modulus
return ans0 * ans1 % modulus
但考慮到奇數次的迭代，并將其與我上面鏈接的方法之一結合起來。
有人可能會認為循環展開應該留給編譯器。我會反駁說，編譯器目前還不夠智能，無法展開這個特定的循環。仔細看看，您會明白為什么。
請注意，盡管我的回答與語言無關，但主要是針對C或C ++的。
江戶川亂折騰
TA貢獻1851條經驗 獲得超5個贊
如果要計算M = a*(a+1) * ... * (b-1) * b (mod p)，可以使用以下方法，如果我們假設可以進行加，減和乘快速運算（mod p），則運行時復雜度為O( sqrt(b-a) * polylog(b-a) )。
為簡單起見，假設(b-a+1) = k^2，是一個正方形。現在，我們可以將產品分成k個部分，即M = [a*..*(a+k-1)] *...* [(b-k+1)*..*b]。本產品中的每個因素都具有p(x)=x*..*(x+k-1)適當的形式x。
通過使用多項式的快速乘法算法（例如Sch?nhage–Strassen算法），以分而治之的方式可以找到多項式的系數p(x) in O( k * polylog(k) )?，F在，顯然有一種算法可以將替換k為相同的k次多項式中的點O( k * polylog(k) )，這意味著我們可以p(a), p(a+k), ..., p(b-k+1)快速計算。
C. Pomerance和R. Crandall在“ Prime number”一書中描述了將許多點代入一個多項式的算法。最終，當您擁有這些k值時，可以將它們相乘O(k)并獲得所需的值。
請注意，我們所有的操作都在執行(mod p)。確切的運行時間為O(sqrt(b-a) * log(b-a)^2 * log(log(b-a)))。
添加回答
舉報
0/150
提交
取消