SICP 全笔记

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

$$\sin x = 3 \sin{\frac{x}{3}} - 4\sin^3{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:

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

对 (sine 12.15) 求值的时候，每一次递归都会调用 p。当 angle <= 0.1 的时候递归终止。所以调用次数：

12.15/3 = 4.05
 4.05/3 = 1.35
 1.35/3 = 0.45
 0.45/3 = 0.15
 0.15/3 = 0.05

总共调用 5 次。

我们使用 trace 来验证进入 p 的次数

1 ]=> (trace p)

;Unspecified return value

1 ]=> (sine 12.15)

[Entering #[compound-procedure 12 p]
    Args: 4.9999999999999996e-2]
[.1495
      <== #[compound-procedure 12 p]
    Args: 4.9999999999999996e-2]
[Entering #[compound-procedure 12 p]
    Args: .1495]
[.4351345505
      <== #[compound-procedure 12 p]
    Args: .1495]
[Entering #[compound-procedure 12 p]
    Args: .4351345505]
[.9758465331678772
      <== #[compound-procedure 12 p]
    Args: .4351345505]
[Entering #[compound-procedure 12 p]
    Args: .9758465331678772]
[-.7895631144708228
      <== #[compound-procedure 12 p]
    Args: .9758465331678772]
[Entering #[compound-procedure 12 p]
    Args: -.7895631144708228]
[-.39980345741334
      <== #[compound-procedure 12 p]
    Args: -.7895631144708228]
;Value: -.39980345741334

算法分析

sine 是线性递归，占用的空间是 $\theta(n)$ 。步长也为 $\theta(n)$ 。

sine a 所需的步数可以如下计算。

sine a 计算时产生的计算需要去判断 $a, \frac{a}{3}, \frac{a}{3x3}, \frac{a}{3x3x3}, \dots$ 是否小于 0.1。所以可得到公式

$$3^{-n}a < 0.1$$ 转化为 n 的式子：

$$n > log_{3}10a$$