Fast Inverse Square Root — A Quake III Algorithm

Channel:Nemean · Length:20:08 · Published:2020-11-28 · Views:6031570

Watch on YouTube

Summary

A walkthrough of the Quake III fast inverse square root, explaining where the constant 0x5f3759df comes from. It covers IEEE 754 floats, the bit hack that approximates a logarithm, and a Newton's method refinement.

Why HN recommends it

HN recommends it as an approachable explanation that makes the famous algorithm finally make sense.

This video is approachable and explains it pretty well — HN, 2021

Software performance & optimization · Algorithms & data structures · Game history & retro gaming

Subtitles (excerpt)

in 2005 game company its software open sourced the engine for their video game quake 3 arena in that source code fans of the game discovered an algorithm that was so ingenious it quickly became famous and the only thing this algorithm does is calculate the inverse of a square root if i had to write a piece of code that would calculate the inverse of a square root this is how i would do it here i'm using the c programming language the same programming language used for quake 3. but to be fair i wouldn't actually write the square root in there myself people work more closely with the c language or we see but design have already figured out how to calculate the square root and the provided algorithm to us in a math.h file that we programmers can then just include in our program so what could possibly be so interesting about the quake 3 algorithm how does its software calculate inverse square roots at first glance it doesn't seem to make any sense where does this number 0x5f3759df come from what does this have to do with taking square roots and why is there a disgusting curse word in the second comment in this video i will show you how with some cool bit manipulation you can take in for square roots and the algorithm that

On Hacker News

Very interesting that this was posted as I literally JUST watched an even MORE interesting youtube upload about this very bit of code just last weekend. Here's the very fun video if anyone wants to take a look: [VIDEO] — greyfox, 2021-07
Apparently the bit pattern of a float interpreted as an int is sorta-kinda it's own logarithm, which is why the famous fast inverse square root from quake 3 works: log(x^-½) = -½log(x) =~ -log(x) >> 1. This video is approachable and explains it pretty well: [VIDEO] — infogulch, 2021-09
> The bits of a float as an integer literal are proportional to its log2 value (plus a constant), … I watched a video[0] a while back about that. Once that coincidence(?) was explained, Q_rsqrt finally made sense. [0]: [VIDEO] (~20 minutes) — colejohnson66, 2021-08
print("Hello World") /s But I've heard good things about the Fast Inverse Square Root Calculation algorithm in the Doom 3 source code. [VIDEO] — bitwidget, 2022-08

Related videos