Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster asin() was hiding in plain sight

16bpp.net

Post reply on HN
Print view View original

51–60 of 140 posts

Re: Faster asin() was hiding in plain sight

#51

Post by Sesse__ »

patchnull wrote: post #50

[flagged]

And similarly, entire generations of programmers were never taught Horner's scheme. You can see it in the article, where they write stuff like

  A * x * x * x * x * x * x + B * x * x * x * x + C * x * x + D
(10 muls, 3 muladds)

instead of the faster

  tmp = x * x;
  ((A * tmp + B) * tmp + C) * tmp + D
(1 mul, 3 muladds)

Re: Faster asin() was hiding in plain sight

#52

Post by david-gpu »

patchnull wrote: post #50

[flagged]

Yeah, I once worked at a place where the compiler team was assigned the unpleasant task of implementing a long list of trigonometry functions. They struggled for many months to get the accuracy that was required of them, and when they did the performance was abysmal compared to the competition.

In hindsight, they probably didn't have anybody with the right background and should have contracted out the job. I certainly didn't have the necessary knowledge, either.

Re: Faster asin() was hiding in plain sight

#53

Post by zahlman »

Sesse__ wrote: post #51
patchnull wrote: post #50

[flagged]

And similarly, entire generations of programmers were never taught Horner's scheme. You can see it in the article, where they write stuff like A * x * x * x * x * x * x + B * x * x * x * x + C * x * x + D (10 muls, 3 muladds) instead of the faster tmp = x * x; ((A * tmp + B) * tmp + C) * tmp + D (1 mul, 3 muladds)

Is this outside of what compilers can do nowadays? (Or do they refuse because it's floating-point?)

Re: Faster asin() was hiding in plain sight

#54

Post by tverbeure »

glitchc wrote: post #22

The 4% improvement doesn't seem like it's worth the effort. On a general note, instructions like division and square root are roughly equal to trig functions in cycle count on modern CPUs. So, replacing one with the other will not confer much benefit, as evidenced from the results. They're all typically implemented using LUTs, and it's hard to beat the performance of an optimized LUT, which is basically a multiplexer…

> The 4% improvement doesn't seem like it's worth the effort.

I've spent the past few months improving the performance of some work thing by ~8% and the fun I've been having reminds me of the nineties, when I tried to squeeze every last % of performance out of the 3D graphics engine that I wrote as a hobby.

Re: Faster asin() was hiding in plain sight

#55

Post by def-pri-pub »

Pannoniae wrote: post #19
stephencanon wrote: post #18

Earlier quoted context omitted.

These sorts of approximations (and more sophisticated methods) are fairly widely used in systems programming, as seen by the fact that Apple's asin is only a couple percent slower and sub-ulp accurate ( https://members.loria.fr/PZimmermann/papers/accuracy.pdf ). I would expect to get similar performance on non-Apple x86 using Intel's math library, which does not seem to have been measured, and significantly better pe…

Yeah, the only big problem with approx. sqrt is that it's not consistent across systems, for example Intel and AMD implement RSQRT differently... Fine for graphics, but if you need consistency, that messes things up.

Wait, what? Do you have a resource I could read up on about that? That is moderately concerning if your math isn't portable across chips.

Re: Faster asin() was hiding in plain sight

#56

Post by 3371 »

Sesse__ wrote: post #51
patchnull wrote: post #50

[flagged]

And similarly, entire generations of programmers were never taught Horner's scheme. You can see it in the article, where they write stuff like A * x * x * x * x * x * x + B * x * x * x * x + C * x * x + D (10 muls, 3 muladds) instead of the faster tmp = x * x; ((A * tmp + B) * tmp + C) * tmp + D (1 mul, 3 muladds)

Isn't that for... readability...?

Re: Faster asin() was hiding in plain sight

#57

Post by def-pri-pub »

exmadscientist wrote: post #32

This line: > This amazing snippet of code was languishing in the docs of dead software, which in turn the original formula was scrawled away in a math textbook from the 60s. was kind of telling for me. I have some background in this sort of work (and long ago concluded that there was pretty much nothing you can do to improve on existing code, unless either you have some new specific hardware or domain constraint, or…

These are books that my uni courses never had me read. I'm a little shocked at times at how my degree program skimped on some of the more famous texts.

Re: Faster asin() was hiding in plain sight

#58

Post by cmovq »

> After all of the above work and that talk in mind, I decided to ask an LLM.

Impressive that an LLM managed to produce the answer from a 7 year old stack overflow answer all on its own! [1] This would have been the first search result for “fast asin” before this article was published.

[1]: https://stackoverflow.com/a/26030435

Re: Faster asin() was hiding in plain sight

#59

Post by arkmm »

Sesse__ wrote: post #51
patchnull wrote: post #50

[flagged]

And similarly, entire generations of programmers were never taught Horner's scheme. You can see it in the article, where they write stuff like A * x * x * x * x * x * x + B * x * x * x * x + C * x * x + D (10 muls, 3 muladds) instead of the faster tmp = x * x; ((A * tmp + B) * tmp + C) * tmp + D (1 mul, 3 muladds)

Didn't know this technique had a name, but I would think a modern compiler could make this optimization on its own, no?

Re: Faster asin() was hiding in plain sight

#60

Post by irishcoffee »

jacquesm wrote: post #49
AlotOfReading wrote: post #11

I'm pretty sure it's not faster, but it was fun to write: float asin(float x) { float x2 = 1.0f-fabs(x); u32 i = bitcast(x2); i = 0x5f3759df - (i>>1); float inv = bitcast(i); return copysign(pi/2-pi/2*(x2*inv),x); } Courtesy of evil floating point bithacks.

That could do with some subtitles.

https://en.wikipedia.org/wiki/Fast_inverse_square_root
Post reply on HN