巨大な階乗の桁数を求めるプログラム

質問

10000!とか、123456!とかの桁数を求めるプログラムを教えて下さい。

スターリングの近似式というキーワードに当たりましたが、n!の値の近似式であって桁数ではないです。

回答No.9

f272 · ベストアンサー

#2 & #7です。

自分でも計測してみた。
「AMD Athron II X2 B24 3GHz/メモリ 4GB/Win7/Mingw32/gcc-4.5.0」という環境で gmp を使ったら 123456! が 0.379秒くらいで計算できたよ。

$ cat f.c
#include<stdio.h>
#include<gmp.h>
int main()
{
mpz_t rop;
unsigned long int op=123456;
FILE *fp;
int base=10;
fp=fopen("output.txt", "w");
mpz_init(rop);
mpz_fac_ui(rop, op);
return mpz_out_str(fp, base, rop);
}

$ gcc -I/usr/local/include -L/usr/local/lib f.c -lgmp

$ time ./a

real 0m0.379s
user 0m0.015s
sys 0m0.061s

$ wc -c output.txt
574965 output.txt

それから「すべての場合で正しい桁数が求まる」とは主張しません。
所詮エクセルで扱える程度の数しか考えてないので，この程度で勘弁してください。>#8

お礼

おお！わざわざプログラムまで載っけていただきありがとうございます。
先ほど別の方の解答に合ったように、正確さと計算量はトレードオフにあるらしく、正確な値を求めるにはこのように数を一度求めてから数えるしか無いようですね…
ただこの方法は大きい桁数でも凄く早く計算できるのですね、どうもありがとうございます！

回答No.10

Tacosan

おっと, gmp に「階乗を求める関数」があったんですね＞#9. #8 は「地道にかけ算した」結果でございます. あと, 誤差についてもそれで了解.

ところで, この質問者は何をしたいんだろう. もとの質問では「桁数を求める」となっているのに, #4 への補足では「全桁正確に計算したい」ようにも読める. どっちだ....

お礼

私としては正確に桁数を計算したいという意味で言いました。
近似すると正確ではなくなってしまうのではないかと思い、このような発言になりました。
誤解を招くようですみませんでした。

回答No.8

Tacosan

ちなみに「Core i7-2600/メモリ 8GB/Debian6.0/gcc-4.4.5くらい」という環境で gmp を使ったら 123456! が 1.7秒くらいで計算できた. gmp を使わず手組だと OpenMP を使っても 2.5秒くらいかかってる. む～, どこに手を入れたものだか....

なお, ぎりぎりまで考えると「スターリングの近似式を使って確実に桁数が求まる」とはなかなか言えないんじゃないでしょうか＞#7. 計算誤差を無視したとしても, 所詮は「近似式」なので「無限に多くの場合で正しい桁数がわかる」とは言えても「すべての場合で正しい桁数が求まる」というのは難しいはず. 正直に言えばどう示せばいいかわからない.

お礼

gmpというのは、GNU MP Libraryの事ですね。
このようなものがあると初めて知りました。
任意の長さの整数が宣言できるとのことで、これがあればC言語でも全ての桁を計算し、そこから正確な桁数を求めることが出来るのですね。
ありがとうございます、今度実際に書いてみることにします。

回答No.7

f272

#２です。
常用対数で計算すると誤差があるように書いている人がいるけど，適当に誤差評価を行っても#2で書いた方法だと７桁の数の階乗は正しく計算できるよ。
で，もう少しまじめに考えてみたら
=A1*LOG(A1)+0.5*LOG(2*PI()*A1)+(-A1+1/(12*A1))/LN(10)
でも大丈夫だったね。エクセルでA1に1048576と入れて上の式を計算すると
5.857669213400840E+06
となり，この数値を切り上げて5857670桁ということがわかる。スターリングの近似式ですね。ちゃんと誤差も考えているので１桁のずれもありません。

お礼

なるほど…誤差評価を行えば凄く上手くいくのですね。
ちょっと式が理解できないので、後日じっくり読ませていただきます。
どうもありがとうございました。

回答No.6

ki073

No.5で書かれているとおりですが、
Core Duo 1.66GHzと余り速くないパソコンでの計算時間だけを補足しておきますと
全桁計算では10000!で1.6秒、30000!で18秒です。
Logを使ったものは、10000!で0.019秒、123456!で0.27秒です。
いずれもRubyでの速度ですので、コンパイラなど使うともう少し速くなるはずです。

