5 ms·
Improving the fast inverse square root (2010)
- oranlooney 8y agoThat'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 https://cs.uwaterloo.ca/~m32rober/rsqrt.pdf
- dnautics 8y agoEven 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.
- llukas 8y agoNot really - https://en.wikipedia.org/wiki/Numerical_stability 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 https://en.wikipedia.org/wiki/Verlet_integration
- toolslive 8y agoWhat 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.
- whyever 8y ago> Even scientific calculation would be fine with 32 bit floats It really depends on the algorithms in question and the error tolerances.
- wyldfire 8y agoLots of ML and AI applications are using ever-smaller precisions. Half and even quarter-precision floats are able to maximize efficiency of the various CPU/GPU ALUs.
- cbsmith 8y agoI was going to mention that... Just because we have ridiculous transistor budgets don't mean there aren't problems where you need/want to push the envelope for performance instead of precision. If anything, it grows the applicable problem space.
- Bromskloss 8y ago> nobody needs a 32-bit anything in 2018 Tell us more about this strange "2018" place!
- nightcracker 8y agoNobody needs absolutes in 2018.
- minton 8y agoI think this article is from 2010.
- jacquesm 8y agoThat'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.
- duckerude 8y agoI 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.
- dleslie 8y agoTIL, no one in the gaming industry uses 32 bit floats any longer. /s
- bananaboy 8y agoThis is not true. In games 32-bit floats are extremely common.
- oppositelock 8y agoRealtime 3D still uses floats, but only when we can afford something so big, s10e5 is better where available.
- perfmode 8y agodeep learning uses low precision floats sometimes as few as 8 bits are needed
- jadedhacker 8y agoI think gen 1 or gen 2 of the TPU explicitly supported short ints.
- dagenix 8y agoThat'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.
- stochastic_monk 8y agoAnd 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.
- dnautics 8y agofor 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.
- stochastic_monk 8y agoDoes that mean it’s 64x as fast for 16-bit floating point vs 64-bit for a rank 3 tensor?
- dnautics 8y agoassuming 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).
- egocentric 8y agoThis "nobody needs a 32-bit anything in 2018" seems like a weird opposite of "640K should be enough for anyone". https://www.wired.com/1997/01/did-gates-really-say-640k-is-enough-for-anyone/ https://www.wired.com/1997/01/did-gates-really-say-640k-is-e...
- vardump 8y ago> 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).
- 21 8y agoFunny, in 2018 a lot of people are asking for 16-bit floats. https://en.wikipedia.org/wiki/Half-precision_floating-point_format https://en.wikipedia.org/wiki/Half-precision_floating-point_...
- deleted 8y ago[deleted]
- simonbyrne 8y agoIt is worth noting that with AVX-512, Intel has introduced a native inverse sqrt approximation (VRSQRT14).
- robin_reala 8y agoHow does that perform in comparison?
- brandmeyer 8y agorsqrt{p,s}s has guaranteed relative error <= 1.5 * 2^-12, or about 3.6e-4. According to Agner Fog, it typically executes in one cycle. I would assume that the AVX512 versions are similar.
- mmozeiko 8y agoInverse sqrt approximation is available since SSE1 with rsqrtss & rsqrtps instructions.
- vardump 8y agoIndeed. Both reciprocal (inverse) square root SSE SIMD instructions were available in Intel Pentium III, released in 1999.
- slavik81 8y agoWhich 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.
- 8y ago
- skrebbel 8y agoPretty 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 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.
- Waterluvian 8y agoI heard some Nintendo games does that with sprites or sounds that can take on a random-ish look. Very very cool.
- andybest 8y agoYars' Revenge on the Atari 2600 used the game code as random input to generate the graphics for the 'safe zone'
- GuB-42 8y agoFrom 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.
- narkee 8y agoHow 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...
- meta_AU 8y agoIt 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.
- majewsky 8y agoThe 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.
- StefanKarpinski 8y agoI 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.
- deleted 8y ago[deleted]
- n4r9 8y agoA better phrase would be "reciprocal square root".
- whyever 8y agoIt seems like this does not work for denormal floats.