無限の猿は円周率の夢を見るか？
はじめに
今日は 3 月 14 日、円周率の日です。すこし面白いことをしましょう。
計算機の仕事
まずは次に示す C のプログラムを適当にコンパイルし、実行しておきましょう。沢山の数が流れていきますが大丈夫です。このプログラムが終了するには、きっととても長い時間を必要とするはずです。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#define PI 3.151673980
int
main(int argc, char *argv[])
{
const float pi = PI;
union { float f; char b[sizeof(float)]; } buf;
srandom((unsigned)time(NULL) + (unsigned)getpid());
do {
for (size_t i = 0; i < sizeof(buf); i++)
buf.b[i] = (random() & 0xFF);
(void)printf("%g\n", buf.f);
} while (memcmp(&buf, &pi, sizeof(buf)) != 0);
return 0;
}
これはなに？
無限の猿定理と呼ばれる定理があります。猿にタイプライタを渡して長い時間放置しておくと、ほぼ確実にシェイクスピアの素晴しい作品と同じものを打ち出すというものです。
上のプログラムでは猿の代わりに疑似乱数を利用し、シェイクスピアの作品の代わりに円周率の値を打ち出してもらっています。
浮動小数点数とは
C 言語における float 型はその名の通り、浮動小数点数を格納する型です。浮動小数点数では、数を符号、指数、仮数の組み合わせで表現します。
よく使われる形式は IEEE 754 と呼ばれるものです。この形式の（単精度の）浮動小数点数は 1 ビットの符号部、8 ビットの指数部、23 ビットの仮数部の計 32 ビットで表現されます。
IEEE 754 の浮動小数点数のビット単位の見た目とそれに対応する値をとてもわかりやすく可視化してくれる web ページが公開されています。このページで浮動小数点数をいじくってみると、コンピュータが浮動小数点数をどのように見ているのか感じることができると思います。
無限の猿と円周率
さて、上のプログラムをもう一度眺めてみます。
プログラムの冒頭では、pi と名付けられて円周率の値を格納されている定数の他に、buf と名付けられた共用体が宣言されています。この共用体は f と名付けられた float と b と名付けられた char の配列をメンバに持っています。b の長さは float の大きさと同じだけ確保されていますから、b の
プログラムの主要な部分は do-while のループです。ランダムな値を共用体の b の各要素に代入し、そのバイト列を float として解釈した値 f を printf で表示します。その値が pi と完全に同じならばループを抜けます。
このプログラムを実行する環境において float が 4 バイトで表現されることを仮定すると、このプログラムの仕事は
おわりに
おわりです。
プログラムの出力を虚空にリダイレクトしないと I/O ばかりに時間を取られて本当に時間がかかります。気をつけてください。
$ time ./a.out >/dev/null
real 0m27.646s
user 0m25.468s
sys 0m0.312s
Discussion