How do GPUs compute sines?

Question

I've been wondering lately how GPUs compute sines and cosines, and Google hasn't helped me finding a precise answer.

Initially, I was thinking that in order to make the computations as fast as possible, the GPU would use some kind of lookup table. But then I realized, storing all sin values in a table of the range of doubles between [0, 2 * pi] would be a massive one, and thus not be a valid option.

The table could possible be shrunk down in resolution, and the missing values for a lookup can then be lerped. This however, introduces a possible error which can propagate to bigger and unacceptable errors when performing the computation multiple times.

My last idea is then that they could be using a Taylor approximation, but that would involve quite some arithmetic, which may be too slow for a GPU. So the question is, what do GPUs use to calculate the sines? Are it lookup tables, approximations, or a hybrid of both? And possible, do they use the same method for other computations like sqrt()?

Answer 1

I believe that NVidia GPUs they use a table lookup, followed by a quadratic interpolation. I think they are using an algorithm similar to the one described in: Oberman, Stuart F; Siu, Michael Y: "A High-Performance Area-Efficienct Mutlifunction Interpolator," _IEEE Int'l Symp Comp Arithmetic, (ARITH-17):272-279, 2005.

The table lookup is indexed with the $m$ most-significant bits from the input, $x$, and returns three coefficients, $c_0$, $c_1$, $c_2$. The final result is produced by evaluating $c_0 + c_1 x + c_2 x^2$. The coefficients for each range of $x$ are chosen to minimize the maximum error from the target function over that range.

So that the unit can be fully pipelined to produce one result per cycle the unit contains a special squaring unit and two booth-encoded wallace-tree multipliers. For each special function they choose the number of table entries ($2^m$) so that the polynomial evaluation will give them a single-precision IEEE FP answer correct to within a couple of units in the last place.