Entries

PCで円周率を計算したい人へ。

 PC上で円周率を計算するソフトと言えば、スーパーπがたぶん一番有名でしょう。
 「円周率 ソフト」でググれば一番上に来ますし。
 ですが……ハッキリ言いましょう。今時スーパーπは遅いです。遅すぎます。自分でテストしてみた結果、最速のソフトと比べて40倍は遅かったです。円周率計算目的には間違っても使用しないようにしましょう。ほぼ間違いなく情弱(バカ)扱いされますから。
 じゃあどのソフトが速いのかって? 実際にベンチして確かめてみました。

 今回使用するPCは、前にも報告した、ASUSのK55VD-3210Bという機種です。CUDAを使ってくれるような計算プログラムはまだ無いようなので、CPU(Core i5-3210M)・メモリ(DDR3 PC3-12800を4GB)のチカラをもって争うことになります(HDDの性能を考慮するほどの桁数は計算しませんでした)。64bitOSなので、対応ソフトが能力を活かしやすいことになるでしょう。
 一方使用するソフトは9種類。色々ググってまともに使えそうなもの(コンパイルせずに使えるもの)をピックアップしました(Vectorはマシなものが置いていないので普通にググることを推奨。円周率.jpのページが大いに参考になりました)。では、順番に見ていきましょう。
 なお、今回の測定時、「すっきり!! デフラグ」を利用して、常駐ソフトを極限まで削りました。また、以下の説明の中では、「桁数→秒数の順で表示」「MとかGとかは1024単位」「xは桁数、yは秒数」「logは自然対数」「ソフト名横の時間は1億桁計算の予想時間」ですのでご注意下さい。

1. HSP de 円周率(188年246日)
http://www.vector.co.jp/soft/win95/edu/se479047.html (Vector)
http://ysrken.blog.fc2.com/blog-entry-4.html (ブログでの紹介ページ)
 拙作……と言うより習作です。言うまでもありませんがカナリ遅いです。

桁数 秒数
1000 4.71
2000 6.56
3000 9.53
4000 13.67
5000 19.10
∴y=5.95e-7*x^2+1.9e-5*x+4.112000


2. 高速電子式計算機(69.5日)
http://hsp.tv/contest2007/list_n4.html (ソフト名で検索をかけて下さい)
http://blog.livedoor.jp/toropippi/archives/692774.html (ソースコードが読めます)
 いっちょまえにChudnovskyアルゴリズムを使っているせいか、拙作より圧倒的に速いです。しかし、乗算に筆算法を用いているせいで、オーダーがO(n^2)になってしまっています。勿体無い……。

桁数 計算終了
5120 0.015
10240 0.094
20480 0.265
40960 0.998
81920 3.760
163840 13.931
327680 57.065
655360 224.999
1310720 991.148
∴y=6.007584e-10*x^2


3. スーパーπ(37分33秒)
http://www1.coralnet.or.jp/kusuto/PI/super_pi.html (本家ページ)
http://www.techpowerup.com/downloads/366/ (ミリ秒単位で表示できるMOD版)
 最初にボロクソに言っていますが、SSEどころかMMXすら無い時期(1995年のプログラムなので。MMX搭載Pentiumが登場したのは1997年)にこの完成度で出せるのはハッキリ言って凄いです。アルゴリズムはGauss-Legendreの公式(AGM法)+FFTなので、オーダーはO(n*(log(n))^2)となっています。ふむふむ、実測結果もそのようになっているようですな。
 ちなみに、天然キャラも真っ青な純粋さ(拡張命令使わない的な意味で)から、CPUのシングルコア性能を調べる汎用なベンチとしてよく使われます(のだめカンタービレの作者が漫画化してました。どういうことなの……)。

桁数 計算終了 出力まで
16K 0.141 0.156
32K 0.281 0.297
64K 0.561 0.592
128K 1.185 1.263
256K 2.496 2.636
512K 5.444 5.741
1M 12.386 13.010
2M 28.064 29.422
4M 62.010 64.803
8M 139.683 145.517
16M 300.066 311.423
32M 654.468 678.289
∴y=6.640268e-8*x*log(x)^2


4. PAI Calculator(8分59秒)
http://www.vector.co.jp/soft/win95/hardware/se120394.html
 SuperPAIよりも2.5倍高速 と謳う謎のソフトウェアです。アルゴリズム自体はスーパーπと同じようなので、きっとSIMD化したのでしょう(1999年のプログラムだし)。で、実際に走らせてみたところ、2.5倍どころか4.2倍速かった。「流石Ivy!」と誇っていいのかはカナリ謎です。

