2
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.