円周率.jp (http://xn--w6q13e505b.jp/program/roemer.html)

Roemer

このプログラムは IOCCC で 1989 年に Best layout 賞を得たプログラムである。 とりあえず元のプログラムを見てみよう。

									char
							    _3141592654[3141
	  ],__3141[3141];_314159[31415],_3141[31415];main(){register char*
      _3_141,*_3_1415, *_3__1415; register int _314,_31415,__31415,*_31,
    _3_14159,__3_1415;*_3141592654=__31415=2,_3141592654[0][_3141592654
   -1]=1[__3141]=5;__3_1415=1;do{_3_14159=_314=0,__31415++;for( _31415
  =0;_31415<(3,14-4)*__31415;_31415++)_31415[_3141]=_314159[_31415]= -
1;_3141[*_314159=_3_14159]=_314;_3_141=_3141592654+__3_1415;_3_1415=
__3_1415    +__3141;for			(_31415 = 3141-
	   __3_1415  ;			_31415;_31415--
	   ,_3_141 ++,			_3_1415++){_314
	   +=_314<<2 ;			_314<<=1;_314+=
	  *_3_1415;_31			 =_314159+_314;
	  if(!(*_31+1)			 )* _31 =_314 /
	  __31415,_314			 [_3141]=_314 %
	  __31415 ;* (			 _3__1415=_3_141
	 )+= *_3_1415			  = *_31;while(*
	 _3__1415 >=			  31415/3141 ) *
	 _3__1415+= -			  10,(*--_3__1415
	)++;_314=_314			  [_3141]; if ( !
	_3_14159 && *			  _3_1415)_3_14159
	=1,__3_1415 =			  3141-_31415;}if(
	_314+(__31415			   >>1)>=__31415 )
	while ( ++ *			   _3_141==3141/314
       )*_3_141--=0			   ;}while(_3_14159
       ) ; { char *			   __3_14= "3.1415";
       write((3,1),			   (--*__3_14,__3_14
       ),(_3_14159			    ++,++_3_14159))+
      3.1415926; }			    for ( _31415 = 1;
     _31415<3141-			    1;_31415++)write(
    31415% 314-(			    3,14),_3141592654[
  _31415    ] +				   "0123456789","314"
  [ 3]+1)-_314;				   puts((*_3141592654=0
,_3141592654))				    ;_314= *"3.141592";}

実行結果(特に入力は必要ない)については自身で確かめてほしい。

解析の前準備

インデントを直す

roemer2.c

clang-fomat などのツールを使うことで簡単に修正できる。 エディタの自動修正機能とともに覚えておきたいツールである。

変数名を修正する(1)

roemer3.c

C 言語では _ から始まれば他が数字ばかりでも変数名として使うことができる。 本当の数値定数と見分けにくいので一度仮の変数名を割り当てよう。 以下のような対応でとりあえずアルファベット名の変数にする。

a_3141592654
b__3141
c_314159
d_3141
e_3_141
f_3_1415
g_3__1415
h_314
i_31415
j__31415
k_31
l_3_14159
m__3_1415
n__3_14

複文演算子を減らす

roemer4.c

1 文の中に二重三重に演算が行われていると、 演算子の優先順位を把握していないと読めない。 そこで次は複数の演算が行われているものを 読みやすくなる程度にバラしていく。

, 演算子は他の演算子より優先度が低い(全演算子の中で最下位な)ので、 その原則から外れないように , を除く。

また、定数項で演算している所は数値変換する。ポイントになる変換規則は

  • int 型同士の除算結果は int
  • , 演算子の返り値は最後の値
  • = 演算子の返り値は代入された値
  • int 型とポインタ型の変数について a[b] == b[a] が成り立つ。

なので、たとえば (3,1)1 に変換できる。

Warning を無くす

roemer5.c

今更だがここまでのプログラムはコンパイラにかけるといくつかの警告を出す。 主な警告は

  • 変数の型が書かれていない (int が仮定される)
  • main 関数の返り値型が書かれていない (int が仮定される)
  • 宣言の無い関数が使われている (C99 以降では不正なのでタマタマ動いていると考える)
  • 文字列と文字(char)の足し算は文字の追加にならない

といったところである。

分かりにくい表現を変更する

roemer6.c

write() 関数はデバイスメモリに書きこむ関数で、 このプログラムでは表示の役割を担っている。 計算速度では遅くなるが、やはり広く使われている printf() 関数へ置き換えたい。 本来は "0123456789"a[i] 番目のバイトを持ってきているため putchar(a[i] + '0') などへの変換もできるが、折角の printf() 関数なので %d に置換させてもらっている。

解析

roemer7.c

結論から言うと、このプログラムは自然対数の底 $e={\displaystyle \sum_{n=0}^{\infty}} \dfrac{1}{n!}$ を計算している。 正確には $n\leq 2$ の計算が初期値として与えられているので、 $e=2.5 + {\displaystyle \sum_{n=3}^{\infty}} \dfrac{1}{n!}$ という形で計算している。

実際に $\dfrac{1}{n!}$ を求める計算では「階乗の逆数」 という形で計算するのではなく 既に求められている $\dfrac{1}{(n-1)!}$ の値を $n$ で割ることで $\dfrac{1}{n!}$ を作っている。 (factInv[] に多倍長固定小数点数として格納している) この過程で denom での除算が多くなるので、 一度行った計算は quotient[]remaind[] に登録し再計算しないようにしている。

この除算テーブルは使わない形でも計算はできる。 この形にしたものが roemer8.c であるが、 削減するテーブルの容量も遅くなる計算時間も大したことないので 読みやすくなる程度しかメリット・デメリットは無い。