3 ms·

Although this post is interesting, the best way to optimize trig functions is generally via rational approximations[1] if you can live with the error (and the c

by dvt 9y ago

Although this post is interesting, the best way to optimize trig functions is generally via rational approximations[1] if you can live with the error (and the clamping). I remember finding a rational function to approximate a tanh-like soft clipper via a Padé approximator on (-1, 1) a few years ago[2]. See an equivalent rational approximation for atan2 here[3]. [1] http://www.embedded.com/design/other/4216719/Performing-efficient-arctangent-approximation http://www.embedded.com/design/other/4216719/Performing-effi... [2] https://stackoverflow.com/questions/6118028/fast-hyperbolic-tangent-approximation-in-javascript/6118100#6118100 https://stackoverflow.com/questions/6118028/fast-hyperbolic-... [3] https://www.dsprelated.com/showarticle/1052.php https://www.dsprelated.com/showarticle/1052.php

agnivade 9y ago
Thanks ! I will look into it :)
raphlinus 9y ago
A bit OT but my favorite way to approximate tanh is to do g(f(x)) where f(x) is an odd polynomial and g(x) is 1/sqrt(1 + x^2). The recip sqrt can be computed very quickly using Newton approximation, and many SIMD instructions have an instruction for it. Highly recommended for audio applications.
- jacobolus 9y ago
  Something is definitely off about your recollection here. g(x) = 1/√(1+x²) is always positive, whereas tanh(x) is negative for negative values of x. So regardless of your f, g(f(x)) can’t ever be a correct approximation for negative x.
  - jwmerrill 9y ago
    Looks like grandparent probably meant g(x) = x/√(1+x²) Looks like f(x)=x+x^3/5 gets you two decimal digits everywhere [1], and you could improve that with more terms in the polynomial. Edit: you can derive f(x) by doing a series expansion of tanh(x)/√(1-tanh(x)²) about x=0, and Mathematica tells me the first few terms are f(x) = x + x^3/6 + x^5/120 + x^7/5040 + O(x^9) [1] https://www.desmos.com/calculator/zbyll5oeqk https://www.desmos.com/calculator/zbyll5oeqk
    - raphlinus 9y ago
      Oops, yes, you're correct, I was typing from memory and didn't double-check. And yes, the Taylor series is pretty good but you can usually squeeze a bit more accuracy-over-range by, eg, using an optimizer for the coefficients. Also, note that in your notebook you have x^3/5 but x^3/6 is probably what you wanted.
  - conistonwater 9y ago
    Could be a typo, f(g(x)) with g(x)=x/√(1+x²) and f a polynomial makes more sense to me.
conistonwater 9y ago
Here's what atan looks like in openlibm: https://github.com/JuliaLang/openlibm/blob/1581174c85f7b645b15ba1ac1c3a98fb601f0fe7/src/s_atanf.c https://github.com/JuliaLang/openlibm/blob/1581174c85f7b645b... It's a degree-4 polynomial, with on division in the reduction atan2->atan, and at most one division in the argument reduction step in atan, giving an pretty accurate answer. By comparison, in [3] there is a degree-3 polynomial and the thing doesn't work outside [-1,1]. There is some kind of a tradeoff between accuracy and performance, but most of the time it's not worth it. Maybe if division is ludicrously expensive or something unusual like that. I suspect most performance gains that people are looking for come from omitting proper handling of special cases.
- dr_zoidberg 9y ago
  Hmmm... I'm a bit foggy on the specific quote, but in the Graphics Programming Black Book, specifically the part where Abrash covers writing fast code, he says something along the lines of: > Avoid special cases, because a special case means slow code So yeah, handling of special cases will bite you on the performance side. Sometimes it's inevitable, but if you have a lot of control (or you're very specific) of what values get passed as parameters, then you can get away with not handling special cases (or just handling the ones you care about).
  - conistonwater 9y ago
    Yeah, but the people talking about finding their own interpolating polynomials and Pade approximations are looking for those approximations in the regular common cases, and omitting the special cases happens almost by accident. You could just take the same approximation used by openlibm or whatever and it's likely better than anything you yourself can come up with.
mooman219 9y ago
I actually wanted a fast atan2 about 3 years ago in Java and held a small competition to see what people could come up with [1]. In plain old java, it looks like it performed very well, I would expect it outperformed what they did in the post using LUTs. My methodology for micro benchmarks was pretty awful back then, so there's reason for error. The fastest was just 3 branches and a memory lookup. [1] http://www.java-gaming.org/topics/extremely-fast-atan2/36467/view.html http://www.java-gaming.org/topics/extremely-fast-atan2/36467...
- rzzzt 9y ago
  Additional magic is involved -- Math.atan2 is an intrinsic method in HotSpot, which will use a hand-coded implementation instead of the Java definition when possible: https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc
  - mooman219 9y ago
    Math.Atan2 was well outperformed by the custom implementations in the post I linked. The native version isn't well optimized. Apache's Atan2 is just as accurate and about twice as fast for example.

by dvt 9y ago

agnivade 9y ago

Thanks ! I will look into it :)

