Exercise 1.15

文責:@naoiwata

与えられた式

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

(a) 解法

与えられた sine 手続きにおいて, if 文を評価する回数がこの手続き p の作用数となる. よって, if 文の (not (> (abs angle) 0.1) を評価する回数を n 回 (n は 0 以上の整数) と置くと, \(x*(1/3)^n > 0.1\) を満たす最小の n の値が求める手続きの p の作用数と同値である.

上式を展開すると,

\(x*(1/3)^n > 0.1\)

\(10x > 3^n\)

\(\log_{3} 10x > n\)

ここで問にあるように x が 12.15 の場合を考える. x に 12.15 を代入すると \(4.3609... < n\) となるので最小の n は 5 となる. よって, (sine 12.15) にかかる手続き p の作用数は 5 回となる.

(b) 解法

ステップ

ステップ数を N (任意の実数) と仮定する.

N は (a) で求めたように手続き p の作用回数と同値である. よって, N は \(x*(1/3)^n > 0.1\) を満たす最小の n である. よって,

\(\log_{3} 10x > n\)

\(\log_{3} 10x + C = N (|C| < 1)\)

\(N = \log_{3} 10 + \log_{3} x + C\)

よって, \(\Theta(N) = \log_{3} x\) すなわち \(\Theta(N) = \log x\) となる.

解は \(\Theta(N) = \log a\) となる.

スペース

この手続において, スペース数はステップ数と等しい. 何故ならステップ数が 1 回増加する度に p 手続きの処理が 1 回増加するからである. スペース数とステップ数が等しいことから, こちらのスペース数も \(\Theta(N) = \log a\) となる.