SICP 問題 1.15 (sine近似ネタでステップ数とスペース数を求める)

【問題】
ラジアンで表す)角度の正弦はxが十分小さい時、


\sin(x) \simeq x
の近似と、正弦の引数の値を小さくする為の三角関係式、

\sin(x) = 3 \sin(\frac{x}{3}) - 4 \sin^3(\frac{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)について。


trace使えば何回呼ばれたかわかるよね。
というわけで準備。


gosh> (use slib)
#
gosh> (require `trace)
#t
gosh> trace
#
gosh> (trace p)
#
gosh>
んでは実行してみましょう。


gosh> (sine 12.15)
CALL p 0.049999999999999996
RETN p 0.1495
CALL p 0.1495
RETN p 0.4351345505
CALL p 0.4351345505
RETN p 0.9758465331678772
CALL p 0.9758465331678772
RETN p -0.7895631144708228
CALL p -0.7895631144708228
RETN p -0.39980345741334

  • 0.39980345741334

gosh>

CALLされた回数だから、答えは5回。ずるいとか言わない。



b)について

これ、例によってまったく分からん。。解答をカンニング

SICP Reading's Wiki



藤谷さんの回答でちょっと分かったような気がしてきた。
藤谷さん、ありがとうございました!


終了条件に目をつけるのね。

aを3で割る回数がn回になった時に *終了した* と仮定すると、

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

↓notじゃない表記にすると・・・

(define (sine angle)
  (if (<= (abs angle) 0.1)
      angle
      (p (sine (/ angle 3.0)))))

の定義(特に終了の定義)から、a ≡ angleであるので、


a \, \cdot \underbrace{ \, \frac{1}{3} \, \cdot \, \frac{1}{3} \, \cdot \, \frac{1}{3} \, \cdot \hspace{15px} \cdots \hspace{15px} \cdot \, \frac{1}{3} \, }_{n} \leq \, 0.1 \hspace{15px} \cdots \hspace{15px} (1)
(※左辺は\frac{1}{3}をn回掛けている)
という関係式が成り立つ。n回の時に初めてこれが成り立つという仮定なので、n-1回の時は勿論↓こうなる。

0.1 \, \lt \, a \, \cdot \underbrace{ \, \frac{1}{3} \, \cdot \, \frac{1}{3} \, \cdot \, \frac{1}{3} \, \cdot \hspace{15px} \cdots \hspace{15px} \cdot \, \frac{1}{3} \, }_{n-1}  \hspace{15px} \cdots \hspace{15px} (2)
なので、(1), (2)から、次の関係式が導かれる。

\frac{a}{3^n} \, \leq \, 0.1 \, \lt \, \frac{a}{3^{n-1}}
こいつを元に、n =[f(a)] の関係式を導く。
ちなみに、[x]という表記は、「xを超えない最大の整数」という意味を持つ。
nは当然ながら「回数」であるので自然数の範疇であるから、この意味は納得できる。
さて、n=...の形にしたい場合、ベキ乗になっているnを通常の項にしてやらないとならんので、まずは両辺の対数を取る。
あと、3^nの3を消去したいので底は3にする必要がある。

\log{_3} \, \frac{a}{3^n} \, \leq \, \log{_3} \, 0.1 \, \lt \, \log{_3} \, \frac{a}{3^{n-1}}
\log{_3} \, a \, - \log{_3} \, 3^n \, \leq \, \log{_3} \, 0.1 \, \lt \, \log{_3} \, a \, - \, \log{_3} \, 3^{n-1}
\log{_3} \, a \, - n \cdot \log{_3} \, 3 \, \leq \, \log{_3} \, 0.1 \, \lt \, \log{_3} \, a \, - \, (n-1)\log{_3} \, 3
\log{_3} \, a \, - n \, \leq \, \log{_3} \, 0.1 \, \lt \, \log{_3} \, a \, - \, n \, + \, 1
各辺にnを加算。

\log{_3} \, a \leq \, \log{_3} \, 0.1 \, + \, n \, \lt \, \log{_3} \, a \, + \, 1
各辺からに log_3(0.1) を減算。

\log{_3} \, a \, - \, \log{_3} \, 0.1 \leq \, n \, \lt \, \log{_3} \, a \, - \, \log{_3} \, 0.1 \, + \, 1
上記の式から、[x]で表記可能にするには取りうる値の最大の値(式)を採用したいので中辺と右辺を採用して、

n \, = \, [ \log{_3} \, a \, - \, \log{_3} \, 0.1 \, + \, 1 \, ]
となる。
Θは、定数項、次元の低い項、定数係数は無視するので、ステップ数nは、Θ(log_3(a)) となる。
ちょっと分かった!(気がする(かも))
しかしスペースに関しては「これだ!」という計算の方法がわからない。
けど、sine関数は末尾再帰になってなくてかつ枝分かれするタイプでもないので、ステップ数に比例してpの計算の為の領域が増加していくイメージは湧く。
ステップ数と比例関係にあるから、やっぱりスペース数もΘ(log_3(a))でいいんじゃない?
藤谷さんの解答にもあったけど、このイメージ↓。

(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))))))