Fast Inverse Square Root — A Quake III Algorithm
Channel:Nemean · Length:20:08 · Published:2020-11-28 · Views:6031570
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
- How to achieve nanometer precision in space? · Breaking Taps · 11:06
- TWO Unpickable (?) Locks for Lock Picking Lawyer! · Stuff Made Here · 14:39
- This is why we can't have nice things · Veritasium · 17:30
- The Future of Mathematics? · Microsoft Research · 1:14:48
- [1299] Unpickable Locks From Stuff Made Here · LockPickingLawyer · 10:35
- Why can't you multiply vectors? · Freya Holmér · 51:15
- Fourier Optics used for Optical Pattern Recognition · Huygens Optics · 18:30
- Refterm Lecture Part 1 - Philosophies of Optimization · Molly Rocket · 18:41
- The Simple Essence of Automatic Differentiation - Conal Elliott · Microsoft Research · 1:30:45
- Building my dream computer - Part 1 · The 8-Bit Guy · 20:37
- D/A and A/D | Digital Show and Tell (Monty Montgomery @ xiph.org) · FL Studio · 23:52
- Hold music used to sound better. Here's why. · Tom Scott · 3:36
- 8 Bit & '8 Bitish' Graphics-Outside the Box · GDC Festival of Gaming · 1:25:34
- How Python was Shaped by leaky Internals, Armin Ronacher, Flask framework · Видео с мероприятий {speach! · 49:55
- CppCon 2015: Andrei Alexandrescu “std::allocator...” · CppCon · 1:12:27
- Reverse emulating the NES to give it SUPER POWERS! · suckerpinch · 22:21