Fast Inverse Square Root - A Quake III Algorithm

  Shikime 951,436


4 muaj më parë

In this video we will take an in depth look at the fast inverse square root and see where the mysterious number 0x5f3759df comes from. This algorithm became famous after id Software open sourced the engine for Quake III. On the way we will also learn about floating point numbers and newton's method.
0:00 Introduction
1:23 Why Care?
3:21 The Code
4:18 IEEE 754
9:38 Bits and Numbers
12:09 1st Step: Evil Bit Hack
14:46 2nd Step: WTF
17:34 3rd Step: Newton
19:46 Summary
Picture of John Cramack is licensed under CC BY 2.0 from author Drew "Prognar" Campbell.

Moggetslittlesister 7 orë më parë
This is great; I have way more experience with math than with coding, so it was very interesting seeing how people use math tricks to get around coding quirks! Like, I personally would never need to care about the speed of dividing something, but small bits of time add up really quickly in code! Super neat.
Nine's Own Goal
Nine's Own Goal Ditë më parë
Wait... what?
Sergey Voronezhskiy
Sergey Voronezhskiy 2 ditë më parë
Cool stuff, I like it. Can you continue this work on describing different complicated things in code for us?
Nemean 2 ditë më parë
Kinda, I want to do algorithms in general
John Yue
John Yue 3 ditë më parë
Really Really well-made animations. Easy to understand.
G LUONG 3 ditë më parë
Bold of you to assume I understood anything
Abobker Elaghel
Abobker Elaghel 3 ditë më parë
Bro, make more videos.
Andreas Beschorner
Andreas Beschorner 3 ditë më parë
And when you experience texture errors or texture blinks it often happens at steep angels which result in non smooth functions (or those with large derivatives), where Newtons methods becomes inaccurate. Or at very flat angels where devision with the derivative leads to problems...
1Maklak 3 ditë më parë
Ugh, it took me way too long to not confuse x and y. y is the output we want, so it's what's used in Newton's method, not x. f(y) = -x + 1/(y^2) diff(f(y)) = -2/(y^3) f(y) / diff(f(y)) = 0.5*(-y + x*y^3) y_new = y - f(y)/diff(f(y) = y - 0.5*(y - x*y^3) = y * (1.5 - y * y * x /2)
Mglisty 3 ditë më parë
but how much faster is it?
謎の海月 3 ditë më parë
6:41 "Something definitely has gone wrong" i: *Let me introduce myself*
Wassim Bouaziz
Wassim Bouaziz 4 ditë më parë
Cool video! What did you use to make it? ^^
Nemean 4 ditë më parë
Adobe After Effects, Adobe Illustrator and LaTeXiT
trashedlife1 4 ditë më parë
Just wow , Thanks 😊 ✌️
Tanim Sk
Tanim Sk 4 ditë më parë
Santtu Kähkönen
Santtu Kähkönen 4 ditë më parë
This algorithm will make a LOT more sense after watching *Zach Star's 'Approximations. The Engineering way'* on youtube: it is the Newton-Raphson Method for approximating square (/any) roots Also for those who have never used bit-manipulation that bit shifting by 1 to right ( >> 1) just means divided by 2, and is what compilers actually automatically replace divided by two during compilation, since it is such a fast operation. And the opposite bit shift of 1 to left (
Antonio Astorino
Antonio Astorino 5 ditë më parë
Brilliant. Thanks for sharing!
Not Today
Not Today 5 ditë më parë
And here I am thinking the exact comment in the video: WHAT THE *****?! Whoever came up with this thing was not human.
Alex Enrique Crispim
Alex Enrique Crispim 5 ditë më parë
Awesome video!
Goliath Stark
Goliath Stark 6 ditë më parë
from where or how did you source the equation for representing binary32 bits (float) in decimal values before they did the log magic?
Anurag Pandey
Anurag Pandey 6 ditë më parë
Carl Eric Doromal
Carl Eric Doromal 7 ditë më parë
The thumbnail got me to click. It's my first time seeing a very random-looking hexadecimal be used in programming lol
Luck 7 ditë më parë
I've seen many attempts to explain this code, but you are the first one who explained where that magic constant came from. Thanks a lot!
Sohan 8 ditë më parë
When limits, differentiation and C you learnt fall into one piece. Total denouement. That guy is genius.
Gabriel Dibble
Gabriel Dibble 8 ditë më parë
Alok Tiwari
Alok Tiwari 8 ditë më parë
Bro the world needs more of your videos
Matthew 8 ditë më parë
This was cool to see and well explained. I would enjoy seeing an explanation of "Division by Invariant Integers using Multiplication" (should be a paper by that name)
Nemean 8 ditë më parë
Thanks for recommending the paper, very appreciated. If I'm not mistaken, these algorithms are standard compiler optimisations, and since I'm likely going to cover compilers at some point in the future, you should see an explanation of that paper by then.
Unhearted 8 ditë më parë
Quake teaching me that I’m just a fucking casual even before it was compiled.
Sachin Kiragi
Sachin Kiragi 9 ditë më parë
newton raphson method..I used this during one of my college project when one of the ATMEL microcontroller was not having sqrt function in it to calculate RMS value of Voltage.
80s gamr
80s gamr 9 ditë më parë
Fascinating... and over my head, lol. Really cool. 😎
lethalsub 9 ditë më parë
This is even faster: float fast_inverse_square_root(float x) { return x*x; }
deadmayday 9 ditë më parë
"Inverse" is the wrong word, i think you mean "reciprocal". Inverse means the inverse function, so inverse square root is.. squaring. Reciprocal of "whatever" is 1/"whatever".
Paulo Eduardo Morbeck
Paulo Eduardo Morbeck 9 ditë më parë
06:08 and 08:24 "0.0101 = 1.01 * 2^(-2)" instead of "2^(-3)"?
Ofek Shilon
Ofek Shilon 9 ditë më parë
Great video! Are you using 3b1b's animation library?
Nemean 9 ditë më parë
No, I use Adobe After Effects
John Doe
John Doe 10 ditë më parë
It's even scarier than "only 1% error"; using the default magic number of 0x5F3759DF actually gives about 0.175% error maximally, dropping thereafter. It is now believed the original author of the function (not Carmack, who never claimed he was), found the constant through trial and error rather than derivation. If you use Chris Lomont's updated magic number of 0x5F375A86 (which he derived), the error drops to a staggering 0.09% after just 1 iteration. BTW, the original author is unknown, but speculated to be Canadian Velvel Kahan, Turing Award winner and mathematician, circa 1985.
Andrés Prieto
Andrés Prieto 11 ditë më parë
¡Fast inverse square root! sounds like an anime technique
Joeleo 11 ditë më parë
Alright that's it, sub and notification bell are locked in, I'm waiting for another
Neil Chou
Neil Chou 11 ditë më parë
Jesus, I don't get the WTF Part.
Laurent LÊ-HEBRARD 11 ditë më parë
You didn't explain what happens to the bit of the exponent that gets shifted into the mantissa at the "evil bit hack" step.
David Tribble
David Tribble 12 ditë më parë
One nitpick: When you say "decimal number" you really mean "binary real number". First, it's a binary number, not a decimal number. Second, it's a real (floating-point) number, not an integer.
Quinn Culver
Quinn Culver 12 ditë më parë
Great vid. At the end, when applying Newton's method, you probably want y's inside f and f', and y_new not x_new. True?
Nemean 11 ditë më parë
Yes. I honestly don't know why the code calls x "y". As in, y doesn't even refer to the y-axis or anything. I tried to hide that ugliness from the viewers, but some of you are just too observant :P
ThePuzzlemaker2 12 ditë më parë
"I don't know what else to say, that's just how C works" An excellent explanation of all of C
Neil Chou
Neil Chou 13 ditë më parë
i don't get that 1 in front of + at 10:24
D o D o
D o D o 13 ditë më parë
If you convert 0x5f3759df in python for example (print(int("0x5f3759df",0)) you get 1597463007 But if you calculate 3/2*2^23*(127-0.043) you get 1597488758.784 The mu should be 0,0450465679169398
Kuma 13 ditë më parë
*Doom Eternal running at 500 fps go brrrrrrrr*
Satoshi Nakamoto
Satoshi Nakamoto 14 ditë më parë
I would like to see this outpot in pure hexadecimal format with 64bits...
juan son
juan son 14 ditë më parë
sh**, take my subs and Thumbs-up
Noah Spurrier
Noah Spurrier 14 ditë më parë
I love C. Great video. Very clear.
Kevin Tan
Kevin Tan 14 ditë më parë
He will come back based on his comment in his community tab: *"I plan on covering algorithms in general. But if there's some obscure piece of code accompanying it, that's just more bonus points for the algorithm. - Nemean"*
Alan Medina
Alan Medina 15 ditë më parë
Very interesting solution to inverse root approximation. Good video.
Manu Barrio Linares
Manu Barrio Linares 15 ditë më parë
Nice video and explanation. I didn't get it but me no smart
Adacadabra 15 ditë më parë
As a millennial programmer, I thank the gods every day that these OGs paved the way with stuff like this. I probably couldn't even recreate pong from scratch...
Santosh P.S.S.
Santosh P.S.S. 15 ditë më parë
Important Fact: Standing Bodies Of Water are *always* level (level means no elevation or deviation from the starting point to the end). This is a scientific fact because this is observable, testable, repeatable, measurable, demonstrable by every single human being alive. This fact alone destroys the mathematical concept and religious idea known as the "heliocentric model". More specifically, this fact alone makes it impossible for us to live on an exterior of a pear-shaped sphere spinning at fantastical speeds going nowhere. Just before you start to attach straw man fallacies on to me, keep in mind these important things: There are three different sciences: Natural Science (which deals with the Objective World) Social Science (deals with societies and the relationship between people in societies) Formal Science (deals with languages such as mathematics which bares no connection to the Objective World) "What is the shape of the earth I stand upon?" this is a Natural Science question. Science does not belong to an institution or a group of people. It belongs to every single human being alive. We live in the present. Not in the past or the future. History can never be considered as a fact of reality in any way shape or form because of obvious reasons. We can't directly experience the past or the future. Just observing something is not a fact that something exists. We need observable, testable, repeatable, measurable, demonstrable practical proofs for something to be considered as a fact. This is also known as the Scientific Method. There is a difference between the corporeal world (the physical world) and the visible world. The reason why we can't conclude something as a fact based on our observations is because we know things get smaller based on how far they're from us when we see them through our eyes. If I see a railroad, the lines look like they're converging, but we know that's impossible because people measured the lines, and the lines are parallel. The lines don't actually meet in real life, it's just how we see things. Our eyes are spherical, we see euclidean (planar) world through spherical eyes. Without physically testing, repeating, measuring, and accessing something in full three dimensions, it's impossible to know exactly what it is that we're trying to quantify. Looking up at the sky does not give you measurable proof of the earth you stand upon. It's like looking up at the light in your room and then measuring the floor based on that light. It's absurd. Images and videos are never considered as scientific proofs because of obvious reasons. Images and videos can be manipulated, they're not tangible. We can't directly experience them. Mathematical equations bare no relation to the Objective World. Mathematics is just a language, like English. Just because something is mathematically correct does not make it real. It's like saying "I'm flying!", even though the sentence is grammatically correct, I'm obviously not flying right now. "Gravity" is a mathematical concept, it's pseudoscience. It does not have any practical proofs. Magical pulling forces don't exist in the Objective Reality. Motion only happens if something presses on something else (pressure variants). Pull is just a term for taking something closer to someone. Things falling down has got nothing to do with the shape of the earth. In the simplest sense things that weigh more than air fall, and things that weigh less than air float. Why do things even fall? No one has any practical proof for why things even have weight. The mathematical theorists are making assumptions about why things are falling, but understand that those are just assumptions, not facts. The sky, the Moon, the Sun, and the Stars are all intangibles. If every single human being can't observe, test, repeat, measure, demonstrate something in a practical fashion, it is considered a belief, or pseudoscience. Does every single human being has access to these lights in the sky? Obviously not. Not to mention stars look like flashing lights when looked through a Nikon COOLPIX P900 (It's still not a proof of anything because we can't move around them in full three dimensions). Admitting to yourself that you truly don't know something is the most honest realization you could have, it is how you progress further. For example, I do not know what the Sun is. The mathematical theorists are making assumptions of what the Sun is, and where it is located. They don't know what the Sun actually is, or where it is located. Unless I could move around the Sun in full three dimensions, the only possible stance I can have is "I don't know". Anything beyond that will be a belief. For example, if I say "The Sun is a cylinder-shaped object moving in the sky", it is just a belief because I can't move around the Sun in full three dimensions to know if it's a cylinder or a circle. The only thing I know is that it's a light in the sky moving in a straight line across the sky (because of how our eyes work it looks like the Sun is moving in an arc across the sky, but the Sun is actually moving across the sky in a straight line). Another example, "I know the full dimensions of earth" is also a belief because I never explored the whole world to know the full dimensions. Remember, something only becomes a fact if it's observable, testable, repeatable, measurable, demonstrable by every single human being alive. In this case, each and every individual should explore the Objective World to its fullest extent, listening to "authorities" is just a belief. The world "map" is also a concept, because every single human being didn't explored the whole world to verify or falsify the map. People are believing in whatever the "governments" say or show. People are literally believing in complete strangers and thinking the official "world map" is true and there is nothing more to explore because they see a blue sphere on their TV. Just because the majority of the population are believing something exists doesn't mean something actually exists in the Objective World. Once again, we need OTRMDPPs for something to be considered a fact of the Objective Reality. Letters before your name does not mean anything. Direct experience is the most important thing. If we can't experience something directly then most of the time it's useless for us. I can only represent myself. Personalities are OUT of the question. If I drop a brick on my head I know what's going to happen. The objective reality does not change based on your subjective opinions or beliefs. It is what it is. Why is this important? Well, the government and its associations are BLATANTLY lying about our existence, the shape of the world, and the dimensions of the world. What's more important than finding out how far the world extends? Full exploration is needed for further understanding of life's most important questions: where we are, why we're here, and what's it all about. Without knowing where we are everything we do is just a concept. For example, if I give you a board, and without giving you any instructions or rules, I want you to play a game, what game are you going to play? The government and its associations are telling you what you're suppose to do, what's expected of you, what you're not suppose to do. Who agreed to their "law" book? I certainly did not. How is it fair that the government and its associations (the police and the military) are imposing their subjective rules onto the human beings? Everyone has different rules about different things, subjective rules are personal, they're NOT objective. These governments, police, military are imposing their SUBJECTIVE rules onto others, this is nothing short of tyranny. Why can't we freely explore the objective world as much as we like? Why is there a physical, and mental restriction by the police, the military, and by psychopaths known as the governments? Remember, no one rules if no one obeys. "People are arguing and fighting over what game to play when they don't even know the board they're playing on" -Del (Beyond the imaginary curve youtube channel: (People are arguing about what to do without knowing the full dimensions of the world) Another analogy: if I erase your memory and put you in a confinement, what is the first thing you're going to look for? Where's the exit. But if I put some actors to distract you by showing you books and telling you there is no exit, then you'll never try to even think about the exit, there will be other brainwashed people just like you who'll brainwash you even more. Then some other actors will tell you what to do, what's expected of you, what you're not suppose to do, and what's the punishment for breaking their god-given "law" book, some other brainwashed people will also have weapons so that common people like you will forcefully follow my law book, which makes my job incredibly easy by making you a slave if that's what I was ever up to. Why should we accept slavery? Why should we accept strangers imposing their subjective versions of what's good and what's bad onto us? If you have OTRMDPPs (Observable, Testable, Repeatable, Measurable, Demonstrable Practical Proofs) that large Standing Bodies Of Water can bend, (sounds absurd to even think about it) please feel free to email me at, but understand that I should be able to demonstrate your claims in a practical fashion, because that's how the Objective World works. No offense, but If your claims does not have any practical proofs, then I'm afraid I have to conclude that you're either blatantly lying or you're really stupid (Or for some reason you want to defend your religious beliefs, because the Earth being a sphere is a religious belief, a mathematical concept, it has no practical proofs, it has no relation to the Objective World, that being real life).
Say A
Say A 16 ditë më parë
Thank you for this video. Really well explained.
Shaun Rose
Shaun Rose 16 ditë më parë
You only have one video? The YT community needs someone to break down more cool algorithms like this
retard 16 ditë më parë
Tony Ng
Tony Ng 16 ditë më parë
truely remarkable, but we compute sqrt with javascript now
Bart Gillis
Bart Gillis 16 ditë më parë
Alexander 16 ditë më parë
why not use lookup-tables with an approximation : x= 3.2 -> int(x) = 3 , lookupTable(3) = 0.577 . Just grow the size of the lookupTables to the error margin you tolerate and there you go. Wikipedia states that this approximation routine is actually faster than a lookup table. I do not understand that. If you can accept an error of 5-10% lookup should definitely be faster. Did they just overengineer the normalization of a vector for the game?
Dallin Backstrom
Dallin Backstrom 17 ditë më parë
ahh, love me some good maths breakdowns of code
ElNico56 17 ditë më parë
6:09 wouldn't it be 1.01e-2 ????
Wayfarer Zen
Wayfarer Zen 17 ditë më parë
Oh gods. At the start of the video, just want to say I know where this is going without even having heard of this algorithm. Bitwise math is a hell of a drug, folks. :D
Aleverette S
Aleverette S 17 ditë më parë
Plz make more
Ravikumar 17 ditë më parë
Oh man. Very useful 👌video
iamthewallrus 17 ditë më parë
quake devs be like: - i need a constant for three halfs - lets just write 0x5f3759df because i don't need a variable
Coma Tose
Coma Tose 18 ditë më parë
This came from a programmer versed in Assembly with vectors. Check out some of the old Amiga mega demos. Long before the first Quake was even made.
Coma Tose
Coma Tose 17 ditë më parë
In fact Quake was made on an Amiga.
Steven Wolfe
Steven Wolfe 18 ditë më parë
Overall, the breakdown of this made a lot of sense. I see a couple of problems with your step 2 explanation though that made it harder for me to understand. 1. Your color switching (at 17:00) reused two of the colors I had been associating with other parts of the equation. You also used the same color for the bit shift and the hex constant when it would have been more appropriate to use two separate colors. (Also, the bit shift color should probably be for the whole 1/2, but this is much more of a nitpick relative to other color problems.) 2. Most of the intuition to this process is explained before step 1 so details are lost in one watch (which, admittedly, is probably fine for most people watching casually). As a final nitpick, I kind of wish you had solved that hex constant to show off how it elegantly captures the correction term. Then you could have pointed out that they were using u = 0.045 instead of u = 0.043, suggesting they were expecting numbers closer to the middle of your graph on 11:10. I digress, thanks for sharing this cool algorithm and explaining it! Even though my understanding was about ~80% by the end, that was more than enough to get me the rest of the way on my own.
Pancake Rila
Pancake Rila 18 ditë më parë
actually it is very easy for me, because i am a programmer
Shylesh Srinivasan
Shylesh Srinivasan 19 ditë më parë
..... Oh ! We call it " JUGAAD ". This is great and inspiring ! Thanks a lot for sharing this !
Stephen Davis
Stephen Davis 19 ditë më parë
I think I might have partway cracked the code: The basic adjustment looks like (1−[([ln]([ln]2))+1]/([ln]2))/2~4.303′566′602′796′71…ē2 with [ln] the natural logarithm and ē a scientific notation marker with negative sign for exponent (Enh, so I'm a little bit of a calculus freak;-)
Donald Duck
Donald Duck 19 ditë më parë
Wow this algorithm is genius
tomato 19 ditë më parë
i agree: what the fuck
Алесандр Иванов
Алесандр Иванов 19 ditë më parë
The adamant oil subsequently sail because iran congruently injure including a fine chicken. slippery, narrow butter
Hot potato
Hot potato 19 ditë më parë
Are there videos outlined like this that explain python code? I find it very entertaining and great source of knowledge
Nirre 19 ditë më parë
wtf is wrong with youtube please i don't care
Wolf Fusag
Wolf Fusag 19 ditë më parë
We need more videos like this!
Mike Hawk
Mike Hawk 19 ditë më parë
what the fuck?
gabrielwong1991 20 ditë më parë
Ah the newton thing is just the taylor series approximation
aman verma
aman verma 20 ditë më parë
Fact that this has a million views is amazing
LanDi3000 20 ditë më parë
This video made me give up game programming.
Bob Bobson
Bob Bobson 21 ditë më parë
would probably just make a large look up table.
Anonymouse 21 ditë më parë
My take away is that the Quake engine programmers were way smarter than I'll ever be.
brawaga 21 ditë më parë
6:09 not 0.0101 but rather 0.00101.
brawaga 21 ditë më parë
3:37 they aren't decimal, they are binary.
rustyelectron 21 ditë më parë
I wonder what he used for creating the math animations, it seems a lot similar to the animations created using 3blue1brown's manim library.
Tom Killwhang
Tom Killwhang 22 ditë më parë
Just Newton's method, it has quadratic convergence and is more or less the best
Pharaoh on LFS
Pharaoh on LFS 22 ditë më parë
5:28 Thought that was kinda funny because it sounds like a play on words, but I think that's literally decimated/decimating lol
Marek Poláček
Marek Poláček 22 ditë më parë
I must say that whoever came up with this algorithm is a genius. I do realise it is in fact a work of team, but someone from the team had an idea and the team worked on that idea that someone had. For an FPS game that needs to do fast calculations, this is pretty nifty thing to do to speed up the calculation process and in 1998 (which is actually the year Quake III Arena was in early development, and when first testing versions came out), this is brilliant. And that is why the game looks so good and runs so smoothly even on lower end machines (including those from that era). John Carmack is a god!
seasong 22 ditë më parë
Tfw your documentation is so bad you need a whole ALnets video to explain the code 😂
Buster Dafydd
Buster Dafydd 22 ditë më parë
0:25 I would right it something like 1 / (x**0.5)
Cryztal 22 ditë më parë
never thought i would actually use my math from school, damn. good vid :)
HRobertSI 22 ditë më parë
I understood the first 50 seconds. :)
Mateus Sarmento
Mateus Sarmento 23 ditë më parë
Great video mate 👍 I love it
h zed
h zed 23 ditë më parë
Very normal calculation if you ever sturdied digital electronics and computer architecture.
Kadaj0666 23 ditë më parë
This was awesome ! Thanks a lot for the explanation ! Those guys are crazy (in a crazy good way !) !
Zareh Gorjian
Zareh Gorjian 23 ditë më parë
wait, isn't long 64 bits?
Nemean 23 ditë më parë
By the C standard it is only required to be at least 32 bits and back when Quake III was released they actually were 32 bits. Only when computers had more memory available, did C compilers give you more bits for a long.
dilinator 24 ditë më parë
Is this guy on MasterClass yet?
Eld Attack Krossa
Eld Attack Krossa 24 ditë më parë
begging for more :(
Nemean 23 ditë më parë
Just kidding, I'm finally working on the next video
Nemean 23 ditë më parë
popogast 24 ditë më parë
This is not _my_ job. But well explained. Thanks.
Norhther 24 ditë më parë
Professor at uni: Comment your code My code:
Aleksandr Ivanov
Aleksandr Ivanov 24 ditë më parë
I enjoyed it a lot. So I did the math in the end. Apparently, the fact that we needed the answer for negative power (i.e. X^(-1/2)) did the whole trick in the end by turning the negative powers of Y into positive, hence avoiding the need for division. Therefore, the answer for X^(1/2) is just 1 division away.
the wicaksono
the wicaksono 19 ditë më parë
jucom 24 ditë më parë
This is such great quality, why is it the only video on your channel. I'm not trying to presure you or anything it's just weird that a first public video is already this great.
The Art of Code - Dylan Beattie
NDC Conferences
Shikime 2,6 mln
Coding Adventure: Chess AI
Sebastian Lague
Shikime 633 mijë
Shikime 2,7 mln
Fara e Flliqt - Episodi 4 Sezona 3
Fara e Flliqt Official
Shikime 109 mijë
A Brief History of Graphics
Shikime 4,3 mln
Don't Talk to the Police
Regent University School of Law
Shikime 12 mln
The Discovery That Transformed Pi
Shikime 2,8 mln
Making an unpickable lock. Calling locksmiths
1. Introduction to Superposition
MIT OpenCourseWare
Shikime 2,2 mln
Shikime 2,7 mln
Fara e Flliqt - Episodi 4 Sezona 3
Fara e Flliqt Official
Shikime 109 mijë
Dafina Zeqiri - DURO
Dafina Zeqiri
Shikime 11 mln
Shikime 3,5 mln
Free Mc's - Instagram (Official Video 4K)
2TON - FTYRA JOTE (prod. by Nego)
Shikime 4,7 mln