問題1.15

aについて。(sine 12.15)でpが呼ばれるのは5回。以下traceの出力。

> (sine 12.15)
0> Calling (P 0.049999997) 
<0 P returned 0.1495
0> Calling (P 0.1495) 
<0 P returned 0.43513453
0> Calling (P 0.43513453) 
<0 P returned 0.9758465
0> Calling (P 0.9758465) 
<0 P returned -0.7895632
0> Calling (P -0.7895632) 
<0 P returned -0.39980328
-0.39980328

bについて。ステップ数はsineが呼ばれる回数に比例する。ここで、sineが呼ばれる回数をnとすると、

a / 3^n ≦ 0.1 < a / 3^(n - 1)

という関係が成り立つ。これは、

a / 3^n ≦ 0.1 < a / 3^(n - 1)
a / 0.1 ≦ 3^n < 3 * a / 0.1
log3(a / 0.1) ≦ n < log3(3 * a / 0.1)
log3(a) - log3(0.1) ≦ n < log3(a) - log3(0.1) + 1

よって、nは3を底とするaの対数関数であることが分かる。sineではスペースとステップ数は単純に比例するため、増加の程度は共にΘ(log a)。