6 ms·

I wish there were more details about the historical context in this. I recently went down a rabbit hole of trying to implement a cosine function from scratch a

I wish there were more details about the historical context in this. I recently went down a rabbit hole of trying to implement a cosine function from scratch and found that for most applications where I use cosine (low-resolution graphs or 2d games), I need a shockingly low level of precision. Even four decimals was overkill! For those that are interested, you can read about my adventures with precision and cosine: https://web.eecs.utk.edu/~azh/blog/cosine.html https://web.eecs.utk.edu/~azh/blog/cosine.html

jandrese 6y ago
In games it is very common to see lookup tables for trig functions. Not big ones either, maybe a few hundred entries.
- richrichardsson 6y ago
  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).
- TwoBit 6y ago
  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.
  - jacobolus 6y ago
    Handheld calculators generally use the CORDIC algorithm, https://en.wikipedia.org/wiki/CORDIC https://en.wikipedia.org/wiki/CORDIC
- jacobolus 6y ago
  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.
  - taeric 6y ago
    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...
    - exged 6y ago
      Once you take SIMD into account, lookup tables frequently lose. Vector gathers are not cheap at all.
  - BeetleB 6y ago
    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.
    - deleted 6y ago
      [deleted]
- ThePadawan 6y ago
  Using the rough equivalence of sin(x) ~= x also works shockingly well for smallish x.
mooman219 6y ago
Here's a java snippit that may be of interest to you [0] by a user called Riven [1]. It should be considerably faster than the lookup table with LERP (not that it really matters at this point since we're just counting nanoseconds on one hand). I recall going down this rabbit hole somewhere around High School as well five or so years ago, and ended up brainstorming potential faster implementations on an old java forum with several users. I believe you have a Intel-Core-i7-8559U, which if userbenchmark is to be trusted, leads me to believe the snippit I linked should be in the 3ns range assuming a warm cache for the lut. Accuracy is configurable based on the sin bits. [0]: https://gist.github.com/mooman219/9698a531c932c08ccefd86ba7cd4463a https://gist.github.com/mooman219/9698a531c932c08ccefd86ba7c... [1]: https://jvm-gaming.org/u/riven/summary https://jvm-gaming.org/u/riven/summary
MaxBarraclough 6y ago
Is there a well-optimised library out there for extremely fast low-precision trigonometric functions? Could it make practical sense to do this?
romwell 6y ago
If you are really interested in approximating a cosine on the cheap with high precision, you should look into approximating polynomials. The Taylor expansion produces approximating polynomials that aren't that good. For instance, if you were to ask which degree-4 polynomial best approximates cos(x)?, you wouldn't end up with 1-x^2/2 + x^4/24. In fact, this polynomial is 0.99958 - 0.496393 x^2 + 0.0372093 x^4; it pretty much coincides[2] with cos(x) on the interval (-π/2, π/2); the error is an order of magnitude smaller than with the Taylor polynomial (see [3] vs [4]). How to do this? Linear algbera[1]. See, the polynomials form a Hilbert space (a vector space with an inner product), where a decent choice of one is <f(x), g(x>) := \int_π/2^π/2 f(x)g(x) dx This is Do Gramm-Schmidt on 1, x, x^2, ...; obtain an orthonormal basis, and use the inner product to compute a projection on the first d elements to obtain a best degree-d polynomial approximation. Voila! Linear Algebra saves the day yet again. [1]https://www.math.tamu.edu/~yvorobet/MATH304-503/Lect4-04web.pdf https://www.math.tamu.edu/~yvorobet/MATH304-503/Lect4-04web.... [2] https://www.wolframalpha.com/input/?i=plot+0.0372093+x%5E4+-+0.496393+x%5E2+%2B+0.99958+%2C+cos%28x%29+on+%28-pi%2F2%2C+pi%2F2%29 https://www.wolframalpha.com/input/?i=plot+0.0372093+x%5E4+-... [3]https://www.wolframalpha.com/input/?i=plot+abs%281-x%5E2%2F2+%2B+x%5E4%2F24+-++cos%28x%29%29+on+%28-pi%2F2%2C+pi%2F2%29 https://www.wolframalpha.com/input/?i=plot+abs%281-x%5E2%2F2... [4]https://www.wolframalpha.com/input/?i=plot+abs%281-x%5E2%2F2+%2B+x%5E4%2F24+-++cos%28x%29%29+on+%28-pi%2F2%2C+pi%2F2%29 https://www.wolframalpha.com/input/?i=plot+abs%281-x%5E2%2F2...
- jacobolus 6y ago
  Finding the least-squares best polynomial doesn’t get you the minimum possible worst-case error though, or the minimum worst-case relative error. For those you can use the Remez exchange algorithm, https://en.wikipedia.org/wiki/Remez_algorithm https://en.wikipedia.org/wiki/Remez_algorithm And if you look at the NASA low-precision number routines, you’ll see that’s exactly what they did.
  - romwell 6y ago
    Sure, and thanks for the link! The least-squares solution is just a step-up from Taylor series that doesn't require anything deeper than the notion of an inner product (the parent comment I was responding to didn't go beyond Taylor).
