階乗を計算するための多くのアルゴリズムを説明しているこのページを見つけました。残念ながら、説明は簡潔であり、アルゴリズムの背後にある基本原理を理解するために、ソース コードの行ごとにふるいにかけようとは思いません。
階乗を計算するためのこれらの (または他の高速な) アルゴリズムのより詳細な説明を教えてくれる人はいますか?
編集: このページでは、素因数分解の方法について説明します。これは、最高のパフォーマンスを発揮するすべての階乗アルゴリズムに共通の手法です。また、Python の優れたサンプル コードも含まれています。著者はバイナリ分割の説明にリンクし、 Journal of Algorithmsの記事(「階乗計算の複雑さについて」) を参照しています。
Richard Fateman によるこの論文 (PDF リンク)を参照してください。コード サンプルは Lisp で書かれていますが、いずれにせよ、秘密の多くは、実行しなければならない bignum (任意精度の整数) 計算の数を最小限に抑えることに要約されます。
当然のことながら、bignums を必要としない/持っていない場合、それは些細なことです。ルックアップ テーブルまたは単純なループのいずれかで問題ありません。
編集：おおよその答えを使用できる場合は、 を合計するlog(k)かk = 2 ... n、由緒あるスターリング近似を使用して、階乗の対数を直接計算できます。オーバーフローを避けるために、可能な限り対数を使用する必要があります。特に、スターリングの近似を単純に適用すると、オーバーフローする必要のない多くの場所でオーバーフローが発生します。
別の方法もあります。この方法について詳しく説明します ここでは、少しの足し算と引き算で掛け算の量を半分にします。おそらく、最初に示した方法が必要であり、2 番目に示した方法は、理解できれば興味深い読み物です。