Re:Everything I Know About the Fast Inverse Square Root Algo...
by bnprks on Sunday June 02, 2024 @07:48PM
(#40558055)
Amusingly, (to me at least) there's also an SSE instruction for non-reciprocal square roots but it's so much slower than reciprocal square root that calculating sqrt(x) as x * 1/sqrt(x) is faster assuming you can tolerate the somewhat reduced precision.
Re:Everything I Know About the Fast Inverse Square Root Algo...
by mabster on Sunday June 02, 2024 @08:23PM
(#40558223)
I wouldn't be surprised if _mm_rsqrt_ps is actually implemented using the same bit level trick.
Same as Carmack's, we did a single step of Newton's method and it was definitely good enough.
Re:Everything I Know About the Fast Inverse Square Root Algo...
by pclmulqdq on Sunday June 02, 2024 @11:26PM
(#40559063)
Intel provides bit-accurate code. In older chips it used a faithful bipartite ROM:
https://web.archive.org/web/20120124193536id_/http://www.acs...
Re:Everything I Know About the Fast Inverse Square Root Algo...
by mabster on Tuesday June 04, 2024 @03:53AM
(#40571801)
I don't recall the coprocessor having either reciprocal or reciprocal square root? I didn't do much Intel until later in my career though, so I might be missing something though.
Both _mm_rcp_ps (rcpps) and _mm_rsqrt_ps (rsqrtps) are only good for about half the bits.
Re:Everything I Know About the Fast Inverse Square Root Algo...
by Findecanor on Sunday June 02, 2024 @10:04PM
(#40558742)
I dunno about Intel and AMD, but ARM and RISC-V use lookup tables for rsqrt. Unlike AMD and Intel, those tables are precisely defined in their respective specs.
Re:Everything I Know About the Fast Inverse Square Root Algo...
by kragen on Sunday June 02, 2024 @10:23PM
(#40558830)
the vast, vast majority of computers do not support the sse instruction set or indeed any of the i386 and amd64 instruction set at all, and the fraction of computers that do support them (other than through emulation) is continually shrinking
gpu instruction sets, arm, risc-v, avr, pic, 8051, fpga... of course, in many cases, these do have a built-in approximate reciprocal square root operation, but probably implemented with this algorithm
Re:Everything I Know About the Fast Inverse Square Root Algo...
by colejohnson66 on Monday June 03, 2024 @07:18AM
(#40561539)
In terms of CPUs where you would use an inverse square root (mainly games or scientific), x86 still reigns supreme.
Re:Everything I Know About the Fast Inverse Square Root Algo...
by kragen on Monday June 03, 2024 @03:37PM
(#40566656)
gpus reign supreme for games and scientific, and none of them are x86; larrabee failed. and you'd be surprised at the 3-d kinematics and control systems that people do with microcontrollers
Re:Everything I Know About the Fast Inverse Square Root Algo...
by khangaroo on Sunday June 02, 2024 @10:51PM
(#40558934)
The SSE float reciprocal instructions have slightly different results between Intel and AMD, which can be a source of headaches for those expecting deterministic results between PCs. (see https://robert.ocallahan.org/2021/09/rr-trace-portability-di...)
Re:Everything I Know About the Fast Inverse Square Root Algo...
by kragen on Tuesday June 11, 2024 @05:48PM
(#40651985)
the vast, vast majority of computers do not support the sse instruction set or indeed any of the i386 and amd64 instruction set at all, and the fraction of computers that do support them, other than through emulation, is continually shrinking
gpu instruction sets, arm, risc-v, avr, pic, 8051, fpga... of course, in many cases, these do have a built-in approximate reciprocal square root operation, but probably implemented with this algorithm
That being said, the techniques discussed here are not totally irrelevant (yet). There still exists some hardware with fast instructions for float/int conversion, but lacking rsqrt, sqrt, pow, log instructions, which can all be approximated with this nice trick.