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

Improving the fast inverse square root (2010)

rrrola.wz.cz

Post reply on HN
Print view View original

31–40 of 60 posts

Re: Improving the fast inverse square root (2010)

#31

Post by slavik81 »

mmozeiko wrote: post #17
simonbyrne wrote: post #9

It is worth noting that with AVX-512, Intel has introduced a native inverse sqrt approximation (VRSQRT14).

Inverse sqrt approximation is available since SSE1 with rsqrtss & rsqrtps instructions.

Which is nice because SSE1 and SSE2 are mandatory parts of x86_64. If you're a 64bit application for desktop, you can use rsqrtss without any checks or fallbacks.

Unfortunately, it doesn't tend to get used automatically in languages like C. The result of rsqrtss is slightly different from 1/sqrtf(x) as two seperate operations, so it cannot be applied as an optimization.

If the rules for floating point optimization are loosened by passing -ffast-math to GCC, the compiler will use it. That being said, -ffast-math is a shotgun that affects a lot of things. If you need signed zeros, Infs, NaNs or denormals that flag may break your program.

Re: Improving the fast inverse square root (2010)

#32

Post by toolslive »

dnautics wrote: post #10
oranlooney wrote: post #2

That's great and all, but nobody needs a 32-bit anything in 2018. This undergraduate paper provides a magic number and associated error bound for 64-bit doubles: https://cs.uwaterloo.ca/~m32rober/rsqrt.pdf

Even scientific calculation would be fine with 32 bit floats, but average floating point error due to representation creeps with ON (iirc) over N multiplications, so you have to use 64 bit for many scientific applications to get satisfactory results after a million or a trillion multiplications.

What they typically do in 3d gaming is update the matrix that holds the transformation by a left multiplication, every time the camera changes. So

Tn = U_{n-1} * U_{n-2} * .... * U_0 * T_0

After a while,your matrix accumulates errors, but it's easy to just start and take a fresh one.

Re: Improving the fast inverse square root (2010)

#33

Post by MaxBarraclough »

slavik81 wrote: post #31
mmozeiko wrote: post #17

Earlier quoted context omitted.

Inverse sqrt approximation is available since SSE1 with rsqrtss & rsqrtps instructions.

Which is nice because SSE1 and SSE2 are mandatory parts of x86_64. If you're a 64bit application for desktop, you can use rsqrtss without any checks or fallbacks. Unfortunately, it doesn't tend to get used automatically in languages like C. The result of rsqrtss is slightly different from 1/sqrtf(x) as two seperate operations, so it cannot be applied as an optimization. If the rules for floating point optimization ar…

> -ffast-math is a shotgun that affects a lot of things

Interesting point. GCC and MSVC both seem to have (incompatible) intrinsic functions, for what that's worth.

https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcc/X86-Built-in-Fu...

https://docs.microsoft.com/en-us/previous-versions/visualstu...

Re: Improving the fast inverse square root (2010)

#34

Post by jacquesm »

minton wrote: post #3
oranlooney wrote: post #2

That's great and all, but nobody needs a 32-bit anything in 2018. This undergraduate paper provides a magic number and associated error bound for 64-bit doubles: https://cs.uwaterloo.ca/~m32rober/rsqrt.pdf

I think this article is from 2010.

That's not relevant there are plenty of single precision float applications today (and many fixed point applications as well). It all depends on your workload.

Re: Improving the fast inverse square root (2010)

#35

Post by 21 »

oranlooney wrote: post #2

That's great and all, but nobody needs a 32-bit anything in 2018. This undergraduate paper provides a magic number and associated error bound for 64-bit doubles: https://cs.uwaterloo.ca/~m32rober/rsqrt.pdf

Funny, in 2018 a lot of people are asking for 16-bit floats.

https://en.wikipedia.org/wiki/Half-precision_floating-point_...

Re: Improving the fast inverse square root (2010)

#36

Post by edynoid »

slavik81 wrote: post #31
mmozeiko wrote: post #17

Earlier quoted context omitted.

Inverse sqrt approximation is available since SSE1 with rsqrtss & rsqrtps instructions.

Which is nice because SSE1 and SSE2 are mandatory parts of x86_64. If you're a 64bit application for desktop, you can use rsqrtss without any checks or fallbacks. Unfortunately, it doesn't tend to get used automatically in languages like C. The result of rsqrtss is slightly different from 1/sqrtf(x) as two seperate operations, so it cannot be applied as an optimization. If the rules for floating point optimization ar…

I find it quite fortunate, that they don't use it automatically. Introducing a 1e-3 relative error is quite a deal breaker for some. Not for games sure, but for science that is mostly unacceptable.

Re: Improving the fast inverse square root (2010)

#37

Post by Waterluvian »

skrebbel wrote: post #29

Pretty much off topic, but Řrřola, the author of this blog post, also makes mind blowing 256 byte demos. E.g. Puls from 2009: https://www.pouet.net/prod.php?which=53816 (check the youtube link if you don't have an MS-DOS ready) I understand little about extreme sizecoding, but I suspect it's a similarly obsessed mathy story as this blog post, to double use the same bytes as code and content in a way that things actua…

I heard some Nintendo games does that with sprites or sounds that can take on a random-ish look. Very very cool.

Re: Improving the fast inverse square root (2010)

#38

Post by andybest »

Waterluvian wrote: post #37
skrebbel wrote: post #29

Pretty much off topic, but Řrřola, the author of this blog post, also makes mind blowing 256 byte demos. E.g. Puls from 2009: https://www.pouet.net/prod.php?which=53816 (check the youtube link if you don't have an MS-DOS ready) I understand little about extreme sizecoding, but I suspect it's a similarly obsessed mathy story as this blog post, to double use the same bytes as code and content in a way that things actua…

I heard some Nintendo games does that with sprites or sounds that can take on a random-ish look. Very very cool.

Yars' Revenge on the Atari 2600 used the game code as random input to generate the graphics for the 'safe zone'

Re: Improving the fast inverse square root (2010)

#39

Post by narkee »

How is it that inverse seems to be used as "multiplicative inverse" in this context? It seems like a really ambiguous term, because it could also be interpreted as either:

inverse of the square root (which is just the squaring operation), or

the inverse of some other binary operator, like addition or anything else...

Re: Improving the fast inverse square root (2010)

#40

Post by meta_AU »

narkee wrote: post #39

How is it that inverse seems to be used as "multiplicative inverse" in this context? It seems like a really ambiguous term, because it could also be interpreted as either: inverse of the square root (which is just the squaring operation), or the inverse of some other binary operator, like addition or anything else...

It is the inverse of the square root. If you want to normalise a vector, you divide the components by the length. The length is the sqrt of the sum squares (Pythagoras). Divide is more expensive than multiply. So get the inverse sqrt of the sum of the squared components, then multiply the components by the inverse sqrt.
Post reply on HN