桁数 時間
512K 1
1M 3
2M 8
4M 17
8M 36
16M 77
32M 166
∴y=1.589464e-8*x*log(x)^2


5. Ooura(8分16秒)
http://www.kurims.kyoto-u.ac.jp/~ooura/pi_fft-j.html
 元々はFFTのベンチマークのためのプログラムだとか。DLした中の、「pi_cs.exe」という32bitバイナリを使用しました。なんせ、64bit用にコンパイルし直すのが面倒というより無理(Intel C++ Compiler持ってねぇよ……)だったので。
 実行すると数値入力(length of FFT)を求められますが、打ち込んだ数値の4倍を計算桁数にする仕様なのでお間違えなく。
 計算アルゴリズム? AGM+FFTだけど?

length 桁数 時間
131072 524288 1
262144 1048576 3
524288 2097152 7
1048576 4194304 14
2097152 8388608 32
4194304 16777216 71
8388608 33554432 152
16777216 67108864 332
33554432 134217728 704
∴y=1.462067e-008*x*log(x)^2


6. PiFast(4分31秒)
http://numbers.computation.free.fr/Constants/PiProgram/pifast.html
 自分で最速と謳う(「the fastest windows program to compute pi」とサイトに書いてある)だけあってかなり速いです。ただしシングルコア。
 計算アルゴリズムはChudnovsky+FFTを使用。だったらオーダーは素直にO(n log(n)^3)……かと思いきや、documentをよく読むと「O(n)っぽく見えるけどだんだんO(n^2)に近づいていくよ!」と書かれています。更に、「桁数は2の累乗にするより10の倍数にした方がたぶん速いよ!」とも書かれています。……2の累乗で計算させてましたサーセン。

桁数 時間
131072 0.11
262144 0.25
524288 0.55
1048576 1.19
2097152 2.82
4194304 6.37
8388608 14.20
16777216 31.34
33554432 69.92
67108864 154.91
134217728 345.09
∴y=4.3309765e-10*x*log(x)^3


7. Quick pi(2分29秒)
http://members.shaw.ca/francislyster/pi/pi.html
 やっぱ計算はマルチコアだよネ!
 色々オプションは選べますが、今回は「桁数 -chudnovsky -threads:4 -stats」というコマンドラインオプションにしました(64bit版を使用。他のアルゴリズムも試しましたがやっぱりChudnovskyが一番速いことが判明)。ただ、速いのは良いのですが、なぜかCPU使用率が低いのがムカツキます(30%ぐらい)。手でも抜いているのかと。

桁数 時間
256k 0.14
512k 0.31
1m 0.70
2m 1.54
4m 3.45
8m 7.74
16m 17.14
32m 38.53
64m 89.40
128m 206.51
∴y=2.387083E-10*x*log(x)^3


8. y-cruncher(1分10秒)
http://www.numberworld.org/y-cruncher/
 本日の真打ちです。トップページでスーパーπとPiFastとQuick piを名指ししているのが笑えるのですが、流石に世界一は格が違った。スーパーπ・PiFastも元世界一だけどね
 まず凄いのは、複数環境に合わせて実行ファイルも分かれていること。64bit・AVX環境から32bit環境まで、合計7種類もの実行ファイルが存在し、実行時に自動判定で振り分けてくれるという仕掛け(今回は「x64 AVX ~ Hina」版を使用)。最適な環境で計算させてくれるとは粋ですなぁ。
 次に驚くのが、その計算速度。現在10兆桁で世界一(2013/02/09現在)を取るレベルなだけに、性能は折り紙付きなようで、32M(33554432桁。スーパーπでの最大桁数でもある)を僅か19秒で計算し終えます。いやいやおかしいだろ速すぎだろと。
 そして一番アレなのは、開発者が間違いなくアニオタだということ。なんですか、実行ファイル名にNagisaとかUshioとかって。KEISANは人生とでも言いたいんですか? 挙句にデフォルトの「Username.txt」の内容が、

#
# This file is used to specify a name, username, email, etc... that you would
# like to appear in the validation certificates that y-cruncher will create.
# This is used for identification purposes.
#
# Examples:
# Johnny Sun (Serotoninn)
# Haruhi Suzumiya (涼宮ハルヒ)
#
#
# Note the following rules:
# 1. It must be fewer than 1000 characters.
# 2. Only printable characters are allowed. (i.e. No control characters)
# 3. This file must be saved in Unicode format. (Not ASCII!!!)
# 4. International characters are allowed as long as they are in Unicode.
#


