階乗とは簡単に言えば 1 からその数まで順に掛け算した結果である。正しい定義は帰納的に 0 ! = 1, n ! = (n - 1) ! ×n とする。
Algorithm 等についても殆ど冪乗のそれと変わらないが, 問題は桁数の評価をどうするかである。桁数のことをあんまり考えずに Vector class を使って, 最高位の方で overflow が起こる度に, dig.addElement(new long); などとやるのも一つの手ではあろうが, それではかなり時間がかかるだろう。
実は表題にある Γ 函数 (Euler gamma function) というのがあって, これが非常に良い性質を持っているので, それを利用しているのである。
Γ 函数の定義は Γ(s) = ∫0∞e-xxs-1dx であるが, 有名な函数等式 Γ(s + 1) = sΓ(s) を満たし, しかも Γ(0) = 1 であるから, Γ(n + 1) = n! なので, Γ(s) が s の式として評価出来れば良いことになる。
こんなのをどうしたら評価できるのだろうなどと思うが, 実は James Stirling (1692--1770) の公式という非常に良い公式があるのだ。(実は Stirling は高次の項まで含む形式的漸近展開を示しただけで, 証明したのは Pierre Simon Laplace, 1749--1827 であるという)
公式は (s が充分大きい時) Γ(s) ≒ (2π)1/2ss-0.5e-s+μ(s) で, μ(s) = 1/(12s) - 1/(360s3) + 1/(1260s5) となる。μ(s) のところは難しいのだが, それ以外のところは log n と n - 1/2 から n + 1/2 迄の log x との積分の比較とから殆ど出てくる。係数 (2π)1/2 は John Wallis (1616--1703) の公式から求めることができる。
Friday, 5th May, 2000.
参考文献:
高木貞治, 解析概論, 改訂第三版, 岩波書店。