SICP Exercise 1.15: The Sines of the Fathers

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 r = 3sin(r/3) - 4sin3(r/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)))))

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

As p is not recursive in and of itself, for part (a) we can check this easily via substitution by expanding (sine 12.15) as far as we can (i.e. until we encounter an invocation where (> (abs angle) 0.1) evaluates to true) but leaving any instances of p unexpanded. Then we just count the number of occurrences of p:

(sine 12.15)
= (p (sine (/ 12.15 3.0)))
= (p (sine (/ 12.15 3.0)))
= (p (sine 4.05))
= (p (p (sine (/ 4.05 3.0))))
= (p (p (sine 1.35)))
= (p (p (p (sine (/ 1.35 3.0)))))
= (p (p (p (sine 0.45))))
= (p (p (p (p (sine (/ 0.45 3.0))))))
= (p (p (p (p (sine 0.15)))))
= (p (p (p (p (p (sine (/ 0.15 3.0)))))))
= (p (p (p (p (p (sine 0.05))))))
= (p (p (p (p (p 0.05)))))

So p will be applied 5 times.

As to the order of growth in space and number of steps for part (b), first let's observe that each non-terminating invocation of sine requires:

• a fixed cost in terms of space, as the interpreter needs to record that it needs to apply p to the result of the recursive invocation of sine
• a fixed number of steps (i.e. the number of steps required at each iteration does not vary).

So both space and number of steps have the same order of growth, and this scales with the number of invocations of sine required. How many invocations of sine do we need for any arbitrary invocation of (sine a)? Well for each non-terminating value of a we divide the value of a by 3 and make a recursive call with this smaller value. This indicates that the number of steps will vary logarithmically with a, so we can say that both space and the number of steps are Θ(log a).

That's normally as far as we'd take it when specifying orders of growth, but we can go a bit further if we really want to. We divide a by 3.0 at each step, so that provides us with a base for our logarithm, which gives us Θ(log₃a). We also know that log_x1 = 0 for any x, but our terminating condition occurs when a is 0.1, not 1. To account for this we multiply a by 10 in the order of growth, giving: Θ(log₃10a).

P.S. Apologies - I couldn't resist the title.