## **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

## 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.