Logを使った方も、理論的には全桁計算と同じ結果になるはずですが、計算誤差の蓄積があり、微妙にずれることがあります。
No.4のLogによる計算は倍精度浮動小数点での計算です、実用上問題はない範囲だと思うのですが。

どれくらいの精度を求めるかです。１桁くらいの微妙なずれを許容するならLogによる方法、許容できないのならNo.1の方法しかありません。

お礼

なるほど、思っていた以上に早いのですね。

ただ、問題では最大１０桁までを対象とすると言っていました。
今実際にrubyで１０桁で動かしてみましたが１０分以上たっても終わる気配がありません。
ですが今度C言語で書き直してやってみることにします。どうもありがとうございました。

回答No.5

tatsu99

あなたが、どうしてそのようなことをなさりたいのか、その背景を述べて頂ければ
何か解決の糸口がつかめるかも知れません。
NO2,No3,No4の方のされていることは、基本的には全て同じことです。
＞スターーリングの近似式というキーワードに当たりましたが、n!の値の近似式であって桁数ではないです。
とのことですが、NO2,No3,No4の方の行なっていることは、スターーリングの近似式よりは、
もっと正確です。
何故、常用対数（log）をとると、桁数がわかるかということですが、
Xの常用対数（log）を求める言うことは、10を？乗するとXになるかという、？の値を求めることです。
１０の１乗＝１０
１０の２乗＝１００
１０の３乗＝１０００
となるので
１０のlogをとると１
１００のlogをとると２
１０００logをとると３
になり、結果的にその桁数がわかることになります。

No1の方の行なわれている方法が、もっとも正確な方法ですが、
時間がかかります。
この案件については、正確さと結果を求めるスピードとは、トレードオフの関係にあることを
理解してください。（両方を満足する解決法はないということです）

もし、123456！とかの階乗の上限値が予め、決まっているなら、それをＸとすると、
１の階乗の桁数を計算し、その桁数を保存。
２の階乗の桁数を計算し、その桁数を保存。
・・・
Ｘの階乗の桁数を計算し、その桁数を保存。
を非常に時間がかかりますが、これを予め行なっておき、ファイルなどに格納しておく方法
が考えられます。
そうすると１，２、。。。、Ｘの値に対し、その結果の桁数が表引き出来るので、
それなりに、早い結果を得ることが出来ます。

お礼

この問題はちょうどプログラミングのテストで、最後に任意課題として出ていて、正攻法でやるしか思いつかなくて悔しかったので質問させていただきました。

>この案件については、正確さと結果を求めるスピードとは、トレードオフの関係にあることを
理解してください。（両方を満足する解決法はないということです）
なるほど、やはりどちらも満たすような解法はないということですね…
数そのものではなく桁数だけなら実は凄い解法があるんじゃないか？と思っていました。
どうもありがとうございます。

回答No.4

ki073

ANo.2と同じ計算をやってみましたが、
(1..10000).inject(0.0){|r, a| r+Math.log10(a)}.ceil
-> 35660
(1..30000).inject(0.0){|r, a| r+Math.log10(a)}.ceil
-> 121288
(1..123456).inject(0.0){|r, a| r+Math.log10(a)}.ceil
-> 574965

近似じゃない全桁計算では
(1..30000).inject{|r, a| r*a}.to_s.length
-> 121288
同じ答えですね。
さすがに123456!は時間がかかりすぎて全桁計算はやめましたが。

補足

その時間がかかりすぎるような事をやりたいので、何か良い方法はございませんでしょうか？

回答No.3

rinkun

値の近似が出来れば常用対数を取れば桁数がおおよそ分かりますが。
# 正確にだとズレがあるか

補足

どうして常用対数を取ることで桁数が解るのでしょうか？
私はあんまり数学に詳しくないので出来ません…

回答No.2

f272

桁数を求めるだけならエクセルVBAでもできる。

Sub ndigits()
sum = 0
For i = 1 To 10000
sum = sum + Log(i)
Next i
Range("a1") = Application.RoundUp(sum / Log(10), 0)
sum = 0
For i = 1 To 123456
sum = sum + Log(i)
Next i
Range("a2") = Application.RoundUp(sum / Log(10), 0)
End Sub

補足

ええと…これは何をやっていられるのでしょうか？
logが出てくるようなのですが？

回答No.1

ki073

有効桁数の大きくできるプログラム言語を使えば簡単に求められます。
Rubyで計算しましたが、
(1..10000).inject{|r, a| r*a}
で10000!が計算できます。35660桁でした。検証はしていませんが、バグが無ければ正しいはずです。

補足

すみません、速度を気にするので、できる限り実際に値を求めることはしたくないのです。