Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.15

From Drewiki
Jump to: navigation, search

Problem

The sine of an angle (specified in radians) can be computed by making use of the approximation

<math> \sin x \approx x </math>

if x is sufficiently small, and the trigonometric identity

<math> \sin x = 3 \sin \frac{x}{3} - 4 \sin^3 \frac{x}{3} </math>

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

Problem A. How many times is the procedure p applied when (sine 12.15) is evaluated?

Problem 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 procedure when (sine a) is evaluated?

Solution A

Let's evaluate (sine 12.15) by the substitution model to find the answer to this problem:

(sine 12.15)
(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)))))

Procedure p is applied 5 times.

Solution B

Both procedure p and procedure cube perform a constant number of steps and require a constant amount of storage (assuming that procedures - and * are θ(1)). The order of growth in space and number of steps for procedure sine, then, is proportional to <math>\log_3</math> of the argument, since each non-terminating step in the evaluation of (sine a) divides a by 3. Hence, procedure sine is order <math>\log n</math> both in space and in the number of steps.

Personal tools