jlarcombe 6y ago
Yeah, the classic 3D game Elite (1984) uses the small angle approximation throughout, no look-up tables at all (except for drawing the planets). https://www.bbcelite.com/explore/articles/deep_dive_pitching_and_rolling.html https://www.bbcelite.com/explore/articles/deep_dive_pitching...

jandrese 6y ago

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

richrichardsson 6y ago
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).
TwoBit 6y ago
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.
- jacobolus 6y ago
  Handheld calculators generally use the CORDIC algorithm, https://en.wikipedia.org/wiki/CORDIC https://en.wikipedia.org/wiki/CORDIC
jacobolus 6y ago
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.
- taeric 6y ago
  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...
  - exged 6y ago
    Once you take SIMD into account, lookup tables frequently lose. Vector gathers are not cheap at all.
- BeetleB 6y ago
  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.
  - deleted 6y ago
    [deleted]
ThePadawan 6y ago
Using the rough equivalence of sin(x) ~= x also works shockingly well for smallish x.

mooman219 6y ago

Here's a java snippit that may be of interest to you [0] by a user called Riven [1]. It should be considerably faster than the lookup table with LERP (not that it really matters at this point since we're just counting nanoseconds on one hand). I recall going down this rabbit hole somewhere around High School as well five or so years ago, and ended up brainstorming potential faster implementations on an old java forum with several users. I believe you have a Intel-Core-i7-8559U, which if userbenchmark is to be trusted, leads me to believe the snippit I linked should be in the 3ns range assuming a warm cache for the lut. Accuracy is configurable based on the sin bits. [0]: https://gist.github.com/mooman219/9698a531c932c08ccefd86ba7cd4463a https://gist.github.com/mooman219/9698a531c932c08ccefd86ba7c... [1]: https://jvm-gaming.org/u/riven/summary https://jvm-gaming.org/u/riven/summary

MaxBarraclough 6y ago

Is there a well-optimised library out there for extremely fast low-precision trigonometric functions? Could it make practical sense to do this?

romwell 6y ago

If you are really interested in approximating a cosine on the cheap with high precision, you should look into approximating polynomials. The Taylor expansion produces approximating polynomials that aren't that good. For instance, if you were to ask which degree-4 polynomial best approximates cos(x)?, you wouldn't end up with 1-x^2/2 + x^4/24. In fact, this polynomial is 0.99958 - 0.496393 x^2 + 0.0372093 x^4; it pretty much coincides[2] with cos(x) on the interval (-π/2, π/2); the error is an order of magnitude smaller than with the Taylor polynomial (see [3] vs [4]). How to do this? Linear algbera[1]. See, the polynomials form a Hilbert space (a vector space with an inner product), where a decent choice of one is <f(x), g(x>) := \int_π/2^π/2 f(x)g(x) dx This is Do Gramm-Schmidt on 1, x, x^2, ...; obtain an orthonormal basis, and use the inner product to compute a projection on the first d elements to obtain a best degree-d polynomial approximation. Voila! Linear Algebra saves the day yet again. [1]https://www.math.tamu.edu/~yvorobet/MATH304-503/Lect4-04web.pdf https://www.math.tamu.edu/~yvorobet/MATH304-503/Lect4-04web.... [2] https://www.wolframalpha.com/input/?i=plot+0.0372093+x%5E4+-+0.496393+x%5E2+%2B+0.99958+%2C+cos%28x%29+on+%28-pi%2F2%2C+pi%2F2%29 https://www.wolframalpha.com/input/?i=plot+0.0372093+x%5E4+-... [3]https://www.wolframalpha.com/input/?i=plot+abs%281-x%5E2%2F2+%2B+x%5E4%2F24+-++cos%28x%29%29+on+%28-pi%2F2%2C+pi%2F2%29 https://www.wolframalpha.com/input/?i=plot+abs%281-x%5E2%2F2... [4]https://www.wolframalpha.com/input/?i=plot+abs%281-x%5E2%2F2+%2B+x%5E4%2F24+-++cos%28x%29%29+on+%28-pi%2F2%2C+pi%2F2%29 https://www.wolframalpha.com/input/?i=plot+abs%281-x%5E2%2F2...

jacobolus 6y ago
Finding the least-squares best polynomial doesn’t get you the minimum possible worst-case error though, or the minimum worst-case relative error. For those you can use the Remez exchange algorithm, https://en.wikipedia.org/wiki/Remez_algorithm https://en.wikipedia.org/wiki/Remez_algorithm And if you look at the NASA low-precision number routines, you’ll see that’s exactly what they did.
- romwell 6y ago
  Sure, and thanks for the link! The least-squares solution is just a step-up from Taylor series that doesn't require anything deeper than the notion of an inner product (the parent comment I was responding to didn't go beyond Taylor).

jlarcombe 6y ago

Yeah, the classic 3D game Elite (1984) uses the small angle approximation throughout, no look-up tables at all (except for drawing the planets). https://www.bbcelite.com/explore/articles/deep_dive_pitching_and_rolling.html https://www.bbcelite.com/explore/articles/deep_dive_pitching...