Exercise 1.15 shows an interesting procedure for computing the sine of an angle (in radians) by combined use of the approximation sin x ~ x (if x is sufficiently small) and the trigonometric identity
sin r = 3 * sin(r/3) - 4 * sin3(r/3)
which is used to reduce the argument of sin. The code provided implements the computation:
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
(p (sine (/ angle 3.0)))))
The exercise goes on to ask the following two questions:
a. How many times is the procedure
(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 a)is evaluated?
Looking at how the process executes will help us answer both questions.
(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))))))
(p (p (p (p (p 0.05)))))
(p (p (p (p 0.1495))))
(p (p (p 0.4351345505)))
(p (p 0.9758465331678772))
As long as the angle stays greater than 0.1, the process keeps recursing. There are five calls to the procedure
pbefore that happens.
sineprocedure is recursive, but it makes only a single call to itself, so it isn't tree recursive and its complexity isn't nearly as bad as some of the procedures we've seen in previous exercises. The complexity for this procedure in both space and number of steps is actually better than linear.
Space - The amount of space required by this procedure would increase linearly as the input size is tripled. Only the calls to procedure
pare deferred, and we can triple the size of the input before an additional call would be made.
Number of steps - It's also easy to see that we can triple the value of the starting input angle and only one more step would be required by this procedure.
The complexity of both the space and the number of steps required by this procedure can be described as O(log n).
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.