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

Roemer

このプログラムは IOCCC で 1989 年に Best layout 賞を得たプログラムである.

とりあえず元のプログラムの形だけ HTML にそのまま載せて概観を見てみる.

									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

変数名を修正する(1)

roemer3.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

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

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 であるが, 削減するテーブルの容量も,遅くなる計算時間も大したことないので, 読みやすくなる程度しかメリット・デメリットは無い.