SICP 問題1.15

2017/08/15

#sicp

(ラジアンで表す)角度の正弦は, xが十分小さい時, sin x ≈ xの近似と, 正弦の引数の値を小さくするための三角関係式
sin x = 3sin(x/3) - 4sin^3(x/3)
を使って計算出来る.
(この問題のためには, 角度の大きさが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は何回作用させられたか.
b. (sine a) の評価で, 手続き sine の生成するプロセスが使うスペースとステップ数の増加の程度は(aの関数として)何か.

なるほど、数学力が低くてラジアンはよくわからないから飛ばそうとも思ったけれど、ラジアンわからなくても答えられるかもしれないっぽいので少し考えてみる。

a. 手続きpは何回作用させられたか

(sine 12.15) を呼ぶと下記のように展開される。

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

よって、pは5回作用する。

b. スペースとステップ数の増加の程度は何か.

スペース

aが大きくなればなるほど上記の山は大きくなるので、スペースはO(n)で増加する。

ステップ数

ステップ数もスペースと同様に山が大きくなればなるほどステップ数が増加するので、O(n)で増加する。

と思ったのだけど、調べてみると全然違うのね。
ちょっとスペースとステップ数、そして反復的プロセスについて再度復習する必要がありそう。
あとlogとか言われても全然わからない。。。