News for hackers. Stuff that matters.
Re:Understanding the math behind 0x5f3759df and the fast inv... by lemoncucumber on Wednesday August 16, 2017 @12:47PM (#15028987)
Be sure to read the appendix, which is an easy-to-miss link at the end: http://h14s.p5r.org/2012/09/0x5f3759df-appendix.html

The appendix was by far the most interesting part to me, after reading it I felt like I really got the intuition behind how the trick works.

Re:Understanding the math behind 0x5f3759df and the fast inv... by numlocked on Wednesday August 16, 2017 @03:12PM (#15030267)
Wow! Totally agree. The visualization makes it incredibly intuitive. It also makes me appreciate the importance and elegance of the floating point to int trick, which my brain had sort of elided over previously, as the "magic constant" seemed like the crux.
Re:Understanding the math behind 0x5f3759df and the fast inv... by lvoudour on Wednesday August 16, 2017 @02:59PM (#15030143)
I first saw the code in the early 2000's and although I figured out the newton-rapshon part I couldn't wrap my head around the magic number, until I read chris Lomont's famous paper[1]. A little gem which reminds us that not that long ago computing resources were a limited commodity.

Abundance is great and speeds up development time, but unfortunately it leads to laziness and bloat

[1] http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf

Re:Understanding the math behind 0x5f3759df and the fast inv... by Sinergy2 on Thursday August 17, 2017 @12:47PM (#15038406)
>> not that long ago computing resources were a limited commodity.

They are still limited in non-phone embedded contexts these days, leading to the ironic situation that the radar in your car that can override your brakes is running a much weaker CPU than your phone. RAM measured in the low megabytes.

Source: I write code for one of those radars and this constant appears in that code, alongside several other sqrt implementations of varying resolutions (8b, 16b, float). You are expected to use the least-resolution option in your algorithm, based on your analysis/testing. Same goes for trig functions.

I have to keep computer game development textbooks from the nineties and aughts around for reference material.

Re:Understanding the math behind 0x5f3759df and the fast inv... by gilbetron on Wednesday August 16, 2017 @11:05PM (#15033493)
Oh man, lets hope Chris doesn't read this - he doesn't need an even bigger ego!

(he's a personal friend and a great guy!)

Re:Understanding the math behind 0x5f3759df and the fast inv... by lvoudour on Thursday August 17, 2017 @04:55AM (#15034938)
Then don't tell him I've also read all his floating point papers as well back in the day :)
Re:Understanding the math behind 0x5f3759df and the fast inv... by qubex on Wednesday August 16, 2017 @11:16AM (#15028115)
Surely this is the reciprocal of the square root, not the inverse?
Re:Understanding the math behind 0x5f3759df and the fast inv... by sparky_z on Wednesday August 16, 2017 @12:20PM (#15028722)
Multiplicative inverse.
Re:Understanding the math behind 0x5f3759df and the fast inv... by hjalle on Wednesday August 16, 2017 @12:16PM (#15028677)
Isn't that the same?
Re:Understanding the math behind 0x5f3759df and the fast inv... by sparky_z on Wednesday August 16, 2017 @12:33PM (#15028850)
I think what he's getting at is that the "inverse function"[0] of sqrt(x) is just x^2.

[0] https://en.wikipedia.org/wiki/Inverse_function

Re:Understanding the math behind 0x5f3759df and the fast inv... by qubex on Wednesday August 16, 2017 @02:56PM (#15030122)
Correct, that is what I intended. The inverse of any function whose application, subsequent or prior to the function, leads to the identity. The reciprocal, on the other hand, is very clearly understood to be the quotient such that the nominator and denominator are reversed.
Re:Understanding the math behind 0x5f3759df and the fast inv... by ColinWright on Thursday August 17, 2017 @05:36AM (#15035115)
> The reciprocal, on the other hand, is very clearly understood to be the quotient such that the nominator and denominator are reversed.

That depends on the math you use. In this case you are given a floating point argument, so there really isn't a concept of reciprocal either, because it's not a rational number. There are places where "reciprocal" is not specific to the rationals, but there it is usually a more general term meaning pretty much the same as inverse.

In both cases context is everything, and trying to read this - as with all math - in isolation is likely, almost inevitable, to cause confusion.

In this case it's the multiplicative inverse of the square root of the argument.

Re:Understanding the math behind 0x5f3759df and the fast inv... by adenadel on Wednesday August 16, 2017 @12:34PM (#15028859)
If you consider sqrt(x) as a function f(x) = sqrt(x) the inverse could be considered the function inverse f^-1(x) = x^2.
Re:Understanding the math behind 0x5f3759df and the fast inv... by Havoc on Wednesday August 16, 2017 @04:09PM (#15030866)
Don't particularly want to understand it to be honest. It's one of those stories that still has a bit of magic behind it.
Re:Understanding the math behind 0x5f3759df and the fast inv... by davvid on Thursday August 17, 2017 @03:32AM (#15034510)
These days we have SSE (especially on x64) and its inverse square root (intrinsic: _mm_rsqrt_ss/ps) is faster and more precise.
Re:Understanding the math behind 0x5f3759df and the fast inv... by jmiserez on Wednesday August 16, 2017 @12:47PM (#15028985)
Re:Understanding the math behind 0x5f3759df and the fast inv... by ColinWright on Wednesday August 16, 2017 @02:05PM (#15029675)
To the mods ...

I understand why you've changed the title, but I believe that in this case in doing so you have reduced its usefulness. Since you've not even changed it to the title of the actual article, it's clear that you have given this some thought. Having spent that time, I think your decision is wrong, and don't understand the reasoning behind this change.

To other readers, the title I originally gave was:

    Understanding the math behind
    the magic const 0x5f3759df and
    the fast inverse sqrt.
Please note: This isn't a complaint - I'm providing this here so the information the original title I gave isn't lost.

(Although I fully appreciate that this comment will most likely end up off the top page of comments, and hence never be seen. <fx: shrug />

Re:Understanding the math behind 0x5f3759df and the fast inv... by jmiserez on Wednesday August 16, 2017 @02:21PM (#15029840)
I’d have to agree. “Understanding the math behind” is what drew me to the article and it was exactly as promised.

There are many articles about this hack, but many just write about it and it’s history but don’t actually derive the constant. This article demystifies it by showing that it’s just simple math.

Re:Understanding the math behind 0x5f3759df and the fast inv... by sctb on Wednesday August 16, 2017 @02:47PM (#15030041)
OK, we've added back “Understanding the math behind”.