REVEALED: Quake III's SECRET Algorithm!

When the Quake III Arena source code was released to the world it contained a previously unknown algorithm called the Fast Inverse Square Root. This is the story of this strange algorithm and how it works as told by retired Microsoft software engineer Dave Plummer.
Thanks to viewer Brandon Pinske for the video topic suggestion!

For more info on the FISR:

Amazon Affiliate links for products mentioned in the video:

Chapter Markers:
00:00 The Story
02:10 Welcome
03:25 Vectors
04:30 Normalization
05:48 Pythagoras Redux
07:50 Behold Code
09:10 Roots and Floats
10:21 Newton, Approximately
11:14 Rate of Change
13:02 C++ Code
14:15 Gates and Allen
15:04 Outtakes and Rarities

Errata: Please let me know in the comments of any important errors or omissions, and I will update things here. Currently, the only major update is at the end - I leave you with the impression that IEEE-754 might have been based on MBF, but I don't think that's the case. I will expand on this in Part 2, but recommend these two links for the curious:

• "The IEEE Standard 754: One for the History Books,"
• "An Interview with the Old Man of Floating-Point,"

[nathanmielke]

"If there's anything that Bill Gates taught me, it was never to name drop"... I laughed harder than I should've at that

[michaelafcadio]

"Abuses the compiler in ways I've never seen before." Classic!

[WarriorRazor]

Greatest arena shooter of all time, I miss Quake 3 so much, occasionally I'll launch it and browse the countless empty servers that were once full and shed a tear.

[geoffreyanderson]

I am good at math, and when I first saw that algorithm, I was completely floored. Cracking good stuff Dave!

[WimukthiBandara]

I did some digging and found that Cleve Moler (MATLAB) had a hand in deriving the constant used in the algorithm. It's funny that no one knows how exactly it was derived in the first place.

[The_O]

I have always wondered why QIII was THAT smooth back in a day when such smoothness for such quality seemed impossible still ... and now I know. Thanks, Dave :)

[sryx]

I have a small collection of Abrash's books and I even managed to get his Graphics Programming Black Book signed by Carmack. I had gone to Oculus Connect with the hope of getting Michael's autograph but he was never available. He is such a brilliant person, to be able to just walk down the hall and pick his brain must have been an amazing perk of working at Microsoft.

[jelleverest]

That fast inverse square root is a gem of an algorithm!

Also, happy birthday!

[adamsfusion]

Michael Abrash is one of my heroes. Ever since I was a teenager reading his Zen books, I've looked up to him as some sort of wizard. It's been decades since then and his work still amazes me every time I stumble across it.

[nblamer]

Spoiler: it's maths.. if you raise some number to negative exponent, it's same as 1/n^m... second part of the spoiler: dividing m (the exponent) by two is same as taking a square root... think about it, 2^8 for example is 256.. square root of 256 is 16.. which is 2^4, which is (2^(8/2)) and so forth.. floats are encoded as sign * mantissa * 2^exponent, where exponent is between -126 and +127 (some values are reserved for special use like Not-a-Number, Infinity and so on..). The (i >> 1) in the code shifts exponent bits right once, which is same as dividing by two.. which is same as square root, and the subtraction does negation so is doing the reciprocal. The WTF part is the magic constant which less people would stumble on their own (yours truly included).

[BGBTech]

For what it is worth: I made a hobby CPU on an FPGA (custom ISA, I call it BJX2, essentially a VLIW with variable-length bundles). Its FPU only does FADD/FSUB/FMUL in hardware, so I use algorithms fairly similar to the FISR in the video for doing things like floating point divide and square-root in general (just typically with a few more Newton-Raphson stages for sake of accuracy). Basically works, was cheaper than doing it in hardware, and was speed competitive with my original attempt at a hardware FDIV/FSQRT module.
(The HW also does format conversions; FP-compare ops are handled via the integer ALU).

[mikemcgrumpy]

I’m a programmer, and I understood maybe 5% of everything Dave said. Yet I was still mesmerised by it all.

[dpapa]

Dave is like, I'm not very good at Math, then goes into a detailed breakdown of newtonian logs....Kinda lost me at this point. But watched to the end, as it is really interesting anyway. I've never considered this approach to problem solving before...I can see its value. One area where such an approach might be useful is laying out DAGs. Btw - if anyone has a decent algorithm for that based on rectangles representing nodes, let me know.

[arthurarg]

This algorithm is impressively optimal and great for learning about cs, floats and binary. If you want a bit of a deeper dive into the math behind it I recommend the video "fast inverse square root" by Nemean. Looking forward to the next video about it!

[AdobadoFantastico]

This is awesome. I'm aware of the FISR and had always wondered whether anyone got some kind of answers as to its origin. Looking forward to the later episodes. This is my first time on this channel but I'll be sure to come back.
Also Happy Birthday! 🎊🥳🍰

[momchilandonov]

Red Faction was also insane in terms of optimization. I recall playing it around 20 years ago on 300 Mhz CPU (most likely 233 Mhz real speed), 128 SDRAM and 16 MB of video memory or overall a very similar system and was amazed at how smooth it ran!

[Codeaholic]

I've gone over this code a few times, first from an old usenet post. Dave's explanation is one of the better ones I've seen, aside from the hand wavy don't worry about calculus.

[rj_chap]

I've worked in InfoSec, specifically Incident Response, for nearly 10 years. Our team and teams like ours respond to clients when threat actors have broken into their network and caused problems (which is an understatement). A common example are ransomware cases. Throughout my entire IT tenure, I've commented on how I've never needed much math. I went up through Calc 2, maybe higher, I don't even remember. I read/write C/C++ and various scripting languages often. And yet I never really need anything more than modulus. Every once in a while, I remember that game programming is a different animal. This video has *proven* that to me! I'm going to share this with all my cohorts. We all think we're special... let's see how many of us can actually following along with this video :).

[brunomazzei]

Happy birthday, Dave! And thank you a lot for this excellent video!!

[wadz]

90% of all this goes over my head, yet I'm 100% intrigued by these videos.