[HN Gopher] Faster asin() was hiding in plain sight
___________________________________________________________________
Faster asin() was hiding in plain sight
Author : def-pri-pub
Score : 168 points
Date : 2026-03-11 14:35 UTC (8 hours ago)
(HTM) web link (16bpp.net)
(TXT) w3m dump (16bpp.net)
| erichocean wrote:
| Ideal HN content, thanks!
| orangepanda wrote:
| > Nobody likes throwing away work they've done
|
| I like throwing away work I've done. Frees up my mental capacity
| for other work to throw away.
| adampunk wrote:
| We love to leave faster functions languishing in library code.
| The basis for Q3A's fast inverse square root had been sitting in
| fdlibm since 1986, on the net since 1993:
| https://www.netlib.org/fdlibm/e_sqrt.c
| def-pri-pub wrote:
| Funny enough that fdlimb implementation of asin() did come up
| in my research. I believe it might have been more performant in
| the past. But taking a quick scan of `e_asin.c`, I see it doing
| something similar to the Cg asin() implementation (but with
| more terms and more multiplications, which my guess is that
| it's slower). I think I see it also taking more branches (which
| could also lead to more of a slowdown).
| adampunk wrote:
| Yeah Ng's work in fdlibm is cool and really clever in parts
| but a lot of branching. Some of the ways they reach correct
| rounding are...so cool.
| drsopp wrote:
| Did some quick calculations, and at this precision, it seems a
| table lookup might be able to fit in the L1 cache depending on
| the CPU model.
| Pannoniae wrote:
| Microbenchmarks. A LUT will win many of them but you pessimise
| the rest of the code. So unless a significant (read: 20+%)
| portion of your code goes into the LUT, there isn't that much
| point to bother. For almost any pure calculation without I/O,
| it's better to do the arithmetic than to do memory access.
| jcalvinowens wrote:
| Locality within the LUT matters too: if you know you're
| looking up identical or nearby-enough values to benefit from
| caching, an LUT can be more of a win. You only pay the cache
| cost for the portion you actually touch at runtime.
|
| I could imagine some graphics workloads tend compute asin()
| repeatedly with nearby input values. But I'd guess the
| locality isn't local enough to matter, only eight double
| precision floats fit in a cache line.
| groundzeros2015 wrote:
| I don't want to fill up L1 for sin.
| jcalvinowens wrote:
| Surely the loss in precision of a 32KB LUT for double precision
| asin() would be unacceptable?
| Jyaif wrote:
| By interpolating between values you can get excellent results
| with LUTs much smaller than 32KB. Will it be faster than the
| computation from op, that I don't know.
| jcalvinowens wrote:
| I'm very skeptical you wouldn't get perceptible visual
| artifacts if you rounded the trig functions to 4096 linear
| approximations. But I'd be happy to be proven wrong :)
| drsopp wrote:
| I experimented a bit with the code. Various tables with
| different datatypes. There is enough noise from the Monte
| Carlo to not make a difference if you use smaller data
| types than double or float. Even dropping interpolation
| worked fine, and got the speed to be on par with the best
| in the article, but not faster.
| jcalvinowens wrote:
| Does your benchmark use sequential or randomly ordered
| inputs? That would make a substantial difference with an
| LUT, I would think. But I'm guessing. Maybe 32K is so
| small it doesn't matter (if almost all of the LUT sits in
| the cache and is never displaced).
|
| > if you use smaller data types than double or float.
| Even dropping interpolation worked fine,
|
| That's kinda tautological isn't it? Of course reduced
| precision is acceptable where reduced precision is
| acceptable... I guess I'm assuming double precision was
| used for a good reason, it often isn't :)
| drsopp wrote:
| I didnt inspect the rest of the code but I guess the
| table is fetched from L2 on every call? I think the L1
| data cache is flooded by other stuff going on all the
| time.
|
| About dropping the interpolation: Yes you are right of
| course. I was thinking about the speed. No noticable
| speed improvement by dropping interpolation. The asin
| calls are only a small fraction of everything.
| scottlamb wrote:
| Isn't the faster approach SIMD [edit: or GPU]? A 1.05x to 1.90x
| speedup is great. A 16x speedup is better!
|
| They could be orthogonal improvements, but if I were
| prioritizing, I'd go for SIMD first.
|
| I searched for asin on Intel's intrinsics guide. They have a
| AVX-512 instrinsic `_mm512_asin_ps` but it says "sequence" rather
| than single-instruction. Presumably the actual sequence they use
| is in some header file somewhere, but I don't know off-hand where
| to look, so I don't know how it compares to a SIMDified version
| of `fast_asin_cg`.
|
| https://www.intel.com/content/www/us/en/docs/intrinsics-guid...
| TimorousBestie wrote:
| I don't know much about raytracing but it's probably tricky to
| orchestrate all those asin calls so that the input and output
| memory is aligned and contiguous. My uneducated intuition is
| that there's little regularity as to which pixels will take
| which branches and will end up requiring which asin calls, but
| I might be wrong.
| scottlamb wrote:
| I'd expect it to come down to data-oriented design: SoA
| (structure of arrays) rather than AoS (array of structures).
|
| I skimmed the author's source code, and this is where I'd
| start: https://github.com/define-private-
| public/PSRayTracing/blob/8...
|
| Instead of an `_objects`, I might try for a `_spheres`,
| `_boxes`, etc. (Or just `_lists` still using the virtual
| dispatch but for each list, rather than each object.) The
| `asin` seems to be used just for spheres. Within my
| `Spheres::closest_hit` (note plural), I'd work to SIMDify it.
| (I'd try to SIMDify the others too of course but apparently
| not with `asin`.) I think it's doable:
| https://github.com/define-private-
| public/PSRayTracing/blob/8...
|
| I don't know much about ray tracers either (having only
| written a super-naive one back in college) but this is the
| general technique used to speed up games, I believe. Besides
| enabling SIMD, it's more cache-efficient and minimizes
| dispatch overhead.
|
| edit: there's also stuff that you can hoist in this impl.
| Restructuring as SoA isn't strictly necessary to do that, but
| it might make it more obvious and natural. As an example,
| this `ray_dir.length_squared()` is the same for the whole
| list. You'd notice that when iterating over the spheres.
| https://github.com/define-private-
| public/PSRayTracing/blob/8...
| TimorousBestie wrote:
| This tracks with my experience and seems reasonable, yes. I
| tend to SoA all the things, sometimes to my coworkers'
| amusement/annoyance.
| def-pri-pub wrote:
| When I was working on this project, I was trying to
| restrict myself to the architecture of the original Ray
| Tracing in One Weekend book series. I am aware that things
| are not as SIMD friendly and that becomes a major bottle
| neck. While I am confident that an architectural change
| could yield a massive performance boost, it's something I
| don't want to spend my time on.
|
| I think it's also more fun sometimes to take existing
| systems and to try to optimize them given whatever
| constraints exist. I've had to do that a lot in my day job
| already.
| scottlamb wrote:
| I can relate to setting an arbitrary challenge for
| myself. fwiw, don't know where you draw the line of an
| architectural change, but I think that switching AoS ->
| SoA may actually be an approachably-sized mechanical
| refactor, and then taking advantage of it to SIMDify
| object lists can be done incrementally.
|
| The value of course is contingent on there being a decent
| number of objects of a given type in the list rather than
| just a huge number of rays being sent to a small number
| of objects; I didn't evaluate that. If it's the other way
| around, the structure would be better flipped, and I
| don't know how reasonable that is with bounces (that
| maybe then aren't all being evaluated against the same
| objects?).
| Am4TIfIsER0ppos wrote:
| I don't do much float work but I don't think there is a single
| regular sine instruction only old x87 float stack ones.
|
| I was curious what "sequence" would end up being but my
| compiler is too old for that intrinsic. Even godbolt didn't
| help for gcc or clang but it did reveal that icc produced a
| call https://godbolt.org/z/a3EsKK4aY
| nitwit005 wrote:
| If you click libraries on godbolt, it's pulling in a bunch,
| including multiple SIMD libraries. You might have to fiddle
| with the libraries or build locally.
| AlotOfReading wrote:
| 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.
| def-pri-pub wrote:
| > floating point bithacks
|
| The forbidden magic
| chuckadams wrote:
| You brought Zalgo. I blame this decade on you.
| moffkalast wrote:
| > float asinine(float x) {
|
| FTFY :P
| adampunk wrote:
| // what the fuck
| jacquesm wrote:
| That could do with some subtitles.
| irishcoffee wrote:
| https://en.wikipedia.org/wiki/Fast_inverse_square_root
| LegionMammal978 wrote:
| In general, I find that minimax approximation is an
| underappreciated tool, especially the quite simple Remez
| algorithm to generate an optimal polynomial approximation [0].
| With some modifications, you can adapt it to optimize for either
| absolute or relative error within an interval, or even come up
| with rational-function approximations. (Though unfortunately,
| many presentations of the algorithm use overly-simple forms of
| sample point selection that can break down on nontrivial input
| curves, especially if they contain small oscillations.)
|
| [0] https://en.wikipedia.org/wiki/Remez_algorithm
| jason_s wrote:
| Not sure I would call Remez "simple"... it's all relative; I
| prefer Chebyshev approximation which is simpler than Remez.
| stephencanon wrote:
| Ideally either one is just a library call to generate the
| coefficients. Remez can get into trouble near the endpoints
| of the interval for asin and require a little bit of manual
| intervention, however.
| LegionMammal978 wrote:
| Perhaps, but at least I find it very simple for the
| optimality properties it gives: there is no inherent need to
| say, "I know that better parameters likely exist, but the
| algorithm to find them would be hopelessly expensive," as is
| the case in many forms of minimax optimization.
| herf wrote:
| They teach a lot of Taylor/Maclaurin series in Math classes
| (and trig functions are sometimes called "CORDIC" which is an
| old method too) but these are not used much in actual FPUs and
| libraries. Maybe we should update the curricula so people know
| better ways.
| bee_rider wrote:
| Taylor series makes a lot more sense in a math class, right?
| It is straightforward and (just for example), when you are
| thinking about whether or not a series converges in the
| limit, why care about the quality of the approximation after
| a set number of steps?
| stephc_int13 wrote:
| My favorite tool to experiment with math approximation is
| lolremez. And you can easily ask your llm to do it for you.
| glitchc wrote:
| 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 connected to some dedicated
| memory cells in hardware.
| kstrauser wrote:
| > The 4% improvement doesn't seem like it's worth the effort.
|
| People have gotten PhDs for smaller optimizations. I know. I've
| worked with them.
|
| > instructions like division and square root are roughly equal
| to trig functions in cycle count on modern CPUs.
|
| What's the x86-64 opcode for arcsin?
| adrian_b wrote:
| Presumably the poster meant polynomial approximations of
| trigonometric functions not instructions for trigonometric
| functions, which are missing in most CPUs, though many GPUs
| have such instructions.
|
| x86-64 had instructions for the exponential and logarithmic
| functions in Xeon Phi, but those instructions have been
| removed in Skylake Server and the later Intel or AMD CPUs
| with AVX-512 support.
|
| However, instructions for trigonometric functions have no
| longer been added after Intel 80387, and those of 8087 and
| 80387 are deprecated.
| glitchc wrote:
| > What's the x86-64 opcode for arcsin?
|
| Not required. ATAN and SQRTS(S|D) are sufficient, the half-
| angle approach in the article is the recommended way.
|
| > People have gotten PhDs for smaller optimizations. I know.
| I've worked with them.
|
| I understand the can, not sure about the should. Not trying
| to be snarky, we just seem to be producing PhDs with the
| slimmest of justifications. The bar needs to be higher.
| kstrauser wrote:
| > I understand the can, not sure about the should. Not
| trying to be snarky, we just seem to be producing PhDs with
| the slimmest of justifications. The bar needs to be higher.
|
| I couldn't disagree more. Sure, making a 4% faster asin
| isn't going to change the world, but if it makes all
| callers a teensy bit faster, multiplied by the number of
| callers using it, then it adds up. Imagine the savings for
| a hyperscaler if they managed to made a more common
| instruction 4% faster.
| charcircuit wrote:
| The effort of typing about 10 words into a LLM is minimal.
| tverbeure wrote:
| > 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.
| def-pri-pub wrote:
| You'd be surprised how it actually is worth the effort, even
| just a 1% improvement. If you have the time, this is a great
| talk to listen to: https://www.youtube.com/watch?v=kPR8h4-qZdk
|
| For a little toy ray tracer, it is pretty measly. But for a
| larger corporation (with a professional project) a 4% speed
| improvement can mean MASSIVE cost savings.
|
| Some of these tiny improvements can also have a cascading
| effect. Imagining finding a +4%, a +2% somewhere else, +3% in
| neighboring code, and a bunch of +1%s here and there.
| Eventually you'll have built up something that is 15-20%
| faster. Down the road you'll come across those optimizations
| which can yield the big results too (e.g. the +25%).
| glitchc wrote:
| It's a cool talk, but the relevance to the present problem
| escapes me.
|
| If you're alluding to gcc vs fbstring's performance (circa
| 15:43), then the performance improvement is not because
| fbstring is faster/simpler, but due to a foundational gcc
| design decision to always use the heap for string variables.
| Also, at around 16:40, the speaker concedes that gcc's
| simpler size() implementation runs significantly faster (3x
| faster at 0.3 ns) when the test conditions are different.
| jason_s wrote:
| While I'm glad to see the OP got a good minimax solution at the
| end, it seems like the article missed clarifying one of the key
| points: error waveforms over a specified interval are critical,
| and if you don't see the characteristic minimax-like wiggle,
| you're wasting easy opportunity for improvement.
|
| Taylor series in general are a poor choice, and Pade approximants
| of Taylor series are equally poor. If you're going to use Pade
| approximants, they should be of the original function.
|
| I prefer Chebyshev approximation:
| https://www.embeddedrelated.com/showarticle/152.php which is
| often close enough to the more complicated Remez algorithm.
| ogogmad wrote:
| Chebyshev polynomials cos(n arcos(x)) provide one of the proofs
| that every continuous function f:[0,1]->R can be uniformly
| approximated by polynomial functions. Bernstein polynomials
| provide a shorter proof, but perhaps not the best numerical
| method:
| https://en.wikipedia.org/wiki/Bernstein_polynomial#See_also
| exmadscientist wrote:
| 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 you're
| just looking for something quick-n-dirty for whatever reason, or
| are willing to invest research-paper levels of time and effort)
| and to think that someone would call Abramowitz and Stegun "a
| math textbook from the 60s" is kind of funny. It's got a similar
| level of importance to its field as Knuth's Art of Computer
| Programming or stuff like that. It's not an obscure text. Yeah,
| you might forget what all is in it if you don't use it often, but
| you'd go "oh, of _course_ that would be in there, wouldn 't
| it...."
| wolfi1 wrote:
| Abramowitz/Stegun has been updated 2010 and resides now here:
| https://dlmf.nist.gov/
| def-pri-pub wrote:
| 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.
| neutronicus wrote:
| It is not a textbook, it is an extremely dense reference
| manual, so that honestly makes sense.
|
| In physics grad school, professors would occasionally allude
| to it, and textbooks would cite it ... pretty often. So it's
| a thing anyone with postgraduate physics education should
| know exists, but you wouldn't ever be _assigned it_.
| axus wrote:
| In this case, AI understood history better than the human.
| bsder wrote:
| Yeah, if you want something that's somewhat obscure, pull up
| Cody and Waite "Software Manual for the Elementary Functions".
|
| And, lo and behold, the ASIN implementation is minimax.
| ok123456 wrote:
| Chebyshev approximation for asin is sum(2 _T_n(x) / (pi*n*n),n),
| the even terms are 0._
| empiricus wrote:
| Does anyone knows the resources for the algos used in the HW
| implementations of math functions? I mean the algos inside the
| CPUs and GPUs. How they make a tradeoff between transistor
| number, power consumption, cycles, which algos allow this.
| groos wrote:
| Here's one way to do it.
|
| https://en.wikipedia.org/wiki/CORDIC
| xt00 wrote:
| To be accurate, this is originally from Hastings 1955, Princeton
| "APPROXIMATIONS FOR DIGITAL COMPUTERS BY CECIL HASTINGS", page
| 159-163, there are actually multiple versions of the
| approximation with different constants used. So the original work
| was done with the goal of being performant for computers of the
| 1950's. Then the famous Abramowitz and Stegun guys put that in
| formula 4.4.45 with permission, then the nvidia CG library wrote
| some code that was based upon the formula, likely with some
| optimizations.
| sixo wrote:
| It appears that the real lesson here was to lean quite a bit more
| on theory than a programmer's usual roll-your-own heuristic would
| suggest.
|
| A fantastic amount of collective human thought has been dedicated
| to function approximations in the last century; Taylor methods
| are over 200 years old and unlikely to come close to state-of-
| the-art.
| cmovq wrote:
| > 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
| def-pri-pub wrote:
| I did see that, but isn't the vast majority of that page
| talking about acos() instead?
| seanhunter wrote:
| That's equivalent right? acos x = pi/2 - asin x
|
| So if you've got one that's fast you have them both.
| varispeed wrote:
| If you are interested in such "tricks", you should check out the
| classic Hacker's Delight by Henry Warren
| debo_ wrote:
| https://bash-org-archive.com/?427792
| andyjohnson0 wrote:
| Interesting article. A few years back I implemented a bunch of
| maths primitives, including trig functions, using Taylor
| sequences etc, to see how it was done. An interesting challenge,
| even at the elementary level I was working at.
|
| So this article got me wondering how much accuracy is needed
| before computing a series beats pre-computed lookup tables and
| interpolation. Anyone got any relevant experience to share?
|
| How much accuracy does ray tracing require?
| peterabbitcook wrote:
| I am curious, did you check how much your benchmarks moved (time
| and errors) if at all if you told the compiler to use
| ---use_fast_math or -ffast-math?
|
| There's generally not a faster version of inverse trig functions
| to inline, but it might optimize some other stuff out.
|
| Unrelated to that, I've seen implementations (ie
| julia/base/special/trig) that use a "rational approximation" to
| asin, did you go down that road at any point?
___________________________________________________________________
(page generated 2026-03-11 23:01 UTC)