Understanding the math behind 0x5f3759df and the fast inverse square root (2012) | Hacker News Reader

Understanding the math behind 0x5f3759df and the fast inverse square root (2012)

h14s.p5r.org

222 pointsColinWright19 comments

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.

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.

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

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

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!)

Then don't tell him I've also read all his floating point papers as well back in the day :)

Surely this is the reciprocal of the square root, not the inverse?

Multiplicative inverse.

Isn't that the same?

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

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.

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

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.

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.

These days we have SSE (especially on x64) and its inverse square root (intrinsic: _mm_rsqrt_ss/ps) is faster and more precise.

Dupe of: https://news.ycombinator.com/item?id=15024539

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

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.

OK, we've added back “Understanding the math behind”.

Reply on news.ycombinator.com