An excerpt of http://pdg.lbl.gov/2012/reviews/rpp2012-rev-monte-carlo-techniques.pdf (section 37.4.3) states that obtaining the sine/cosine of a random angle in 2D without the explicit use of $\pi$ is as follows:
Generate (uniformly) a $u$ and $v$ where $u$ is in $(-1, 1)$ and $v$ is in $(0, 1)$. If $r^2 = u^2 + v^2 > 1$, then repeat this process. Otherwise, sine ($S$) and cosine ($C$) is given by:
$S = 2uv / r^2$ and $C = (u^2 – v^2) / r^2$
Can someone explain the mathematics behind this? I was thinking it was something related to generating a point on the unit circle and then taking the sine/cosine relationships, but I can't seem to directly make the correlation.
Best Answer
This gives us a random point $(u,v)$ in a $2 \times 1$ rectangle.
This gives a random point $(u,v)$ in the closed semidisk (i.e., semicircle plus its interior) inscribed in that rectangle. That is, our point is of the form $(r \cos \theta,r\sin \theta)$ where $\theta$ is uniformly distributed on $[0, \pi]$.
Here we're applying a double-angle formula so our angle will be uniform over $[0, 2\pi]$ instead of $[0,\pi]$:
$$S=\frac{2uv}{r^2}=\frac{2(r \cos \theta)(r\sin \theta)}{r^2}=2\cos\theta\sin \theta=\sin(2\theta)\\ C=\frac{u^2-v^2}{r^2}=\frac{r^2\cos^2\theta - r^2\sin^2 \theta}{r^2}=\cos^2\theta-\sin^2 \theta=\cos(2\theta) $$
The advantage of this algorithm over the more obvious one (where you sample over the entire disk instead of using a double-angle formula) is that it only requires rational arithmetic; $r=\sqrt{u^2+v^2}$ is not a rational function of $u$ and $v$, but $r^2$ is.