SICP - Solution: Exercise 1.15

SICP - Solution: Exercise 1.15

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)

a number of steps
12 6
120 8
1200 10
12000 12
120000 14
1200000 16
12000000 18

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))}$