ochalog

Ruby と MediaWiki が好きな電子・情報系の学生のブログ。

SICP: Exercise 1.15

\( \sin x \) の計算は、\( x \) が十分に小さければ \( \sin x \approx x \) で近似可能。\( x \) を小さくするためには 3 倍角の公式

$$ \sin x = 3 \sin \frac{x}{3} - 4 \sin^3 \frac{x}{3} $$

が使える。ここでは \( x \) は 0.1 ラジアンを超えないものとする。

(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 12.15) を評価したとき p は何回適用されるか

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))

より 5 回。

b. (sine a) の増加の程度

\( a \) が 0.1 以下になるまで sine を適用する回数を約 \( n \) 回とすると

$$ \begin{align*} \frac{a}{3^n} &= 0.1 \\ 3^n &= \frac{a}{0.1} \\ n &= \log_3 \left( \frac{a}{0.1} \right) \end{align*} $$

sine再帰的プロセスなので、段階数、空間ともに増加の程度は \( \Theta(\log a) \)。