1.15.md

1.15

Question

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

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

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?

Answer

a.

p is applied 5 times¹.

b.

sine's order of operations (evaluating sine before p) generate a recursive process whose space and time complexity depend on the number of divisions by 3 required to yield an angle less than 0.1:

$$ \begin{align*} \argmin_x & {a \cdot (1/3)^x < 0.1} \[4pt] \argmin_x & {a \cdot 3^{-x} < 0.1} \[4pt] \argmin_x & {\log a - x \cdot \log 3 < \log 0.1} \[4pt] \argmin_x & {x \cdot \log 3 > \log a - \log 10} \[4pt] \argmin_x & {x > \frac{\log a - \log 10}{\log 3}} \[4pt] \implies & \Theta(\log a). \end{align*} $$

Footnotes

1. cf. 1.15.scm. ↩