4 ms·

For an approximate (very rough) answer, as opposed to one accurate to the nearest integer, a right shift by half the number of bits of the leading 1’s position

by dahart 3y ago

For an approximate (very rough) answer, as opposed to one accurate to the nearest integer, a right shift by half the number of bits of the leading 1’s position will do, and of course nearly every processor has a shift instruction. I’m not sure how often processors haven’t had something like FLO (Find Leading One) or FFS (Find First Set) instruction, those seem ubiquitous as well. The super rough approximation for some uses can be approximately as good as an accurate answer. When you just need a decent starting place for some further Newton-Raphson iteration, for example. (Of course the right-shift trick is a nice way to seed a more accurate square root calculation. :P)

lordnacho 3y ago
Is this where the DOOM reference comes in? Somewhat famous Internet story by now featuring Carmack and a magic 32 bit number.
- dahart 3y ago
  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.
  - creato 3y ago
    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.
    - dahart 3y ago
      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.
- epcoa 3y ago
  You mean Quake 3 and fast inverse square root? No. And it wasn’t Carmack. https://www.beyond3d.com/content/articles/15/ https://www.beyond3d.com/content/articles/15/ https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root
  - dboreham 3y ago
    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.
    - dahart 3y ago
      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.
    - epcoa 3y ago
      It was called "inverse square root" as it is just another practical "layer" on top of "inverse" which is just meant to mean multiplicative inverse. This is the original Blinn 97 BTW. https://web.archive.org/web/20130309073539/http://rufus.hackish.org/~rufus/FPtricks.pdf https://web.archive.org/web/20130309073539/http://rufus.hack... 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.
winwang 3y ago
Fun fact, FFS (and its generalization, FNS) is in CUDA: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group__CUDA__MATH__INTRINSIC__INT_1gaf1eb22243e29e0b7222adee8ae7d4e4 https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_... Another nice CUDA hardware intrinsic I like is log2.

by dahart 3y ago

lordnacho 3y ago

Is this where the DOOM reference comes in? Somewhat famous Internet story by now featuring Carmack and a magic 32 bit number.

dahart 3y ago
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.
- creato 3y ago
  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.
  - dahart 3y ago
    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.
epcoa 3y ago
You mean Quake 3 and fast inverse square root? No. And it wasn’t Carmack. https://www.beyond3d.com/content/articles/15/ https://www.beyond3d.com/content/articles/15/ https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root
- dboreham 3y ago
  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.
  - dahart 3y ago
    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.
  - epcoa 3y ago
    It was called "inverse square root" as it is just another practical "layer" on top of "inverse" which is just meant to mean multiplicative inverse. This is the original Blinn 97 BTW. https://web.archive.org/web/20130309073539/http://rufus.hackish.org/~rufus/FPtricks.pdf https://web.archive.org/web/20130309073539/http://rufus.hack... 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.

winwang 3y ago

Fun fact, FFS (and its generalization, FNS) is in CUDA: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group__CUDA__MATH__INTRINSIC__INT_1gaf1eb22243e29e0b7222adee8ae7d4e4 https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_... Another nice CUDA hardware intrinsic I like is log2.