raphlinus 9y ago

A bit OT but my favorite way to approximate tanh is to do g(f(x)) where f(x) is an odd polynomial and g(x) is 1/sqrt(1 + x^2). The recip sqrt can be computed very quickly using Newton approximation, and many SIMD instructions have an instruction for it. Highly recommended for audio applications.

jacobolus 9y ago
Something is definitely off about your recollection here. g(x) = 1/√(1+x²) is always positive, whereas tanh(x) is negative for negative values of x. So regardless of your f, g(f(x)) can’t ever be a correct approximation for negative x.
- jwmerrill 9y ago
  Looks like grandparent probably meant g(x) = x/√(1+x²) Looks like f(x)=x+x^3/5 gets you two decimal digits everywhere [1], and you could improve that with more terms in the polynomial. Edit: you can derive f(x) by doing a series expansion of tanh(x)/√(1-tanh(x)²) about x=0, and Mathematica tells me the first few terms are f(x) = x + x^3/6 + x^5/120 + x^7/5040 + O(x^9) [1] https://www.desmos.com/calculator/zbyll5oeqk https://www.desmos.com/calculator/zbyll5oeqk
  - raphlinus 9y ago
    Oops, yes, you're correct, I was typing from memory and didn't double-check. And yes, the Taylor series is pretty good but you can usually squeeze a bit more accuracy-over-range by, eg, using an optimizer for the coefficients. Also, note that in your notebook you have x^3/5 but x^3/6 is probably what you wanted.
- conistonwater 9y ago
  Could be a typo, f(g(x)) with g(x)=x/√(1+x²) and f a polynomial makes more sense to me.

conistonwater 9y ago

Here's what atan looks like in openlibm: https://github.com/JuliaLang/openlibm/blob/1581174c85f7b645b15ba1ac1c3a98fb601f0fe7/src/s_atanf.c https://github.com/JuliaLang/openlibm/blob/1581174c85f7b645b... It's a degree-4 polynomial, with on division in the reduction atan2->atan, and at most one division in the argument reduction step in atan, giving an pretty accurate answer. By comparison, in [3] there is a degree-3 polynomial and the thing doesn't work outside [-1,1]. There is some kind of a tradeoff between accuracy and performance, but most of the time it's not worth it. Maybe if division is ludicrously expensive or something unusual like that. I suspect most performance gains that people are looking for come from omitting proper handling of special cases.

dr_zoidberg 9y ago
Hmmm... I'm a bit foggy on the specific quote, but in the Graphics Programming Black Book, specifically the part where Abrash covers writing fast code, he says something along the lines of: > Avoid special cases, because a special case means slow code So yeah, handling of special cases will bite you on the performance side. Sometimes it's inevitable, but if you have a lot of control (or you're very specific) of what values get passed as parameters, then you can get away with not handling special cases (or just handling the ones you care about).
- conistonwater 9y ago
  Yeah, but the people talking about finding their own interpolating polynomials and Pade approximations are looking for those approximations in the regular common cases, and omitting the special cases happens almost by accident. You could just take the same approximation used by openlibm or whatever and it's likely better than anything you yourself can come up with.

mooman219 9y ago

I actually wanted a fast atan2 about 3 years ago in Java and held a small competition to see what people could come up with [1]. In plain old java, it looks like it performed very well, I would expect it outperformed what they did in the post using LUTs. My methodology for micro benchmarks was pretty awful back then, so there's reason for error. The fastest was just 3 branches and a memory lookup. [1] http://www.java-gaming.org/topics/extremely-fast-atan2/36467/view.html http://www.java-gaming.org/topics/extremely-fast-atan2/36467...

rzzzt 9y ago
Additional magic is involved -- Math.atan2 is an intrinsic method in HotSpot, which will use a hand-coded implementation instead of the Java definition when possible: https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc
- mooman219 9y ago
  Math.Atan2 was well outperformed by the custom implementations in the post I linked. The native version isn't well optimized. Apache's Atan2 is just as accurate and about twice as fast for example.