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?


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.