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

41–50 of 60 posts

Re: Improving the fast inverse square root (2010)

#41

Post by StefanKarpinski »

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.) Mathematical terminology and notation in general are full of ambiguities which are resolved by extensive contextual knowledge. As noted by a sibling comment, calling it the reciprocal square root would be clearer.

Re: Improving the fast inverse square root (2010)

#42

Post by n4r9 »

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

A better phrase would be "reciprocal square root".

Re: Improving the fast inverse square root (2010)

#43

Post by stephencanon »

zbjornson wrote: post #26
simonbyrne wrote: post #9

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

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

Note that VRSQRT28 is in AVX-512ER, which is Xeon Phi only.

Re: Improving the fast inverse square root (2010)

#44

Post by duckerude »

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.

I wanted to put over a billion floats in a numpy array just a few months ago. Making them 16-bit saved a lot of memory.

It doesn't matter how much resource limits increase, people are going to keep hitting them. And when they hit them, using a smaller data type will always help.

Re: Improving the fast inverse square root (2010)

#46

Post by meta_AU »

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.

From memory, GCC does one NewtonRaphson iteration on the approximate result so the error is much lower (closer to e-9 from memory again). They don't use the approximation directly in fast-math mode.

Re: Improving the fast inverse square root (2010)

#47

Post by whyever »

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.

> Even scientific calculation would be fine with 32 bit floats

It really depends on the algorithms in question and the error tolerances.

Re: Improving the fast inverse square root (2010)

#49

Post by jadedhacker »

perfmode wrote: post #7
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

deep learning uses low precision floats sometimes as few as 8 bits are needed

I think gen 1 or gen 2 of the TPU explicitly supported short ints.

Re: Improving the fast inverse square root (2010)

#50

Post by dustmop »

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

Yes, "inverse" could perhaps be more clearly stated as "inverted". I've heard the term used this way before, but it's not common.
Post reply on HN