Prime React: Fast Inverse Square Root — A Quake III Algorithm

On the topic of long and long long, if you want to see the best error message ever, try to declare a variable as a long long long, and compile with GCC. “Long long long is too long for GCC”

I’ve had to write code that stores 10-12 constants into specific registers to get a RAM memory unit to work. Why those numbers? No one knows. Truly, no one. I asked an Application Engineer of the company building the chip, no clue. He contacted the “expert” on that reference. No idea either. I got the numbers from a random yt video of *another different chip*. Not even the guys who designed the chip know, because that module is a bought IP. I had to explain all of this in comments and face a code review

The "tragedy" of int not having a defined size was both a feature and a bug. It was originally meant to allow easier porting between machines with different word-sizes. It was intentional. In hindsight... yes it was indeed a mistake that we've been correcting for decades.

This is a nice algorithm but remember: the simple 1 / sqrt(x) is faster on todays CPUs

I love your enthusiasm and appreciation for these subjects

Btw, numbers with fixed fractional part do exist and are super common on DSPs, where you want decimal numbers but you can’t really take the performance hit of float numbers.

If I'm not mistaken, it was John Carmack that added that fast inverse square root in Quake 3, but what's important this time is that he didn't invented it. I mean, it's important because some people attributed that to him, and while he's a genious, it wasn't in this case. Still, way above the average coder for knowing or finding about this.

IIRC HolyC does what you described with the data types; instead of short, long etc it's just i16, i64, etc.

I tried this in our game engine and profiled it. It wasn’t that much faster anymore. CPUs have evolved since this was released and I’m pretty sure the math lib uses those improvements. One thing that I did notice though, was characters suddenly dropping through floors because of the imprecision of the algorithm. So what was fast was me reverting using this code.

About that log ... the log function is the inverse function of the exponential function which means that we can simplify 2^e-127 to only e-127 if we use log(2). This is the reason of using log in base 2 and because it is all part of an equation we also get a log to the other part of it which they cleverly replace with an estimation. And about the change of position of E that was one of the possible ways to remove the division from M while also having them grouped together. Unfortunately the video creator in his decision not to go deep on the math makes it sound way more complex than it is.

I think we can cut the C designers some slack on the "int" not having a fixed sized. Computer Word sizes were in constant fluctuation so having a type that was equal to the word size of the machine it was on made since for a compatibility perspective. The real tragedy was that when word sizes went from 32 to 64 bit. They decided to break the pattern and not make int equal 64 bits and keep it at 32 bits because the jump in memory was so big it would make your programs use way too much memory if you suddenly made every int 64 bits long. If they could have imaged the downstream effect of double the memory usage of a program every time you increased the Word size, maybe they would have not gone with the design. But then again, C was so popular because of how portable it was. If int wasn't the same size as a Word, then maybe C wouldn't have had the staying power it has.

thanks for bringing this video back to me again. I forgot how many times I've watched this, but the more I watch this, the more I enjoy this. It reminds me how much I'm looking forward to enrolling in a computer science course

I was lurking while working during this stream. Thank you for putting it up here so I could actually give it the attention it deserves!

Nobody at id came up with this. The IEEE 754 sqrt trick was invented by mathematicians William Kahan (Berkeley, very famous numerical analyst) and J.C. Ng (Sun Microsystems). But to be clear, the portion actually used in the Quake III source code is completely and utterly pedestrian bit-fiddling. Nothing about it is at all remarkable or novel, these are incredibly well-trodden ideas, even for an undergrad course in numerical analysis, let alone research-level work. Greg Walsh heard about it from mathematician Cleve Moler, who got it from Kahan and Ng. This is what mathematicians are helpful for: for Cleve Moler this is an absolutely trivial, pedestrian application of theory and techniques that go far above and beyond this. So yeah, this is not an example of some game programmer thinking really hard about how to calculate something, this is about community-spanning interactions between mathematicians, who think really hard and come up with brilliant ideas with broad usefulness, and practical programmers who are willing to listen to and work with mathematicians to learn those things. The lesson in this story is: pay attention to mathematicians. Hire them yourselves if you have the money. Work with and communicate with them.

Lol as an Electrical Engineer, I'm so proud of the IEEE standards like 754. I really love the work that was done before my time..

The word mantissa triggers me. I did not have a fun time calculating floating point numbers by hand.

In Javascript, the "evil floating point bit hack" would be the equivalent of manipulating an ArrayBuffer via a Float32Array then looking up the values of that ArrayBuffer with a Float64Array. The data is the same but it doesn't represent the same thing.

I still think one of the most elegant inventions in computer science is two's complement. It's just badass.

I love this video, watched it like 2-3 times before and then through prime. I learnt this stuff in my alevels and degree, and it still amazes me how people came up with it. From IEEE 754 to the algorithm as a whole, makes me want to be a better engineer

I’ve never used JS TS or any of the typically web-oriented technologies. Thankfully right out of college I got into embedded and real time dev. I enjoy the embedded / rt world a lot.