I wondered about the name of that function: surely it isn't inverse square root? That would be "squared". It's "1 over square root" or something. So down the rabbit hole to see if it was always called that. Yup, in Wikipedia articles at least, but the first paper seems to be by Jim Blinn in 1997, without the term in the title. So let's read the paper... Frustratingly, although I am an IEEE member, and I did subscribe to Computer Graphics and Applications in 1997, it won't let me read the paper without paying again. So curious to hear from folks knowledgeable in the space if this was a mis-naming that stuck or I'm confused about the meaning of "inverse". In my universe we used inverse in the context of functions and their inverses, and "invert" in the context of binary values (1s compliment of x is also called x inverted). Never to describe reciprocal.
This seems to have been common usage. I never really thought about it as it was just so normal to refer to reciprocal as "inverse" in this context.
> In my universe we used inverse in the context of functions and their inverses
Yes but, the other type of inverse that is so fundamental to CS in general, and especially geometry is a matrix inverse, which is again a multiplicative inverse, so it's not too surprising how this usage became assumed in many contexts.
I’ve heard inverse used to mean reciprocal often enough. And it’s technically accurate - a reciprocal is a multiplicative inverse. The problem is mainly that “inverse” is ambiguous, especially in this particular case (an inverse square root is a square!), whereas “reciprocal” is clear and unambiguous. Online you can find lots of uses of inverse, and questions about inverse vs reciprocal. So yes reciprocal is the better, more clear term to use here, but “inverse” to mean reciprocal does happen.
Not really, that’s a very clever trick used on floating point numbers, and does the approximate reciprocal square root.
This right-shift thing is far simpler, not very clever, doesn’t involve magic numbers, and is much more well known than the “Quake trick”. There are easy ways to see it. One would be that multiplying a number by itself approximately doubles the number of digits. Therefore halving the number of digits is approximately the square root. You can get more technical and precise by noting that FFS(n) =~ log2(n), and if you remember logs, you know that exp(log(n)/2) = n^(1/2), so shifting right by FFS(n)/2 is just mathematically approximately a square root.
They are more closely related than you suggest. Both methods are using an approximation of log2 to get an initial guess. One gets it from "FPS(n)", the other gets it from the floating point representation of n, where you can roughly find the log2(n) by looking at the exponent of n in the float representation. You can also use the mantissa to refine the guess further.
They are related a little, around the log2 (exponent), I totally agree. I guess I figured the magic number subtraction that turns it into n^(-1/2) is so wild that it puts the Quake trick in a bit of a different class. This right shift thing is a lot older and there’s probably a lineage of ideas from the right shift on integers to the Quake trick. I discovered another fun one on my own that is probably already well known in bit-math circles, but simply inverting the bits of a floating point exponent is a very rough approximation to the reciprocal, good for a Newton initial guess.
