正しい円周率1万桁

[waki]

[1] 質問文
　[1.1] 正しい円周率1万桁を求めるプログラムの高速化をしたいです。
　[1.2] 自分で作ったプラグラムが長いのでtxt形式で添付させてもらいます。


　[1.3] とくにエラーなどはないのですが、実行すると1分以上かかってしまします。
　[1.4] そこで、どうにかして出来る限り早く(できれば数秒で)正しい円周率を出したいのですが、これ以上でどう改善してよいかわかりまん。

[2] 環境 　
　[2.1] OS ： Windows
　[2.2] コンパイラ名 ： gcc

[3] その他
　・構造体はまだ習っておらず、C言語を始めてから半年ほどです。
　・ライブラリはstdio.hでお願いします。
　・補足ですがマチンの公式を用いています。
どうか、よろしくお願いします。

[Dixq (管理人)]

初めまして、wakiさん。
非常にわかりやすい質問をありがとうございます。
質問の意図・内容はしっかり伝わったのですが、肝心のマチンの公式を知らないので＾＾；プログラムを見てわかる範囲のみ気づいた効率化出来る箇所を書いておきます。
（マチンの公式による計算式を書いていただける何かレスが付くかもしれませんが・・、式が多いとちょっと大変ですよね）

まず、グローバル変数は宣言と同時に0で初期化されるので、

for(s = 2; s <= MAX-1; s++){
a = 0;
}

このような処理の必要がありません。
また、前に入れたデータを初期化したい時は、http://www.google.co.jp/search?rlz=1C1G ... 8&q=memsetを使うと短くかけていいかもしれません。

後、時間がかかっているのはやはり二重ループの中のようです。
計算量が多いので致し方ない気がしますが、
私が考えられるのは、何度も同じ計算をしている部分があるので、
同じ計算結果になるものは、一旦変数に計算結果を入れ、それを共通して使うようにすれば
計算量が減ると思います。

後、何の助けにもならないかもしれませんが、ただ真っ黒の画面でいつ計算が終わるのか待つのも面倒なので、
こんなもの作ってみました。

http://dixq.net/code/ForWaki1.cpp

これコンパイルしてみて下さい。今どれ位計算が出来ているのか表示されます。
追加下部分は
//ココ
とかいてある行だけなので、確認したい時は「ココ」で検索するなどしてみて下さい。

[waki]

アドバイスありがとうございます。参考にさせてもらいつつ頑張って改良してみます。
このたびはありがとうございました。

[ibis]

似た文(特に複文)がいっぱいありますが、まずはインライン関数かマクロを使ってそれをまとめるといいです。
そうすると、関数(又はマクロ)を最適化するだけで、その関数(又はマクロ)を呼んでいる全ての箇所が最適化されますので。
それをせずに全箇所を最適化するのはかなり手間がかかりますからね。

最適化については、例えばこんな感じでしょうか。
・printf関数がいっぱい並んでいるところを、一つのprintf関数だけで済ませる
・同じ計算を2度以上するよりも、計算結果を変数に入れておいて使いまわす(dexqさんもこれを言ってますね。例えばa[j] + b[j] + f[j] の計算を各jに対して3回やってます。)
・ループ条件を出来る限り0との比較にする(例えばj >= 1; を j; にできます。)
　ポインタ演算を使えば、ループ条件を全て0との比較にできて、配列のアドレス計算も速くなります。

[waki]

詳しくありがとうございます。是非参考にさせていただきます。

[組木紙織]

1分以上かかるのを数秒で終わらせたいのなら、環境を変えるか、アルゴリズムを変えるのどちらか
(または両方)をしたほうが良いと思います。
小手先の高速化は多分無意味です。

参考リンク
[パズルハウス]
http://homepage3.nifty.com/puzzlehouse/
[Wikipedia マチンの公式]
http://homepage3.nifty.com/puzzlehouse/



/*************/
追記 1
パズルハウスのリンクは上から３段目の左側にあるπの計算に挑戦を見て欲しいと思っていっています。
追記2
正確な値をリテラルとしてソースコードに埋め込むのが一番速いと思います。

[toyo]

Google code searchで探してみました
http://www.google.com/codesearch/p?hl=e ... %20formula

そのままだとコンパイルできなかったので修正して実行しましたが私のパソコンでは1万桁が数秒で出ました

[たいちう]

2年前に1億桁に挑戦しましたが、100万桁に12時間かかり、それ以上縮まなかったのでやる気がなくなりました。
その時の記録は1万桁だと3.594秒。1万桁だけがターゲットならばもっと速くできる可能性はあると思いますが。

さて最適化についてですが、まずGetTickCount()などで時間を計りましょう。
色々試行錯誤することになりますが、予想に反して遅くなることもあります。
その時に時間で判断して、変更前に戻すためです。思い込みで最適化したつもりにせず、
正しく計測して結果を受け止めましょう。

次に配列の使い方ですが、配列の1つの要素に1桁分の数字を使っているようですね。
1つの要素に5桁分の数字を使うように変更するれば、計算の量も約1/5になります。
ここを、もう少し分かりやすい例で説明します。
時分秒の加減算のプログラムを作ることを考えてください。

int h, m, s; // h:m:s で時刻を表す方法
int h1, h2, m1, m2, s1, s2 // h1h2:m1m2:s1s2 のように、時分秒の1の位と10の位を分ける方法

両者の間には、h = h1 * 10 + h2 が成り立ちます。
前者と後者はどちらを選ぶかは場合によりますが、通常は前者でしょう。
使う変数の数も少ないですが、計算の量も少なくなります。

小数を5桁毎の多倍長で表すと、次のようなものになります。
int pi[2001]; // 2001 = 1 + 10000 / 5ですが、実際は余裕を持って定義してください。
pi[0] = 3
pi[1] = 14159
pi[2] = 26535
...

時刻の計算は60進数でしたが、5桁の多倍長は100000進数として考えます。
この変更と、既に指摘されている関数化を進めれば、プログラムは大分見やすくなり、
さらなる改善点も見つかりやすいでしょう。