例として
を部分和で近似することを考える.
とする. そのままプログラム化すると
def factorial(N) { A = 1; for (I=1; I<=N; I++) A *= I; return A; } def e1(N) { E = 0; for ( I = 0; I <= N; I++ ) E += 1/factorial(I); return E; }
|
実はこの e1 関数はとても無駄が多い(何故か?) ので改良してみよう.
だから, 1/factorial(I) の分母を
1/factorial(I-1) から計算できる.
def e2(N) { F = 1; E = 1; for ( I = 1; I <= N; I++ ) { F *= I; E += 1/F; } return E; }
|
E = 1/0!
F = I!
E = 1+1/1!+...+1/I! |
実はこれでもまだ効率が無駄が多い. これは, 有理数計算特有の事情である.
の計算には後の節で説明する整数 GCD の計算が必要になるが,
の分母は
明らかに
を割るので GCD 計算は無駄になる. よって,
とおいて,
の漸化式を求めよう.
より
. よって, 次の
プログラムが書ける.
def e3(N) { A = 1; for ( I = 1; I <= N; I++ ) A = I*A+1; return A/factorial(N); }
|
[...] cputime(1);を実行すると, 計算時間が表示されるようになる.
これらの組み込み関数を使って