Hacker News Reader

Comment by jandrese | Hacker News Reader

In games it is very common to see lookup tables for trig functions. Not big ones either, maybe a few hundred entries.

Audio plugin programming makes extensive use of lookup tables for expensive operations. Pre-calculating is a useful technique for such real-time sensitive work (like games that have to render a new frame every 16ms @ 60hz or audio plugins that need to return potentially a buffer every 0.72ms @ 32 samples/44.1kHz).

Calculators actually use lookup tables themselves. I don't know if FPUs do too, but I wouldn't be surprised, as it's faster than series expansion.

Handheld calculators generally use the CORDIC algorithm, https://en.wikipedia.org/wiki/CORDIC

Using the rough equivalence of sin(x) ~= x also works shockingly well for smallish x.

If you have access to modern processors (CPUs, GPUs) then a lookup table makes no sense. The polynomial is faster, more accurate, and needs less space to store precomputed values.

I wouldn't be shocked if lookup tables win on massively it of order CPUs. Of course, I also wouldn't be surprised if it is the it of order nature that makes the polynomial faster.

Would be interesting to see benchmarks. On to my list of things I have a low chance of completing...

Once you take SIMD into account, lookup tables frequently lose. Vector gathers are not cheap at all.

When you peek at the code for computing trig functions in most standard libraries (e.g. C Standard math library in the GNU C compiler), you'll see they typically use a lookup table somewhere in the calculation.

As an example, the LUT will get you in the ballpark of the answer, and then you compute a polynomial to calculate the delta and add the two together.

You can always find a polynomial that is extremely accurate, but it likely will be higher order, etc. A LUT + polynomial is faster. A pure LUT is the fastest, but takes too much memory.

Reply on news.ycombinator.com