10

階乗への私のアプローチは次のとおりです。

def factorial(n):
    '''Returns factorial of n'''
    r = 1
    for i in range(1, n + 1):
        r *= i
    return r

かなり簡単だと思いますが、100000 のような大きな数には時間がかかるため、もっと効率的なものを作成できると思います。私の質問は、ありますか? math.factorial() もよくありません。ほぼ同じ時間がかかります。

4

9 に答える 9

3

近似だけが必要な場合は、ラマヌジャンの階乗近似の方がスターリングの近似よりも正確であると考えられています。

正確なものが必要な場合 (または必要な場合) は、GNU Multiple Precision ライブラリである GMP を試すことができます。Python での多数の素数性のテストに使用して成功しました。

于 2013-05-02T00:02:29.037 に答える
1

したがって、明示的なループではなく reduce 関数を使用できます。

>>> from functools import reduce
>>> mul = int.__mul__
>>> len(str(reduce(mul, range(2,100001), 1)))
456574
>>>

Python 2 では、 longs: long.__mul__、およびlen(str(reduce(mul, range(2L,100001L), 1L)))

于 2013-05-02T06:47:53.463 に答える
1

真の階乗値 n が本当に必要になるのは、実際には珍しいことです! 多くのアプリケーション分野で。多くの場合、階乗の自然対数を使用する方がより現実的です。階乗は、ものの組み合わせを選択する確率に関連する値を計算するために最もよく使用されるため、ログをより良い代替手段として使用できないアプリケーションは考えられません。

計算する一般的なことは、二項係数 (nk) = n! の選択などの階乗に基づく確率です。/ (k!(nk)!)。これが階乗の比率であるとすると、さまざまな対数階乗近似の 1 つを使用して確実に計算されます。また、多くの確率計算を行う場合は、1 未満の非常に広い範囲の数値が含まれることが多いため、対数領域で行うのが一般的に最善です (確率をデシベル単位で測定します)。ログバージョンが使用されていない場合は浮動小数点表現。

ETJaynes は有名な数学者であり、確率論の専門家でした。私は彼の著書「Probability Theory: The Logic of Science」を、このトピックと対数確率を使用したベイジアン推論と情報理論に関する非常に読みやすい情報源としてお勧めします。

于 2019-02-17T09:38:11.013 に答える
0

ガンマ関数 ( math.gamma(x)) を返すこともできますが、おそらく for ループで階乗を生成する方が速いでしょう。

于 2013-05-01T20:55:11.783 に答える
0

The slowdown in caused by a quadradic effect: as n gets larger you have to do more multiplications, but you also have to multiply larger numbers.

Finding a better algorithm won't be easy. You can try to exploit symmetries (as in FFT). It could also well pay to do multiplications in a different order, with intermediate results, such that you end up with multiplying only a few very big numbers at the end, but I haven't thought that to the end. In any case, you will have to find a law to exploit.

Look here for further inspiration.

于 2013-05-01T20:59:24.450 に答える