SICP 練習問題 1.15 （sine近似ネタでステップ数とスペース数を求める）

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

sin(x)≒x

の近似と、正弦の引数の値を小さくする為の三角関係式、

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


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

gosh> (use slib)
#
gosh> (require `trace)
#t
gosh> trace
#
gosh> (trace p)
#

んでは実行してみましょう。

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された回数だから、答えは５回。ずるいとか言わない。



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 * (1/3) * (1/3) * (1/3) * ... * (1/3) <= 0.1  ・・・(1)  (※左辺は(1/3)をn回掛けている）

という関係式が成り立つ。 n回の時に初めてこれが成り立つという仮定なので、n-1回の時は勿論↓こうなる。

0.1 < a * (1/3) * (1/3) * (1/3) * ... * (1/3)   ・・・(2)　(※右辺は(1/3)をn-1回掛けている）

なので、(1), (2)から、次の関係式が導かれる。

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

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

log_3(a/3^n) <= log_3(0.1) < log_3(a/3^(n-1))
log_3(a) - log_3(3^n) <= log_3(0.1) < log_3(a) - log_3(3^(n-1))
log_3(a) - n・log_3(3) <= log_3(0.1) < log_3(a) - (n-1)・log_3(3)
log_3(a) - n <= log_3(0.1) < log_3(a) - n - 1

各数式にnを加算。

log_3(a) <= log_3(0.1) + n < log_3(a) - 1

各数式からに log_3(0.1) を減算。

log_3(a) - log_3(0.1) <= n < 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))))))

－