円周率の新記録?

| コメント(6) | トラックバック(0)

読売新聞Webによると、パリ在住のフランス人が、なんと普通のパソコンで、円周率の新記録を達成したという。以下、引用:

【パリ=林路郎】パリ在住のフランス人デジタルテレビ関連技術者が、円周率を2兆6999億9999万けたまで計算し、世界記録の更新を宣言した。

筑波大学計算科学研究センターのスーパーコンピューターが昨年樹立した記録を塗り替えたことになる。

ホームページで新記録を公表したのはファブリス・ベラールさん。筑波大のスパコンが昨年樹立した世界記録は2兆5769億8037万けたで、ベラールさんはこれを約1230億けたも上回ったことになる。

また、ベラールさんが計算に使ったのはスパコンではなく、価格2000ユーロ(約26万円)以下の普通のデスクトップ型パソコン。2進法による計算に103日、検算に13日をかけたという。ベラールさんは、新たな記録をダウンロードするには、コンピューターのディスクに1137ギガ・バイトの空きスペースが必要だとしている。

私は、この記事が、どうしても信じられない。理由は、普通のパソコンのリソースの制約と、計算速度の2点である。

まず、円周率を2兆6999億9999万けたまで計算するために、その領域を主記憶に確保しようとすると、1桁1バイトとしても、270GBとなる。パソコンでそんな主記憶を確保するのは無理である。すると、ハードディスク上に計算領域を確保して、仮想記憶的にハードディスクと主記憶の間でデータを読み書きしなくてはならないが、すると計算速度は、著しく低下する。ディスクとの読み書きのコストが大きすぎるのである。

次に、計算速度である。πの計算に書いたように、パソコンで、ARCTANの一番簡単な公式を使って、10000桁くらいまでπを計算すると、だいたい3~10秒くらいかかる。楽観的に観測して、3秒かかったとする。すると、桁数に線形な計算アルゴリズムなんてありえないが、それでもそういう理想的なアルゴリズムがあるとして2兆6999億9999万まで計算するのに、簡単な計算で、8千100万秒かかる。それを日数に直すと、938日となる。ここで、計算に103日しかかからないというのが、既にありえないことになる。ここでは、すべての計算が主記憶上で行われると仮定してのことである。もし、仮想記憶的にハードディスクと主記憶の間でデータを読み書きするなら、その10倍は時間がかかることだろう。

さらに、上記の筑波大のスパコンが昨年樹立した世界記録の記事を再掲してみる。すると、そのシステムの主記憶は、13.5TBあったという。私の想定を遥かに上回る。そこの記事の一部を再掲すると、

プログラムは高橋氏が作成。2つのプログラムともシングルジョブ実行環境で実行し、648台の計算ノード(1ノード当たりの浮動小数点演算理論最大実行性能は1472GFLOPS。全体では95.4TFLOPS)のうち、640台を使用する並列計算として処理が行われた。

これの計算時間は、29時間5分49秒であった。上記単一のパソコンによる計算時間は、たったこれの85倍でしかない。648台の計算ノードで29時間5分49秒かかるものが、単一のパソコンで、たった103日しかかからないというのは、どうしても割りに合わない。

また、ファブリス・ベラールさんは、πの計算のどのアルゴリズムを使用したか明示していない。πの計算には、ガウス・ルジャンドルとか、ボールウェインの4次の収束アルゴリズムとか、古典的ARCTANなどがあるが、何にしてもかなり枯れた分野で、それほど画期的なアルゴリズムは最早期待できない。よって、ベラールさんが既存のアルゴリズムを使ったとすれば、上記の疑問に逢着するのである。

トラックバック(0)

トラックバックURL: http://commutative.world.coocan.jp/mt/mt-tb.cgi/1646

コメント(6)

彼のHPのFAQ
http://bellard.org/pi/pi2700e9/faq.html
によれば筑波と比較して、計算スピードは2000倍遅く、計算時間は96倍かかったとあり、従って自分の方法が20倍計算効率が高いと言ってます。その理由はスパコンはノード間通信にコストがかかることと、アルゴリズムChudnovsky series evaluated using the binary splitting algorithm)が筑波の方法Arithmetic-Geometric Mean algorithm)より漸近的であるにもかかわらず効率的なキャシュと2進分割法のトリックで速くからだそうです。このトリックが数学的に正しいかどうかが興味のある所ですね。

筑波大学の専門家が、20倍効率的なアルゴリズムを見落とすのでしょうか。そもそも、チュドノフスキーのアルゴリズムは、1991年に発表されています。それがその後使われなかったのは、コンピュータの実装に困難があったのでは。

それと、リソース制約のところも説明がほしいところです。どうみても、パソコンのリソースでは苦しいです。

これは高速なアルゴリズムを発見したというのではなくて今の分散コンピューティングではπ計算に完全にフィットしていないので単独PCでうまく調整し、よく知られたアルゴリズムに少し細工してみたら効率的に計算できますよということだと思います。
確かにPCのリソースは知りたいところですが今のPCの実力は相当なものだとも思います。

> 今のPCの実力は相当なものだとも思います。

もしかして、500GBの主記憶、5TBのHDD程度は少なくとも想定しなくてはいけないと思いますが、それが正しいとしたら、そんな仕様のパソコンはあるでしょうか。

主記憶500GBはさすがにないでしょうが5TBは余裕でしょう。結果は2TBはないようです。主記憶、キャシュ、HDDが高速動作するよう調整されているとは想像しますが。

> 主記憶、キャシュ、HDDが高速動作するよう調整されているとは想像しますが。

では、HDDを仮想記憶的に使うのでしょうね。なんか、プログラミングが大変そうです。

コメントする

このブログ記事について

このページは、あやたろうが2010年1月13日 07:18に書いたブログ記事です。

ひとつ前のブログ記事は「マックのマニュアル」です。

次のブログ記事は「中田芳子」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。