SICP - Solution: Exercise 1.15

October 10, 2018

Exercise 1.15 #

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

$$\sin x = 3 \sin\frac x3-4 \sin^3\frac x3$$

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?

Solution #

First, let’s just run the program with a display in sine so that we can see the details of each steps:

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle step)
  (display step) (display ": ") (display angle) (newline)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0) (+ step 1)))))

(display (sine 12.15 1))

Which results in:

1: 12.15
2: 4.05
3: 1.3499999999999999
4: 0.44999999999999996
5: 0.15
6: 0.049999999999999996
-0.39980345741334

Based on that, we can just write a function that will display directly a table formatted in Markdown that I can just cut and paste:

(define (sine-count-step angle step)
  (if (not (> (abs angle) 0.1))
      step
      (sine-count-step (/ angle 3.0) (+ step 1))))

(display "| ") (display "a         ") (display " | ") (display "number of steps              ") (display " |") (newline)
(display "| ") (display "----------") (display " | ") (display "-----------------------------") (display " |") (newline)
(display "| ") (display       12 ) (display " | ") (display (sine-count-step       12 1)) (display " |") (newline)
(display "| ") (display      120 ) (display " | ") (display (sine-count-step      120 1)) (display " |") (newline)
(display "| ") (display     1200 ) (display " | ") (display (sine-count-step     1200 1)) (display " |") (newline)
(display "| ") (display    12000 ) (display " | ") (display (sine-count-step    12000 1)) (display " |") (newline)
(display "| ") (display   120000 ) (display " | ") (display (sine-count-step   120000 1)) (display " |") (newline)
(display "| ") (display  1200000 ) (display " | ") (display (sine-count-step  1200000 1)) (display " |") (newline)
(display "| ") (display 12000000 ) (display " | ") (display (sine-count-step 12000000 1)) (display " |") (newline)

It is easy to see the trend: every time $a$ is multiplied by 10, the number of steps increase by 2. It looks like a logarithm. I could also have noticed that for every iteration, $a$ is divided by 3. So the iteration will stop when:

$$\frac a{3^n}<0.1$$

Which can be rewritten to take out the $n$ as:

$$\frac a{0.1}<3^n$$

$$\log\left(\frac{\displaystyle a}{\displaystyle0.1}\right)<\log\left(3^n\right)$$

$$\log(a)-\log(0.1)<n.\log\left(3\right)$$

$$\frac{\log(a)-\log(0.1)}{\log\left(3\right)}<n$$

Which means that the iteration are ${\mathrm\Theta(\log(a))}$