Fast Inverse Square Root
The cluster centers on the Quake III fast inverse square root algorithm and related performance hacks for computing square roots, reciprocals, and trigonometric functions using techniques like CORDIC, Chebyshev approximations, Newton-Raphson, and lookup tables.
Activity Over Time
Top Contributors
Keywords
Sample Comments
Recent post on the same topic that gets the same information across with fewer words: https://kristerw.github.io/2021/10/19/fast-math/
Do we have another example than the famous quake fast square root function?
Fast inverse square root is an ultra-fancy hack for a very particular processor. Apollo's trigonometric functions are the most natural optimal approximation that could be done.
How do you compute the reciprocal without division? A precomputed lookup table?
Fast inverse square root as seen in Quake (as mentioned in other comments)https://en.wikipedia.org/wiki/Fast_inverse_square_root#Overv...
I tried 1/sqrt(9x-6) from .7 to 1e308, and got as one alternativesqrt(-.16666…)It did correctly mark this as 0% accurate, but I’m kinda curious as to where it came from.It does have a 1.1x speedup apparently. None of the other (more accurate) options provide a speedup. Maybe there aren’t any value options that provide a speedup, but the tool allows increasingly reduced accuracy (down to zero) until it finds a speedup?
The doom square root trick. Reducing an expensive function to almost nothing with low error. Many writeups on the web far better than I could give.
Nitpick: inverse square root is not a transcendental function.
Oof this is bad. If you're going to ask people to approximate, use a Chebyshev approximation please. You will do sin(x) faster than this and more accurately.
Fast inverse square root. Commonly attributed to john carmack, it actually predates his application of it by several years