Username: None Specified - You can edit this in "Username.txt".


って……! なぜついでにジョン・スミスも書いてくれなかったんだよ
 そのせいか、こんなのとかこんなのとかがキャプ画で上がったりしています。嫁を自慢できて羨ましい
 計算アルゴリズムはChudnovsky+FFT。時間を測ったらなぜかO(n log(n)^2)だったのは王者の実力ということか。

桁数 Total Computation Time
1M 0.487
2M 0.993
4M 2.030
8M 4.136
16M 8.845
32M 19.266
64M 42.814
128M 94.030
256M 205.691
∴y=2.054290e-9*x*log(x)^2


9. TachusPI(55秒)
http://bellard.org/pi/pi2700e9/tpi.html
 本日のトリを飾るのはコイツ。ご覧の通り、無茶苦茶速いです。1億桁がまさか1分切るとは自分でも思わなかったもの。「すっきり!!デフラグ」を使わない普通の状態でも、

Using 3.25GiB of RAM
Computation to 100000000 digits, formula=Chudnovsky
Output file=[none], format=txt, binary result size=41.5MB
Binary Splitting
Depth=23, thread_level=1
mem max disk max operation compl lv
431M 431M 0 0 completed 100.0% 0
time = 44.204 s
Compute P, Q
287M 431M 0 0 completed
time = 0.619 s
Division
471M 471M 0 0 completed
time = 4.536 s
Sqrt
415M 471M 0 0 completed
time = 2.982 s
Final multiplication
730M 730M 0 0 completed
time = 2.029 s
Total time (binary result) = 54.387 s
Base conversion
414M 730M 0 0 completed
time = 10.877 s
Total time (base 10 result) = 65.268 s
tag cur local max global max (unit=41.52 MB)
mpx 0.00 0.00 0.00 (0.01 MB)
mpt 0.00 2.01 4.92 (204.33 MB)
fft 0.00 0.00 16.15 (670.63 MB)
fftstate 0.00 0.43 0.44 (18.38 MB)
fac 0.00 0.00 2.83 (117.50 MB)
sieve 0.00 0.00 0.12 (4.88 MB)
ntt 0.00 0.00 0.00 (0.00 MB)
nttdisk 0.00 0.00 0.00 (0.00 MB)
nttstate 0.00 0.00 0.00 (0.00 MB)
io_buf 0.00 0.00 0.00 (0.00 MB)
total 0.00 2.44 17.59 (730.51 MB)
disk 0.00 0.00 0.00 (0.00 MB)
disk I/O: read=0.00 write=0.00
FFT mul count=498710, lost limbs=2.9%, init_count=357, remaining init=0.3%
NTT mul count=0, lost limbs=0.0%, max lost=0.000 MB


といったタイムを出してくるような奴です。凄すぎ。さりげなく64bitOSしか使えませんが、作者が「32bitだと遅くなるから出さない(意訳)」と言っているのでこれは仕方がない。
 ちなみに、y-cruncherの中の人曰く、「いやこっちで長桁計算させたらy-cruncherに負けてるんだけど?(意訳)」とのこと(公式トップページ下のFAQからグラフが見れます)。グラフで分かるように、「1コアではTachusPIが強いけど多コアでは逆」「y-cruncherはLinux版よりWin版の方が微妙に速い」らしいです。
 計算(ryはChud(ry。Chudnovskyさん偉大すぎでしょ。

桁数 時間
1Mi 0.328
2Mi 0.718
4Mi 1.544
8Mi 3.214
16Mi 7.176
32Mi 16.146
64Mi 36.005
128Mi 82.774
256Mi 160.119
∴y=1.608701E-09*x*log(x)^2



 結論。y-cruncherかTachusPI、好きな方を使え(前者推奨)。


[おまけ]
 実はこの実験の前にも、y-cruncherで50億桁を計算させたことがあります。HDD併用で走らせた結果が、18699.798秒(5時間11分39.798秒)でした。じゃあTachusPIじゃどうなるのかと実験したところ、10時間ほどウンウン唸って計算した挙句、BSoD。Binary Splittingは2時間ほどでしたが、Divisionに5時間半Sqrtに3時間弱も掛かっていました。
(TachusPIの作者の名誉のために補足。BSoDの原因はsee.sysでした。パケット警察ェ……)

2012/2/26追記:
誤字を修正。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/38-7ddbee9c

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

10 ≪│2017/11│≫ 12
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数: