SICP Exercise 1.15

sicp

Question

The sine of an angle (specified in radians) can be computed by making use of the approximation $\sin x=3\sin\frac{x}{3}-4\sin^3\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:

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

Answer

The first part of this should be relatively simple to figure out. The angle is divided by three until it reaches a value less than $0.1$. So in this case, how many times would that be?

$$ \frac{12.15}{3}=4.05 $$ $$ \frac{4.05}{3}=1.35 $$ $$ \frac{1.35}{3}=0.45 $$ $$ \frac{0.45}{3}=0.15 $$ $$ \frac{0.15}{3}=0.05 $$

So, five divisions in total have to be performed. Since p is applied once for each of these divions, we can reasonably expect that it will be called five times. Of course, floating point will introduce a certain error into this, but it should not be so significant as to alter the amount of divisions needed to get to below $0.1$.

How about the order of growth?

As we can see, the amount of times p is evaluated is incremented by one for every tripling of a. If we look at it backwards, we could say that a scales with $3^n$, $n$ being the number of steps.

So, what we need is the reverse of $3^n$, which is nothing other than $\log_3(a)$. Therefore, the order of growth regarding the number of steps scales logarithmically, so we have $\Theta(\log n ))$.

As for the order of growth regarding space, it should be the same as for the number of steps, because for each additional step, there is exactly one more function call that the system must keep track of.

So we have a logarithmic order of growth for both space and number of steps. This is a very good order of growth, even better than linear.