/\A toku_?bass \z/x: 計算機プログラムの構造と解釈　問題1.15

2009年2月23日月曜日

計算機プログラムの構造と解釈　問題1.15

問題1.15

(ラジアンで表す）角度の正弦は、xが十分に小さいとき、 $￥sin(x)￥approx x$ の近似と、正弦の引数の値を小さくするための三角関係式
$￥sin(x)=3￥sin￥frac{x}{3}-4￥sin^3￥frac{x}{3}$
を使って計算できる。

あー、つまり、入力した角度を計算式を用いて、極限まで小さくして、xがsin(x)とほぼ同値になったら、xをsin(x)とみなして、復元してやるのね。

a.(sine 12.15)の評価で、手続きpは何回作用されられたか。


gosh> (use slib)
#<undef>
gosh> (require 'trace)
#t
gosh> (define (cube x) (* x x x))
cube
gosh> (define (p x) (- (* 3 x) (* 4 (cube x))))
p
gosh> (define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
sine
gosh> (trace sine)
#<closure (debug:trace-procedure debug:trace-procedure)>
gosh> (sine 12.15)
CALL sine 12.15
CALL sine 4.05
CALL sine 1.3499999999999999
CALL sine 0.44999999999999996
CALL sine 0.15
RETN sine 0.1495
RETN sine 0.4351345505
RETN sine 0.9758465331678772
RETN sine -0.7895631144708228
RETN sine -0.39980345741334
-0.39980345741334

pは5回作用させられる。
ただtraceのCALLがよくわからない。
なんでCALLがsine 0.15で止まってるんだ？もう１回sineが呼ばれてないとおかしくない？

b.(sine a)の評価で、手続きsineの生成するプロセスが使うスペースとステップ数の増加の程度は(aの関数として)何か。

$a/3^N < 0.1$
$a < 3^N/10$
定数1/10を省略
$a < 3^N$
$N > log_{3} a$
${￥red}N > ￥frac{￥log_{2}a}{￥log_{2}3}$
${￥red}N > ￥frac{1}{￥log_{2}3}*￥log_{2}a$
定数を省略
${￥red}N > ￥log_{2}a$
$0.1 < a/3^N + 1$ のときも同様に考える。

スペースは $￥log (a)$
ステップ数は呼び出した数だけリターンするのでスペースの2倍になるが、
定数倍は無視するので同じく $￥log (a)$