これを行う良い方法があるかどうか私は興味がありました。私の現在のコードは次のようなものです：
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 ++で再帰的なメモ化関数を作成するにはどうすればよいですか？
n は任意に大きくすることができます
まあ、任意nに大きくすることはできません- if 、 then (階乗の定義により、要因の1つであるため)。n >= mn! ≡ 0 (mod m) m
私の知る限り、正確なn << m値が必要であると仮定すると、アルゴリズムはこれ以上速くなりません。ただし、 の場合、次の恒等式を使用できます(ウィルソンの定理- @Daniel Fischer に感謝します!)n > m/2
乗算の数を約に制限するm-n
(m-1)! ≡ -1 (mod m) 1 * 2 * 3 * ... * (n-1) * n * (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m) ん！* (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m) ん！≡ -[(n+1) * ... * (m-2) * (m-1)] -1 (mod m)
n! (mod m)これにより、m-n-1乗算で計算する簡単な方法とモジュラー逆数が得られます。
def factorialMod(n, モジュラス):
ans=1
n <=係数//2の場合:
#階乗を普通に計算する(range()の右引数は排他)
i の範囲 (1,n+1):
ans = (ans * i) % モジュラス
そうしないと：
#n が大きい場合の Fancypants メソッド
for i の範囲 (n+1,係数):
ans = (ans * i) % モジュラス
ans = modinv(ans, モジュラス)
ans = -1*ans + モジュラス
リターン ans % モジュラス
上記の方程式を別の方法で言い換えることができます。次の ID を使用します。
方程式を次のように言い換えることができます
ん！≡ -[(n+1) * ... * (m-2) * (m-1)] -1 (mod m)
ん！≡ -[(n+1-m) * ... * (m-2-m) * (m-1-m)] -1 (mod m)
(用語の逆順)
ん！≡ -[(-1) * (-2) * ... * -(mn-2) * -(mn-1)] -1 (mod m)
ん！≡ -[(1) * (2) * ... * (mn-2) * (mn-1) * (-1) (mn-1) ] -1 (mod m)
ん！≡ [(mn-1)!] -1 * (-1) (mn) (mod m)
これは Python で次のように記述できます。
def factorialMod(n, モジュラス):
ans=1
n <=係数//2の場合:
#階乗を普通に計算する(range()の右引数は排他)
i の範囲 (1,n+1):
ans = (ans * i) % モジュラス
そうしないと：
#n が大きい場合の Fancypants メソッド
for i in range(1,modulus-n):
ans = (ans * i) % モジュラス
ans = modinv(ans, モジュラス)
#m は奇素数なので (-1)^(mn) = n が偶数なら -1、n が奇数なら +1
n % 2 == 0 の場合:
ans = -1*ans + モジュラス
リターン ans % モジュラス
正確な値が必要ない場合は、少し楽になります。スターリングの近似O(log n)を使用して、時間の近似値を計算できます( 2 乗によるべき乗を使用)。
最後に、これが時間が重要で、Python を使用している場合は、C++ に切り替えてみてください。個人的な経験からすると、1 桁以上の速度の向上を期待する必要があります。これは、ネイティブにコンパイルされたコードが優れているまさに一種の CPU バウンドのタイトループであるためです (また、何らかの理由で、GMP はPython の Bignum よりもはるかに細かく調整されています)。
私のコメントを答えに拡張する：
はい、これを行うより効率的な方法があります。しかし、それらは非常に厄介です。
そのため、追加のパフォーマンスが本当に必要でない限り、これらを実装しようとすることはお勧めしません。
重要なのは、モジュラス (本質的に除算) がボトルネック操作になることに注意することです。幸いなことに、同じ数に対してモジュラスを何度も実行できる非常に高速なアルゴリズムがいくつかあります。
これらの方法は基本的に弾性率を排除するため高速です。
これらの方法だけでも、適度なスピードアップが得られるはずです。本当に効率的にするには、ループを展開して 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
ただし、奇数回の繰り返しを考慮して、上記でリンクした方法の1つと組み合わせます。
ループ展開はコンパイラに任せるべきだと主張する人もいるかもしれません。私は、コンパイラは現在、この特定のループを展開するほど賢くないと反論します。よく見ると、その理由がわかります。
私の答えは言語に依存しませんが、主に C または C++ を対象としていることに注意してください。
ん！mod m は、単純な O(n) の代わりに O(n 1/2 + ε ) 操作で計算できます。これには FFT 多項式乗算を使用する必要があり、たとえば n > 10 4など、非常に大きな n の場合にのみ価値があります。
アルゴリズムの概要といくつかのタイミングは、http: //fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/で確認できます。
を計算したい場合は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) )。さて、kの同じ次数 k の多項式に点を代入するアルゴリズムがあるようです。O( k * polylog(k) )これは、高速に計算できることを意味しp(a), p(a+k), ..., p(b-k+1)ます。
多くの点を 1 つの多項式に代入するこのアルゴリズムは、C. Pomerance と R. Crandall による本「素数」で説明されています。最終的に、これらのk値が得られたら、それらを乗算しO(k)て目的の値を取得できます。
私たちのすべての操作が行われたことに注意してください(mod p)。正確な実行時間はO(sqrt(b-a) * log(b-a)^2 * log(log(b-a)))です。
私のコメントを拡張すると、これは m=(117 | 1117) の [100, 100007] のすべての n に対して約 50% の時間を要します。
Function facmod(n As Integer, m As Integer) As Integer
Dim f As Integer = 1
For i As Integer = 2 To n
f = f * i
If f > m Then
f = f Mod m
End If
Next
Return f
End Function
素数 m に対して n = (m - 1) の場合、http://en.wikipedia.org/wiki/Wilsonの s_theorem n! モッド m = (m - 1)
また、すでに指摘されているようにn！n > m の場合、mod m = 0
選択したプラットフォームの「mod」演算子が十分に高速であると仮定すると、主に、計算できる速度と、それn!を計算するために使用できるスペースによって制限されます。
次に、それは本質的に2ステップの操作です。
特に速度が重要な要素である場合は、物事を複雑にする必要はありません。一般に、ループ内で実行する操作はできるだけ少なくします。
n! mod m繰り返し計算する必要がある場合は、計算を実行する関数から出力される値をメモ化することをお勧めします。いつものように、これは古典的な空間と時間のトレードオフですが、ルックアップテーブルは非常に高速です。
最後に、メモ化と再帰（および必要に応じてトランポリン）を組み合わせて、物事を非常に高速にすることができます。