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

51–60 of 60 posts

Re: Improving the fast inverse square root (2010)

#51

Post by stephencanon »

piyush_soni wrote: post #28
zbjornson wrote: post #26

Earlier quoted context omitted.

VRSQRT28 too, which has max 2^-28 rel error. https://software.intel.com/en-us/articles/reference-implemen...

Thanks, I came here to ask the similar question about native optimizations on this 'hack'. Apologies for my lack of knowledge, but I'm a little confused on which one to use out of all these variants while compiling C++ code on a 64 bit platform for the standard 'float' type inverse square root? Are there varying levels of compromise between speed and accuracy among all these methods? Thanks ...

For a generic 64b platform, use RSQRTSS/RSQRTPS, since it's the only one that will exist. The others are specific to rather new hardware.

My recollection is that it's accurate to 11.5 bits, so after one refinement step you have nearly full precision (an error bound of a couple ULP). Check Intel's docs for more details.

Re: Improving the fast inverse square root (2010)

#52

Post by GuB-42 »

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…

From the author:

What is it: implicit surfaces raymarching using binary search. The shapes get "blown up" according to step size, which fakes the ambient occlusion feel (also necessary for the bisection to work). Color is the number of missed probes minus log(last step size), which had the most bearable artifacts.

- implicit surfaces are surfaces defined as the solution of an equation f(x,y,z)=0

- raymarching is a raytracing technique where you advance step by step along the ray, it is a very common technique for sizecoding. The rest of the description detail the rendering tricks used for shading and coloring.

The "content" does not "use the same byte as code", it is code, in the form of the implicit surface equation.

Re: Improving the fast inverse square root (2010)

#54

Post by mmozeiko »

MaxBarraclough wrote: post #33
slavik81 wrote: post #31

Earlier quoted context omitted.

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...

That is not quite true. You don't need to use GCC __builtin functions for this. GCC supports SSE1 intrinsics like _mm_rsqrt_ss exactly same as MSVC - it is declared in xmmintrin.h header. Just include it and _mm_rsqrt_ss/ps will be available for you in gcc and msvc.

Re: Improving the fast inverse square root (2010)

#55

Post by [deleted] »

StefanKarpinski wrote: post #41
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...

I think you’ve hit the nail on the head: > it could also be interpreted as ... [the] inverse of the square root (which is just the squaring operation) Since the other obvious interpretation is not very useful and has a clearer name—i.e. “the square”—the term “inverse square root” has only one useful meaning, which is therefore how it’s interpreted. (I don’t follow the second option about binary operators.) Mathematic…

[deleted]

Re: Improving the fast inverse square root (2010)

#56

Post by convolvatron »

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…

this is wildly off topic, but can anyone from either the scientific or the graphics community comment on the practical impact of losing denorms? i certainly understand that it softens the impact of underflow, but does anyone care?

Re: Improving the fast inverse square root (2010)

#57

Post by majewsky »

meta_AU wrote: post #40
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.

The point is that "inverse" usually refers to the function that reverses the effect of the original function, i.e.

  f_inv(f(x)) = x for all x in Domain(f)
g(x) = 1 / sqrt(x) is not the inverse of f(x) = sqrt(x) in this sense.

Re: Improving the fast inverse square root (2010)

#58

Post by [deleted] »

edynoid wrote: post #36
slavik81 wrote: post #31

Earlier quoted context omitted.

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.

[deleted]

Re: Improving the fast inverse square root (2010)

#59

Post by piyush_soni »

stephencanon wrote: post #51
piyush_soni wrote: post #28

Earlier quoted context omitted.

Thanks, I came here to ask the similar question about native optimizations on this 'hack'. Apologies for my lack of knowledge, but I'm a little confused on which one to use out of all these variants while compiling C++ code on a 64 bit platform for the standard 'float' type inverse square root? Are there varying levels of compromise between speed and accuracy among all these methods? Thanks ...

For a generic 64b platform, use RSQRTSS/RSQRTPS, since it's the only one that will exist. The others are specific to rather new hardware. My recollection is that it's accurate to 11.5 bits, so after one refinement step you have nearly full precision (an error bound of a couple ULP). Check Intel's docs for more details.

Thanks!

Re: Improving the fast inverse square root (2010)

#60

Post by simonbyrne »

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.

Ah, I should have done more googling. I guess the AVX-512 ones are marginally more accurate?
Post reply on HN