SICP: Why does this recursion-based sine approximation work?

Question

Here is the question and solution to Structure and Interpretation of Computer Programs' exercise 1.15 (see here). My problem is, I don't know how the combination of these formulae actually work:

$$sin(x) = 3sin(x/3) - 4sin^3(x/3)$$ and $$sin(x) = x$$ for small $x$ radian values.

I understand the idea that the closer the radian angle gets to zero, the more it approximates the sine of that angle. I've seen excellent explanations (MIT OCW, Khan Academy). I also have worked out how the $sin(3x)= 3sin(x) - 4sin^3(x)$ formula is derived. But how are they being used together to derive an answer to $sin(x)$? The p function seems to simply be taking the variable angle divided by $3$ each recursive pass until angle is down below $0.1$ Then on the way back, we perform p as many times as we had to divide by $3$. So it seems $$sin(x) = 3sin(x/3) - 4sin^3(x/3)$$ magically becomes the same as $$sin(x) = 3(x) - 4(x^3)$$ through recursive application. How? I'm not very deeply versed in recursion theory. Also, if this is logarithmically getting closer to $0.1$, it's not as if we're totaling up lots of small $x$'s a la integration. This seems to be doing something vaguely like the Y-combinator -- which I also don't grasp that well yet.

Also, when we see the recursive steps (recursion) repeatedly dividing angle by $3$, what tells you definitively this is logarithmic? I mean, it looks like it's taking those giant order of magnitude leaps at each division, but is there another analytical way to call this logarithmic reduction?

Answer 1

There are two methods that this exercise uses. The first method is the $p$ function,

$$ p(x) = 3x - 4x^3, $$

and the second is an approximation of sine, given by

$$ \sin(x) \approx x.$$

The connection between the $p$ function and sines is that $p(\sin(x/3)) = \sin x$. This is a trigonometric identity (that one can prove by examining $e^{3ix} = (e^{ix})^3$, expanding via $e^{i \theta} = \cos \theta + i \sin \theta$, and considering imaginary parts).

The approximation $\sin(x) \approx x$ is more accurate when $x$ is smaller. In fact, the error of this approximation can be bounded by $x^3/6$, so this becomes a very good approximation for very small $x$.

The idea of this exercise is to repeatedly apply the $p$ map until evaluating $\sin(x)$ can be expressed in terms of a (possibly complicated polynomial) evaluated at $\sin(y)$ for some much smaller $y$, specifically a $y$ of the form $y = x/3^n$.

Let's work this through explicitly. We want to evaluate $\sin x$.

• If $x$ is small enough, we say $\sin x \approx x$ and we're done.
• If not, then we note that $\sin x = p (\sin(x/3))$. Now the relevant sine computation is $\sin(x/3)$.
• If $x/3$ is small enough, we use $\sin(x/3) \approx (x/3)$ to get that $\sin x = p(\sin(x/3)) \approx p(x/3)$.
• If not, then we use $\sin (x/3) = p(\sin(x/3^2))$ to see that $\sin x = p(p(\sin(x/3^2))$. Now the relevant sine computation is $\sin(x/3^2) = \sin(x/9)$.
• If $x/3^2$ is small enough, we use $\sin(x/9) \approx x/9$ to get that $\sin x = p(p(\sin(x/9)) \approx p(p(x/9))$.

Notice that the structure of this answer and the structure of the lisp code in the exercise are very similar. Iterating, the key recursive identity is that $\sin x = p^{(n)}(\sin (x/3^n))$, where $p^{(n)}$ means to iterate the $p$ map $n$ times.