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

21–30 of 60 posts

Re: Improving the fast inverse square root (2010)

#21

Post by dnautics »

llukas wrote: post #20
dnautics wrote: post #10

Earlier quoted context omitted.

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.

Not really - https://en.wikipedia.org/wiki/Numerical_stability If your algorithm is not stable then even 64-bit won't help you. Compare Euler vs Verlet - https://en.wikipedia.org/wiki/Verlet_integration

You're making a different argument.

Re: Improving the fast inverse square root (2010)

#22

Post by vardump »

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

> That's great and all, but nobody needs a 32-bit anything in 2018.

Then why x86-64 integer instructions default to 32-bit register size when REX prefix byte is not present?

You can double x86 FP throughput using 32-bit floats versus 64 bit ones.

For GPUs, the performance 32-bit float performance advantage can be more than 4-10x (sometimes a lot more).

Re: Improving the fast inverse square root (2010)

#23

Post by dnautics »

stochastic_monk wrote: post #14
dagenix wrote: post #8

Earlier quoted context omitted.

That's not really accurate. Even in cases were 32 bit and 64 bit operations are equally fast on the CPU, 32 bit values still take up half the memory. For many workloads, the limiting factor is cache space. So, if you can use 32 but values, you can get much better performance for those workloads.

And if you’re doing heavy floating point work, you can fit twice as many operations in with a 32-bit float vector as an equally sized double vector, and The vectorized operations happen roughly as fast for both forms, yielding an approximate doubling of speed.

for rank-2 tensor work you can do 4x as many operations, for rank-3 tensor work, it's 8x, assuming memory bandwidth is the bottleneck.

Re: Improving the fast inverse square root (2010)

#24

Post by vardump »

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.

Indeed.

Both reciprocal (inverse) square root SSE SIMD instructions were available in Intel Pentium III, released in 1999.

Re: Improving the fast inverse square root (2010)

#25

Post by stochastic_monk »

dnautics wrote: post #23
stochastic_monk wrote: post #14

Earlier quoted context omitted.

And if you’re doing heavy floating point work, you can fit twice as many operations in with a 32-bit float vector as an equally sized double vector, and The vectorized operations happen roughly as fast for both forms, yielding an approximate doubling of speed.

for rank-2 tensor work you can do 4x as many operations, for rank-3 tensor work, it's 8x, assuming memory bandwidth is the bottleneck.

Does that mean it’s 64x as fast for 16-bit floating point vs 64-bit for a rank 3 tensor?

Re: Improving the fast inverse square root (2010)

#27

Post by dnautics »

stochastic_monk wrote: post #25
dnautics wrote: post #23

Earlier quoted context omitted.

for rank-2 tensor work you can do 4x as many operations, for rank-3 tensor work, it's 8x, assuming memory bandwidth is the bottleneck.

Does that mean it’s 64x as fast for 16-bit floating point vs 64-bit for a rank 3 tensor?

assuming 1) memory bandwidth is the bottleneck and 2) you can keep the tensor values in cache or registers.

I think that GPUs are still vector processing engines, so they should scale with 4x... But assuming google architected the TPU correctly, it should be 16x as fast (I think the architecture is actually that of a rank-2 tensor).

Re: Improving the fast inverse square root (2010)

#28

Post by piyush_soni »

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

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

Re: Improving the fast inverse square root (2010)

#29

Post by skrebbel »

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 actually work and look great.

Re: Improving the fast inverse square root (2010)

#30

Post by llukas »

dnautics wrote: post #21
llukas wrote: post #20

Earlier quoted context omitted.

Not really - https://en.wikipedia.org/wiki/Numerical_stability If your algorithm is not stable then even 64-bit won't help you. Compare Euler vs Verlet - https://en.wikipedia.org/wiki/Verlet_integration

You're making a different argument.

Which problem that has stable algorithm would require 64-bit then?
Post reply on HN