Fast Inverse Square Root

#1

Post by timhh » Sun, Nov 01, 2020, 12:58 PM UTC

Fast Inverse Square Root
timmmm.github.io

Re: Fast Inverse Square Root

#2

Post by timhh » Sun, Nov 01, 2020, 1:04 PM UTC

This is an explanation of the fast inverse square root that I hope is easy to understand. I also managed to improve on it a little bit.

Re: Fast Inverse Square Root

#3

Post by recursive » Mon, Nov 02, 2020, 10:49 PM UTC

timhh wrote: post #2

This is an explanation of the fast inverse square root that I hope is easy to understand. I also managed to improve on it a little bit.

Thanks for this. I have one nit. You show `q = 1598029824 - u/2;` as being identical to `q = 0x5F400000 - u >> 1;`, but every language I know of uses a different order of operations, giving different results. It might be clearest to provide parentheses in the second case.

Re: Fast Inverse Square Root

#4

Post by jedbrown » Mon, Nov 02, 2020, 10:49 PM UTC

It may be useful to mention that modern architectures often have vectorized instructions like vrsqrt14ps (accessible via the _mm512_rsqrt14_ps intrinsic) that provides a 14-bit approximation (there are more accurate variants too) in every lane with an inverse throughput of 2. These are faster than the integer bit hacks.

https://software.intel.com/sites/landingpage/IntrinsicsGuide...

Re: Fast Inverse Square Root

#5

Post by Greek0 » Mon, Nov 02, 2020, 10:56 PM UTC

Here's another article (from 2012) describing the same calculation:

http://h14s.p5r.org/2012/09/0x5f3759df.html

Re: Fast Inverse Square Root

#6

Post by apocalypses » Mon, Nov 02, 2020, 11:11 PM UTC

jedbrown wrote: post #4

It may be useful to mention that modern architectures often have vectorized instructions like vrsqrt14ps (accessible via the _mm512_rsqrt14_ps intrinsic) that provides a 14-bit approximation (there are more accurate variants too) in every lane with an inverse throughput of 2. These are faster than the integer bit hacks. https://software.intel.com/sites/landingpage/IntrinsicsGuide...

Though worth noting only for specific AVX-512 CPUs.

Though you can still have vectorised support for regular precision for AVX2.

Re: Fast Inverse Square Root

#7

Post by adamnemecek » Mon, Nov 02, 2020, 11:24 PM UTC

God, this is such an old meme at this point. What's next, telling me how good lisp is?

Re: Fast Inverse Square Root

#8

Post by usmannk » Mon, Nov 02, 2020, 11:27 PM UTC

recursive wrote: post #3

timhh wrote: post #2

This is an explanation of the fast inverse square root that I hope is easy to understand. I also managed to improve on it a little bit.

Thanks for this. I have one nit. You show `q = 1598029824 - u/2;` as being identical to `q = 0x5F400000 - u >> 1;`, but every language I know of uses a different order of operations, giving different results. It might be clearest to provide parentheses in the second case.

Interestingly enough it seems to do the shift first in Swift

Re: Fast Inverse Square Root

#9

Post by IMTDb » Mon, Nov 02, 2020, 11:29 PM UTC

adamnemecek wrote: post #7

God, this is such an old meme at this point. What's next, telling me how good lisp is?

Obligatory XKCD: https://xkcd.com/1053/

Re: Fast Inverse Square Root

#10

Post by jedbrown » Mon, Nov 02, 2020, 11:34 PM UTC

apocalypses wrote: post #6

jedbrown wrote: post #4

It may be useful to mention that modern architectures often have vectorized instructions like vrsqrt14ps (accessible via the _mm512_rsqrt14_ps intrinsic) that provides a 14-bit approximation (there are more accurate variants too) in every lane with an inverse throughput of 2. These are faster than the integer bit hacks. https://software.intel.com/sites/landingpage/IntrinsicsGuide...

Though worth noting only for specific AVX-512 CPUs. Though you can still have vectorised support for regular precision for AVX2.

_mm256_rsqrt_ps is 12-bit accuracy in AVX.

https://software.intel.com/sites/landingpage/IntrinsicsGuide...