A Method for Quickly Sampling Points on a Circle

I saw a $\mathbb{X}$eet that piqued my interest earlier today. Traditionally, to sample a point on the unit circle, you’d generate $u,v \in [0, 2\pi)$ and then return $\left(\operatorname{cos}\big(u), \operatorname{sin}\big(v) \right)$. Can we do this faster and without trigonometry? I got sniped by this question and tried for about an hour. The code is cursed, but the method that prevailed involved estimating $\operatorname{sin}\big(\theta)$ and $\operatorname{cos}\big(\theta)$ as low-degree polynomials and then rotating the result to avoid too much distortion.

If you read the code you’ll notice that I’m cheating a bit. The method, $\texttt{Approx. Trig}$ actually samples on the perimeter of an egg-shaped region. We can fix this with one more “rotation bit” or one more term in $\texttt{COS_P}$ and $\texttt{SIN_P}$. That said, absolutely bonkers to be thinking about performance like this in Python. There’s an interesting paper, A Low Distortion Map Between Disk and Square that discusses ways to (non-uniformly) map $[-1, 1]^2$ to a point in the unit circle. Once again, we have to give it up for the graphics folks. Here’s a blog discussing Shirley-Chiu and related methods.