TCC の作者であるところの Fabrice Bellard という人は何やらものすごくて、 TCC のスライドにも書いたように、 qemu とか ffmpeg の作者であると同時に、πの任意桁を比較的高速に求めるアルゴリズムを開発したり、πをたくさんの桁数計算して、8ヶ月ほど世界一の記録を持っていた人だったりもします。
でまぁそのへんの話。
http://en.wikipedia.org/wiki/Chronology_of_computation_of_%CF%80
あたりを見るとわかる通り、世界記録は2002年からずっと、1.2兆桁くらいってのが更新されてなかったのですが、2009年に 2.6兆、2.7兆、と来て、2010年に5兆と来ているみたいです。
2009年の最初の2.6兆というのは T2K Open Supercomputer とかいう 640 ノードとかあるスパコンによる記録で、まあアカデミックな感じなわけです。
で、それに少し遅れてるけどほとんど同時に計算してたのが件の Fabrice Bellard で、記録の更新量は少なかったものの、
- Core i7 CPU at 2.93 GHz
- 6 GiB (1) of RAM
- 7.5 TB of disk storage using five 1.5 TB hard disks (Seagate Barracuda 7200.11 model)
- 64 bit Red Hat Fedora 10 distribution
などという、ご家庭のハイエンド程度のコンピュータで計算したというのがとんでもないということのようです。まあ HDD はちょっと異様な感じがするものの、テレビとかやたら保存しまくってる人は結構このくらい持ってたりするもんなんじゃないでしょうか知らんけど。
5兆の記録の方は、
http://www.numberworld.org/misc_runs/pi-5t/details.html
あたりに書いてあるのですが、
After Fabrice Bellard's announcement of 2.7 trillion digits on a "relatively cheap" desktop, it was pretty clear that the limit of personal computing was a lot higher.
と書いてあって、 Fabrice の方法でもっと計算できるのは明らかだったから、もっといいマシンで似たような方法でやってみた、って感じなんだと思います。実際マシンのスペックも、
- 2 x Intel Xeon X5680 @ 3.33 GHz - (12 physical cores, 24 hyperthreaded)
- 96 GB DDR3 @ 1066 MHz - (12 x 8 GB - 6 channels) - Samsung (M393B1K70BH1)
- 1 TB SATA II (Boot drive) - Hitachi (HDS721010CLA332), 3 x 2 TB SATA II (Store Pi Output) - Seagate (ST32000542AS) 16 x 2 TB SATA II (Computation) - Seagate (ST32000641AS)
- Windows Server 2008 R2 Enterprise x64
と、ちょっとご家庭で買うには高そうな感じのものになったみたいでした。
でまぁその Fabrice の方の細かい報告の
http://bellard.org/pi/pi2700e9/pipcrecord.pdf
や、サイトの FAQ
http://bellard.org/pi/pi2700e9/faq.html
とかを読んでみると、イマイチよくわからんものの、いくつか面白いなーと思ったことがあったので羅列していってみます。正直 pdf の方はよくわからない部分が多かったので FAQ からの部分が多いですが。
- 計算は Chudnovsky 級数というものを使ったそうです。詳細はよくわかりません。この方法だと O(M(n)log(n)^2) (M(n) はだいたい線型だそうなので、だいたい n log(n) と思って良い…のかな?) くらいで、その前の記録で使われてたのは O(M(n)log(n)) なので、計算量的には不利なんだけど、データの局所性が良いとか、色んな工夫で定数項を減らせたとかで、 Chudnovsky 級数を使う方法で記録を出せた、とのこと。 n が相当でかくても log(n) くらいなら力でねじふせれたーみたいな話でしょうか、なにやらかっこいいわけです。
- 具体的な工夫としては、共通項のくくり出し、事前計算、マルチスレッド、なんていうそれっぽいものが上げられています。詳細はよくわかってません。
- 確認の方法として、似てるけどちょっと違って少し遅い (14/8倍の時間がかかる、っぽい?) アルゴリズムを使って同じ結果が出るかどうか調べようとした、とのこと。面白いのはその方法は断念していて、理由はマシンのディスクが壊れたから、とのこと。
- しょうがないから代わりとして持ち出した確認法は、片方は checksum 的なもので、よくわからんですが Chudnovsky 級数の特徴からその checksum 的なものはラクに計算できるらしい
- もう一方は円周率の任意桁を高速に計算する方法というのがあるらしくて、それを使って、最後の50桁が正しいことを確認した、とのこと。これはもともと Bailey-Borwein-Plouffe formula というのがあったのを、 Fabrice 自身がそれよりいいものとして発見した Bellard's formula というので確認したとのことで、まぁなんかすごげな。
- 本質的にデカい掛け算が一番重要になるらしくて、デカい掛け算は FFT してからほげほげして逆 FFT 、ってのが常識らしい。なんか聞いたことはある気がするけどまあそんなこんな。
- 詳しい説明がありました: http://homepage2.nifty.com/m_kamada/math/fftmul.htm
- で、本気でデカい掛け算はメモリにおさまらんので HDD の上でやる必要がある、とのこと。そんなこんなで disk I/O が律速しちゃったので、 GPU とか使って計算する部品を速くしてもたいしてよくならんのじゃないかなーとか FAQ に書いてありました。
- あとソースコード出すかは検討中、とのこと。意味わかるとは思えないけど眺めてみたいもんだと思います。
そんなこんな。世の中なにやらすごげな人はすごいなあという話。
