Suppose we are give a natural number $n$, the value of $\sin(x)$ and $\cos(x)$. How efficiently can we compute $\sin(n x)$?
My Thoughts :
The $\sin (n x)$ expansion will have $O(n)$ terms. The power terms will take $\log(n)$ time each to compute. But there will be a term $nC_n/2$ so if $n=10$ this will be $10/5$. How to find the complexity of this term? Is it $\Theta(2^n)$? Is there any alternate algorithm to compute it more efficiently? This way it looks around $2^n n\log n $.
Start with Euler's identity: $$e^{ix} = \cos x + i \sin x$$ where $i^2 = -1$.
Therefore:
$$\cos (nx) + i \sin(nx) = e^{inx} = \left( \cos x + i \sin x\right)^n$$
So the complexity of computing $\cos (nx)$ is the complexity of raising a single complex number to the power of $n$, then taking the real part.
You multiply y = nx and calculate sin(y), so practically the same time complexity as sin(x).
If n is large, say x is around 0.5 and n = 100,000, then nx will have significant rounding error. In that case, since sin (x + 2kpi) = sin(x), you would use some tricks to calculate (nx - 2kpi) with high precision to avoid rounding errors.
How do you do that? Calculate k = nx / 2pi, rounded to an integer. Don’t worry about precision. Go to the internet to find a better approximation to pi by finding p1 = pi rounded to double precision, and p2 = pi - p1.
Let p’ = p1 with bits removed so that 2p’ x k can be calculated without rounding error, and let p’’ = p1 - p’ + p2, so p’ + p’’ is very close to pi.
Calculate t = 2p’ k without rounding error, then use a “fused multiply-add” operation to calculate nx - t with high precision, then add 2p’’ k. The result is y = nx - 2kpi with high precision, then you calculate sin y. Total time: The time for sin(y) plus half a dozen additional operations. And it will work with high precision if nx is large.
