excercise-1.15

The sine of an angle (specified in radians) can be computed by making use of the approximation $sin xapprox x$ if $x$ is sufficiently small, and the trigonometric identity

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

to reduce the size of the argument of $sin$. (For purposes of this exercise an angle is considered “sufficiently small” if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:

1
2
3
4
5
6
7
8

(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. How many times is the procedure p applied when (sine 12.15) is evaluated?

b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?

Ans

a.

$(sine space 12.15) leftarrow (sine space 4.05) leftarrow (sine space 1.35) leftarrow (sine space 0.45) leftarrow (sine space 0.15) leftarrow (sine space 0.05) leftarrow 0.05$

所以一共是 6 次

b.

每执行一次 $(sinespace x)$, $a$ 的值将会变为原来的 $frac{1}{3}$ 终结条件如下 $frac{a}{3^n} < 0.1$ 转换即为 $n> log_3{10a}$ 所以规模的增长为 $lg{n}$