No.9ベストアンサー
- 回答日時:
#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
- 回答日時:
おっと, gmp に「階乗を求める関数」があったんですね>#9. #8 は「地道にかけ算した」結果でございます. あと, 誤差についてもそれで了解.
ところで, この質問者は何をしたいんだろう. もとの質問では「桁数を求める」となっているのに, #4 への補足では「全桁正確に計算したい」ようにも読める. どっちだ....
私としては正確に桁数を計算したいという意味で言いました。
近似すると正確ではなくなってしまうのではないかと思い、このような発言になりました。
誤解を招くようですみませんでした。
No.8
- 回答日時:
ちなみに「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
- 回答日時:
#2です。
常用対数で計算すると誤差があるように書いている人がいるけど,適当に誤差評価を行っても#2で書いた方法だと7桁の数の階乗は正しく計算できるよ。
で,もう少しまじめに考えてみたら
=A1*LOG(A1)+0.5*LOG(2*PI()*A1)+(-A1+1/(12*A1))/LN(10)
でも大丈夫だったね。エクセルでA1に1048576と入れて上の式を計算すると
5.857669213400840E+06
となり,この数値を切り上げて5857670桁ということがわかる。スターリングの近似式ですね。ちゃんと誤差も考えているので1桁のずれもありません。
なるほど…誤差評価を行えば凄く上手くいくのですね。
ちょっと式が理解できないので、後日じっくり読ませていただきます。
どうもありがとうございました。
No.6
- 回答日時:
No.5で書かれているとおりですが、
Core Duo 1.66GHzと余り速くないパソコンでの計算時間だけを補足しておきますと
全桁計算では10000!で1.6秒、30000!で18秒です。
Logを使ったものは、10000!で0.019秒、123456!で0.27秒です。
いずれもRubyでの速度ですので、コンパイラなど使うともう少し速くなるはずです。
Logを使った方も、理論的には全桁計算と同じ結果になるはずですが、計算誤差の蓄積があり、微妙にずれることがあります。
No.4のLogによる計算は倍精度浮動小数点での計算です、実用上問題はない範囲だと思うのですが。
どれくらいの精度を求めるかです。1桁くらいの微妙なずれを許容するならLogによる方法、許容できないのならNo.1の方法しかありません。
なるほど、思っていた以上に早いのですね。
ただ、問題では最大10桁までを対象とすると言っていました。
今実際にrubyで10桁で動かしてみましたが10分以上たっても終わる気配がありません。
ですが今度C言語で書き直してやってみることにします。どうもありがとうございました。
No.5
- 回答日時:
あなたが、どうしてそのようなことをなさりたいのか、その背景を述べて頂ければ
何か解決の糸口がつかめるかも知れません。
NO2,No3,No4の方のされていることは、基本的には全て同じことです。
>スターーリングの近似式というキーワードに当たりましたが、n!の値の近似式であって桁数ではないです。
とのことですが、NO2,No3,No4の方の行なっていることは、スターーリングの近似式よりは、
もっと正確です。
何故、常用対数(log)をとると、桁数がわかるかということですが、
Xの常用対数(log)を求める言うことは、10を?乗するとXになるかという、?の値を求めることです。
10の1乗=10
10の2乗=100
10の3乗=1000
となるので
10のlogをとると1
100のlogをとると2
1000logをとると3
になり、結果的にその桁数がわかることになります。
No1の方の行なわれている方法が、もっとも正確な方法ですが、
時間がかかります。
この案件については、正確さと結果を求めるスピードとは、トレードオフの関係にあることを
理解してください。(両方を満足する解決法はないということです)
もし、123456!とかの階乗の上限値が予め、決まっているなら、それをXとすると、
1の階乗の桁数を計算し、その桁数を保存。
2の階乗の桁数を計算し、その桁数を保存。
・・・
Xの階乗の桁数を計算し、その桁数を保存。
を非常に時間がかかりますが、これを予め行なっておき、ファイルなどに格納しておく方法
が考えられます。
そうすると1,2、。。。、Xの値に対し、その結果の桁数が表引き出来るので、
それなりに、早い結果を得ることが出来ます。
この問題はちょうどプログラミングのテストで、最後に任意課題として出ていて、正攻法でやるしか思いつかなくて悔しかったので質問させていただきました。
>この案件については、正確さと結果を求めるスピードとは、トレードオフの関係にあることを
理解してください。(両方を満足する解決法はないということです)
なるほど、やはりどちらも満たすような解法はないということですね…
数そのものではなく桁数だけなら実は凄い解法があるんじゃないか?と思っていました。
どうもありがとうございます。
No.4
- 回答日時:
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.2
- 回答日時:
桁数を求めるだけならエクセル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
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Ruby プログラミングについてです。教えていただきたいです。 実行例のように、整数xが1から12までにつき、 2 2022/12/19 22:47
- JavaScript Javascript で、0000 から 9999 までの表を作りたい。 6 2022/09/11 14:47
- Visual Basic(VBA) vba 隣のセルに値がある行だけ関数をコピー&ペーストしたい A1 100001 A2 100002 1 2023/01/28 14:29
- Visual Basic(VBA) 【再々投稿】VBAのプログラムで動作しなくて困っています 8 2022/10/14 09:06
- 数学 tan(z)をローラン展開して tan(z)=-1/(z-π/2)+(1/3)(z-π/2)+… と 14 2023/01/17 10:33
- 数学 これまでに愚かな回答者を何人も見てきました。 それでも私は問うてみたい。 京都大学の入試問題に 「 6 2023/05/01 14:06
- 物理学 「NHKの時報の音は、振動数が440Hzです。この音の波長を求めましょう。ただし、音の伝わる速度を3 6 2023/03/02 18:24
- JavaScript 最小二乗法 2 2023/01/01 20:57
- Ruby 英数字を含む文字列(0-9,A-Z)の桁数圧縮をするには 5 2022/06/28 18:15
- 数学 2022 11.11 09:45に投稿した質問に対する2022.11.11 18:40に頂いた解答に 3 2022/12/23 21:28
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
c languageで 簡単な質問があ...
-
16進数 加算 減算 C言語
-
ExcelでPC(パソコン)によって...
-
O(n log n)について2
-
VB.net Double と...
-
有効数字について 以前質問をし...
-
z80について
-
EXCELの関数"STDEV(標準偏差)"...
-
VBAでミリ秒まで出力する方法
-
三菱シーケンサ(Aシリーズ)で...
-
乱数 なぜ剰余を使うのか
-
距離から緯度経度を求める方法
-
加算と減算で乗算と除算を表現...
-
初心者です。 C++ついて
-
最大50桁の実数の和・差・積を...
-
8・16進数の引き算を教えてくだ...
-
【VBA、VBS】何故False・・・?
-
2038年問題 日付算出
-
データ型 double の桁数について
-
チェックデジットについて
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
O(n log n)について2
-
16進数 加算 減算 C言語
-
c languageで 簡単な質問があ...
-
VB.net Double と...
-
”/”を使わずに割り算したいんで...
-
三菱シーケンサ(Aシリーズ)で...
-
ExcelのINT関数の計算結果がお...
-
有効数字について 以前質問をし...
-
ExcelでPC(パソコン)によって...
-
除算を使わずに10で割りたい。
-
EXCELの関数"STDEV(標準偏差)"...
-
floatの有効桁数
-
VBAでミリ秒まで出力する方法
-
100桁の計算ができなくて困って...
-
2進数の足し算(C言語)
-
VB6.0での小数点の扱いについて
-
VBAでの割り算の余りの求め方
-
コンピューターは指数関数をど...
-
距離から緯度経度を求める方法
-
BCD・HEX・BINについて
おすすめ情報