April 2, 2009

牧野貴樹「π 円周率1,000,000桁表」暗黒通信団

[ Amazon ] ISBN 978-4-87310-002-9, \341

the_true_book_of_pi.jpg

 多倍長計算に手を染めるようになって,10年経つ。一応査読論文も何本か書いてきたから,ボチボチこの分野に関しては言いたいことを言っても罰は当たらんだろうと思うので,ここらで本音をぶちまけておく。
 そもそもワシがGMPMPFRを使ってライブラリを作ってシコシコ計算してきたのは,たーくさんの数字の羅列を眺めるのが好きだからである。まあ元は誤差誤差した計算を解析するのに飽きて,「だーっと桁をたくさん取って計算すりゃいいんだろ!」とヤケクソのように始めたのがきっかけなのであるが,元々数字フェチの気があったのが運の尽きで,以来,100桁,1000桁の数値データをみなければ満足しない体となり,中毒の様相を呈するようになってしまったのである。もちろん,「たくさん数字が並んでると楽しいでしょ?」では論文にならんので,それなりに実用的な意義のある悪条件問題やら多倍長計算の分散・並列化やらを対象としてもっともらしい理屈をつけてまとめるのであるけど,根源的には「数字の羅列が好き」という以上の動機が見あたらないのだ。
 だから,本書のような,ホントにπを百万桁並べただけの潔い本は,もうそれこそベッドに引きずり込んでホンホン(by 唐沢なをき)したいぐらい大好きなのである。もちろん数字の一個一個を丹念に読むなんてことはしない。適当にぱらぱらめくって一ページあたり一万桁並んでいる数字を眺めて悦に入るのである。これで一時間はイケる。
 ・・・ええ,変態だよヘンタイッ! いいじゃないか,誰にも迷惑かけてないんだからさ,ほっといてちょうだい!,とワシは声を大にして言いたいのである。

 変態の告白だけで終わっちゃうと,ワシの学者人生も共に終わっちゃいそうだから,もう少し真面目な話をしておく。

 そもそもπを含む実数は,無限桁小数でなければ正確な表現ができないようになっている。有限桁小数(=有理数)による数列の極限値は有限桁に収まらないのが普通なので,極限計算を土台とする微分積分を行うためにはどうしても無限桁小数を扱わねばならない。とはいえ,それは理論上のことであって,実際に扱う数値が無限桁ではどんなスーパーコンピュータを持ってしてもπの値の出力だって終了しやしない。だから実用的には適当な桁数で打ち切って(丸めと呼ぶ),単精度(約7桁),倍精度(約15強桁)とかでコンピュータでは計算することになっている。ここに理論との齟齬(=誤差)が生まれる。誤差をどーにかする方法は難しいのと簡単なのがあるが,とりあえず桁数をどんどん増やして計算しておけばそんなにおかしな結果にはならないんじゃないの~,とバカの一つ覚え的解決をするのが多倍長計算という奴である。頭の良い方策は,誤差の影響が少ない計算方法を問題ごとに考えるという奴であるが,これは数学的かつ数値計算的素養が必須なので,誰にでもできるというものではないし,やっぱり有限桁計算である以上,限界はあるのだ。
 とゆーことで多倍長計算をしておけば誤差の影響は減るのでめでたしめでたし・・・とはいかない。すぐに分かることだが,10桁の小数同士のかけ算をやるのと,100桁小数同士のかけ算をやるのとでは計算の手間(=計算量)がモンのすごく違ってくる。つまり,桁数が大きくなると計算量が増え,それに比例して計算時間も増えてしまう。なるべく大きな桁数でも計算時間を余り増やさないようなアルゴリズムを考えると・・・やっぱりここでも頭を使う必要が出てしまうのだ。
 ワシはバカなので,頭を使うより定評のある多倍長計算ライブラリ(GMP,MPFRはこれの一種)を使うだけという安易な方法を取ったけど,ここんとこを自力で解決しようとすると,アルゴリズムとコンピュータの内部構造に通じる必要が出て,相当の馬力を必要とする仕事になる。手計算をそのままなぞる計算方法では桁が増えると非効率になるので,計算量を減らす複雑なアルゴリズム(たとえばGMPのマニュアル参照)を使い,しかもそれを高速に実行できるようチューニングを行うという作業になるからだ。
 円周率πの計算も事情は一緒で,桁数を長くすればするほど計算時間は格段に増える。ちなみに世界記録を作った研究室出身の方は,計算時間を極力抑えるアルゴリズムを極めて,その方面では世界的に有名なライブラリを作り上げている。純粋数学の方々にはπの計算なんて,と軽視する雰囲気もあったようだが,コンピュータ屋にとってはかなりいい仕事(の目標)を与えたと言えるのである。もっともその後,BBP公式なんて理論的にもおもしろい結果が出たりするから,みんなが面白がって群がっている研究テーマからはいろんなものが発生するものだと感心する。

 最近はパソコンも高速になったので,本書に載っている百万桁計算はかなり軽い計算になっている。試しにSuper πというベンチマークソフトを使ってみたら,Athlon64 X2 3800+マシンで53秒(104万桁)だった。最新のQuad core CPUならこの1/4,さらにSIMD命令を使ったりすればもっと高速化されるので,本気になってあれこれ高速化のためのチューニングをやれば,10秒を軽く切るんじゃないのかな。

 本書に掲載されているπの百万桁は自作のプログラムで計算したとのことであるが,だからまあ多大な計算時間を要するというものではないし,計算の仕方はそれこそググってもらえば山ほど出てくるから,真にオリジナリティのある仕事とは言えない。著者としてはプログラムを作る方もさることながら,数字をかっちり並べてTeXで製版する方もおもしろかったのかなぁと想像する。本書は暗黒通信団というサークルが発行した同人誌ではあるが,ちゃんとISBNコードも取得して一般書店に流通させたりしているあたり,しかも314円という,あらかじめ決められていたようなやっすい頒価をつけちゃうあたり,ワシみたいな数字フェチを喜ばせるというやり方で日本文化に貢献しようというあたりの,心意気は見事である。つーか,心意気しか褒めようのない本を出したこと(eの本もあるらしいがワシは未見)が素晴らしい,とワシは,これはイヤミではなく,素直に感心しているのである。

Posted by tkouya at April 2, 2009 3:00 AM