projectpn
projectpn
階乗は、とくに大きな数になると、計算が大変であるが、それを何とか近似できないものかと2011年の3月あたりから頑張ってみた結果。

基本的な考え方

階乗の計算で何が大変かといえば、当然値がすごく大きくなるということである。
ので、とりあえず対数を取ってみると、(以後、対数といえば断りのない限り自然対数です)
$\displaystyle \log(n!) \\ =\log(1 \times 2 \times \cdots \times n-1 \times n) \\ =\log(1)+\log(2)+ \cdots +\log(n-1)+\log(n) \\ =\sum^n_{k=1}\log(k)$
このように対数の和の形に直すことができる。
ここで、対数関数を積分してやったものと比べると、次の等式が成り立つことがすぐに分かる。
$\displaystyle \int^{n+1}_1 \log(x)dx>\sum^n_{k=1}\log(k)>\int^n_1\log(x)dx \\ \ [x(\log(x)-1)]^{n+1}_1>\sum^n_{k=1}\log(k)>[x(\log(x)-1)]^n_1 \\ (n+1)\log(n+1)-n>\sum^n_{k=1}\log(k)>n\log(n)-n+1$
つまり、
$\displaystyle (n+1)\log(n+1)-n>\log(n!)>n\log(n)-n+1$
という近似が得られる。
試しに計算してみると、n=100,n=1,000,000のとき、
$\displaystyle n=100 \\ 101\log(101)-100\sim 366.13 \\ 100\log(100)-99\sim 361.52 \\ n=1,000,000 \\ 1000001\log(1000001)-1000000\sim 12815525.37 \\ 1000000\log(1000000)-999999\sim 12815511.56$
といった感じで、「おおよその桁数が分かる」程度である。

評価の改良

n≧2のとき、以下の二つの等式が成り立つことは簡単に示せる。(グラフを描いて積分を面積で考えると直感的に理解できる)
$\displaystyle \int_{n-\frac{1}{2}}^n\log(n)-\log(x)dx>\int_n^{n+\frac{1}{2}}\log(x)-\log(n)dx \\ \int_{n-1}^{n-\frac{1}{2}}\log(x)-\log(n-1)dx>\int_{n-\frac{1}{2}}^n\log(n)-\log(x)dx \\
これを変形することで、
$\displaystyle \int_{n-\frac{1}{2}}^n\log(n)-\log(x)dx>\int_n^{n+\frac{1}{2}}\log(x)-\log(n)dx \\ \int_n^{n+\frac{1}{2}}\log(x)-\log(n)dx-\int_{n-\frac{1}{2}}^n\log(n)-\log(x)dx<0 \\ \int_{n-\frac{1}{2}}^n\log(x)-\log(n)dx+\int_n^{n+\frac{1}{2}}\log(x)-\log(n)dx<0 \\ \int_{n-\frac{1}{2}}^{n+\frac{1}{2}}\log(x)-\log(n)dx<0 \\ \int_{n-\frac{1}{2}}^{n+\frac{1}{2}}\log(x)dx<\log(n)$
および、
$\displaystyle \int_{n-1}^{n-\frac{1}{2}}\log(x)-\log(n-1)dx>\int_{n-\frac{1}{2}}^n\log(n)-\log(x)dx \\ \int_{n-1}^{n-\frac{1}{2}}\log(x)-\log(n-1)dx-\int_{n-\frac{1}{2}}^n\log(n)-\log(x)dx>0 \\ \int_{n-1}^{n-\frac{1}{2}}\log(x)dx-\frac{1}{2}\log(n-1)+\int_{n-\frac{1}{2}}^n\log(x)dx-\frac{1}{2}\log(n)>0 \\ \int_{n-1}^n\log(x)dx>\frac{1}{2}(\log(n-1)+\log(n)) $
が得られる。(最終式を直接示すのはちょっと厄介なのでこの示し方を用いた)
これを用いることで、
$\displaystyle \log(n!)=\log(1)+\sum_{k=2}^n\log(k) \\ >\sum_{k=2}^n\int_{k-\frac{1}{2}}^{k+\frac{1}{2}}\log(x)dx \\ =\int_{\frac{3}{2}}^{n+\frac{1}{2}}\log(x)dx \\ =[x(\log(x)-1)]^{n+\frac{1}{2}}_{\frac{3}{2}} \\ =(n+\frac{1}{2})\log(n+\frac{1}{2})-(n+\frac{1}{2})-\frac{3}{2}\log(\frac{3}{2})+\frac{3}{2} \\ =(n+\frac{1}{2})\log(n+\frac{1}{2})-\frac{3}{2}\log(\frac{3}{2})-n+1 $
および
$\displaystyle \log(n!)=\log(1)+\sum_{k=2}^n\log(k) \\ <\frac{1}{2}\log(2)+\sum_{k=3}^n\int_{k-1}^k\log(x)dx+\frac{1}{2}\log(n) \\ =\frac{1}{2}(\log(2)+\log(n))+\int_2^{n}\log(x)dx \\ =\frac{1}{2}(\log(2)+\log(n))+[x(\log(x)-1)]^n_2 \\ =\frac{1}{2}(\log(2)+\log(n))+n\log(n)-n-2\log(2)+2 \\ =(n+\frac{1}{2})\log(n)-\frac{3}{2}\log(2)-n+2
となるので、
$\displaystyle (n+\frac{1}{2})\log(n+\frac{1}{2})-\frac{3}{2}\log(\frac{3}{2})-n+1>\log(n!)>(n+\frac{1}{2})\log(n)-\frac{3}{2}\log(2)-n+2$
という近似式が得られる。
試しに計算してみると、n=100,n=1,000,000のとき、
$\displaystyle n=100 \\ 100.5\log(100)-\frac{3}{2}\log(2)-98\sim 363.7799 \\ 100.5\log(100.5)-\frac{3}{2}\log(\frac{3}{2})-99\sim 363.7127 \\ n=1,000,000 \\ 1000000.5\log(1000000)-\frac{3}{2}\log(2)-999998\sim 12815518.4260 \\ 1000000.5\log(1000000.5)-\frac{3}{2}\log(\frac{3}{2})-999999\sim 12815518.3575 $
となり、近似の精度が大幅に改善しているのが分かる。

補足

既に先人がもっと良い近似を与えていて、
スターリングの公式
$\displaystyle n!\sim\sqrt {2\pi n}(\frac{n}{e})^n \\ \Leftrightarrow \log(n!)\sim(n+\frac{1}{2})\log(n)+\frac{1}{2}\log(2\pi)-n$
という近似式がある。従って、このページを真面目に読んでいる人は時間を無駄にしたと思って差し支えない。
「階乗の近似」をウィキ内検索
最終更新：2012年04月29日 22:18