円周率

<経緯>
会社の研修で、C言語を勉強しているのだが、内容が基礎的ゆえ全部『教えた』経験のある事柄ばかり、という暇っぷり。

んで、しゃーないので与えられた課題を、おかしな方法で解くことにする……ループ命令をいっさい使わず、再帰関数とif文でループをくむというやり方である。

これで、ほとんどの課題はうまくいったのだが、たったひとつうまくいかない課題があった。
「円の半径をコマンドライン引数からとって、円の面積を表示するプログラムを作れ」というものである。
一見簡単そうに見えるが、実は円周率πを正しく求めるのに、かなりの調査を要した。
まず最初に、小学生でもわかる求め方の一つとして、円とそれに外接する正方形の比をとる方法を2種類実装した。ひとつはランダムな点を打って、円の中か外かを判断することで、大数の法則に期待して円周率を求めるというやり方(モンテカルロ法という)。もうひとつは正方形の中にメッシュを張って、メッシュの各点が円の中にあるかどうかを判定するやり方。
要するに、どちらもCPUパワーに任せた、力づくのやりかたなわけだが、ループ命令を使わないデメリットがもろに出てしまう結果になった……すなわち、精度を上げようとループ回数を増やすと、スタック・オーバーフローによるエラーでプログラムが落ちてしまうのだ。

で、Wikipediaに頼って円周率を効率よく探すアルゴリズムを探してみると、「円周率の歴史」ページに、そのアルゴリズムがあった。

1995年9月19日午前0時29分

カナダのサイモン・フレイザー大学において、デビット・H・ベイリー、ピーター・ボールウェイン、サイモン・プラウフの研究チームが無限級数
¥pi = ¥sum_{k = 0}^{¥infty} ¥frac{1}{16^k} ¥left( ¥frac{4}{8k + 1} – ¥frac{2}{8k + 4} – ¥frac{1}{8k + 5} – ¥frac{1}{8k + 6}¥right)
を発見する。この式では2進表示または16進表示で n – 1 桁までを求めずに n 桁目以降の π の値を計算できる。ベイリーのウェブサイトで様々なプログラミング言語用の実装例を見ることができる。

これは、コンピュータ上において「桁数を区切って」円周率を求めることが可能という、画期的アルゴリズム。数式がTeXソース形式で読みづらいのはご愛敬。
このアルゴリズムの収束の早さに助けられ、私は無事円周率を再帰関数で求めることができた。私の「おかしな方法でプログラムを組む」というポリシーはこうして守られたのだ。

<主張>
で、ベイリー氏のサイトから。

あなたの名前が、円周率のどこの桁にあるか探してみませんか?

という、氏の円周率アルゴリズムの特長を生かした、すてきなお誘いが。

というわけで、実際に探してみた。

search string = “takumi”
30-bit binary equivalent = 101000000101011101010110101001

search string found at binary index = 3336826008
binary pi : 0110011010100000010101110101011010100101001100110011100111110010
binary string: 101000000101011101010110101001
character pi : up;ljm,rl;dwqnmsftakumiisggyhd;jlcx;wc
character string: takumi

というわけで、33億3682万6008桁めに私の名前があることが、このアルゴリズムにより明らかにされた。

あなたも、円周率の数字の奥深くに、自分の名前が隠されているかもしれません。ひとときの思い出のために、英語をおそれずに、少しの時間を使って、試してみるのはいかがでしょう?

タグ: , , ,

コメントをどうぞ