Fast Inverse Square Root - A Quake III Algorithm

28 Th11, 2020
968 556 lượt xem

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.

  • this is fucking genius.

    Daniel KoláčekDaniel Koláček13 giờ trước
  • This is some whacky shit. A 3month onld channel, with only 1 cool-ass video with 1mn views!!! Think this will become huge

    John TrolleJohn Trolle16 giờ trước
  • ein video... 20 Min.. 60k likes fast ne millionen Aufrufe.. well done :D

    ExxY StarExxY Star20 giờ trước
  • Well done, sir. I love these sorts of deep dives into minutia.

    Michael GourlayMichael GourlayNgày trước
  • LLI H 4 T T H 3 Ф U C K ...

    TacoWilcoTacoWilcoNgày trước
  • Watching this again after obtaining a level of cs knowledge is so weird

    Kimg KomgKimg KomgNgày trước
  • who is sqrt? what's going on here?

    Emmet RayEmmet RayNgày trước
    • Lol

      Andrew SkAndrew Sk23 giờ trước
  • huh.. well Ill be damned

    midakassimidakassiNgày trước
  • I just used the bit manipulation hack in a binary radix sort for floating point numbers when I encountered the same problem. I needed the floats to be put in one of two buckets depending on their bit at a certain index and had to change the numbers into unsigned ints so that I would receive the proper bit. The program ran pretty fast too, it was able to sort 100 million floats in about 30 seconds. Great video!

    ShaneShaneNgày trước
  • my sister's aesthetic: *listening to french songs while drawing* my aesthetic:

    Jhonnatan Walyston Flôr de CarvalhoJhonnatan Walyston Flôr de Carvalho2 ngày trước
  • 20k subscribers from 1 video.. you should post more bro

    Stefan DragosStefan Dragos2 ngày trước
  • At 17:21, is the address conversion from i back to y really necessary? Aren't both variable names referring to the same memory address, and reading y again would give you the correct value?

    David KayeDavid Kaye3 ngày trước
    • No, neither y nor i are pointers.

      NemeanNemean2 ngày trước
  • YT algos brought me here for some reason and I don't understand shit. I am, however, deeply impressed by all of you who does.

    Jakob FredrikssonJakob Fredriksson3 ngày trước
  • Two to two four

    Dmitry KimDmitry Kim4 ngày trước
  • Please make more videos

    Ja Pimeys LaskeutuiJa Pimeys Laskeutui4 ngày trước
  • At around 6:07 it should say 0.0101 = 1.01×2^(-2) Great video though! Thanks a lot!

    Peter-Klaus NikolausPeter-Klaus Nikolaus4 ngày trước
  • what the fuck indeed.

    Liquid | v2Liquid | v25 ngày trước
  • this is now my 3rd time watching this if I’m not mistaken, I think I’m finally starting to understand

    Gustas AudickasGustas Audickas5 ngày trước
  • 1:38 top ten rapper m and m is to afraid to dis

    bob bobbob bob5 ngày trước
  • boring as fuck, sucks.

    Big Vosh'Big Vosh'6 ngày trước
  • I went in for fast inverse sqrt algorithm came out finally understanding the IEE754 .

    tpaladintpaladin6 ngày trước
  • This is pure B E A U T Y

    Mastakilla91Mastakilla917 ngày trước
  • Started watching this video expecting to not understand anything but ended up getting most of it. Great job, really well explained.

    Art KArt K7 ngày trước
  • The algorithm is useless. _mm_rsqrt_ps is way faster (a single instruction), and way more precise (relative error below 0.04%).

    Konstantin XKonstantin X9 ngày trước
  • so if this algorithm exists and is superior when compared in terms of speed with 1% error, why can't the current algorithm in the math.h library be replaced with this algorithm...? Or better yet, included as a new function in the math.h library called fastsqrt like the fast Fourier transform...

    Vivian D'SouzaVivian D'Souza9 ngày trước
    • @Nemean Appreciate the clarification.

      Vivian D'SouzaVivian D'Souza8 ngày trước
    • I should have said that I made this video from the perspective of when Quake III came out. Nowadays 1/sqrt(x) is actually faster. But in general the math.h library always guarantees exactness first (in the sense that it gives the most accurate answer possible), so even if you find a good approximation, the standard will not implement it.

      NemeanNemean8 ngày trước
  • 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.

    MoggetslittlesisterMoggetslittlesister10 ngày trước
  • Wait... what?

    Nine's Own GoalNine's Own Goal11 ngày trước
  • Cool stuff, I like it. Can you continue this work on describing different complicated things in code for us?

    Sergey VoronezhskiySergey Voronezhskiy13 ngày trước
    • Kinda, I want to do algorithms in general

      NemeanNemean12 ngày trước
  • Really Really well-made animations. Easy to understand.

    John YueJohn Yue13 ngày trước
  • Bold of you to assume I understood anything

    G LUONGG LUONG13 ngày trước
  • Bro, make more videos.

    Abobker ElaghelAbobker Elaghel13 ngày trước
  • 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...

    Andreas BeschornerAndreas Beschorner13 ngày trước
  • 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)

    1Maklak1Maklak13 ngày trước
  • but how much faster is it?

    MglistyMglisty13 ngày trước
  • 6:41 "Something definitely has gone wrong" i: *Let me introduce myself*

    謎の海月謎の海月14 ngày trước
  • Cool video! What did you use to make it? ^^

    Wassim BouazizWassim Bouaziz14 ngày trước
    • Adobe After Effects, Adobe Illustrator and LaTeXiT

      NemeanNemean14 ngày trước
  • Just wow , Thanks 😊 ✌️

    trashedlife1trashedlife114 ngày trước
  • COOL

    Tanim SkTanim Sk14 ngày trước
  • 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 (

    Santtu KähkönenSanttu Kähkönen15 ngày trước
  • Brilliant. Thanks for sharing!

    Antonio AstorinoAntonio Astorino15 ngày trước
  • And here I am thinking the exact comment in the video: WHAT THE *****?! Whoever came up with this thing was not human.

    Not TodayNot Today15 ngày trước
  • Awesome video!

    Alex Enrique CrispimAlex Enrique Crispim15 ngày trước
  • from where or how did you source the equation for representing binary32 bits (float) in decimal values before they did the log magic?

    Goliath StarkGoliath Stark16 ngày trước
  • Yes

    Anurag PandeyAnurag Pandey16 ngày trước
  • The thumbnail got me to click. It's my first time seeing a very random-looking hexadecimal be used in programming lol

    Carl Eric DoromalCarl Eric Doromal17 ngày trước
  • 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!

    LuckLuck17 ngày trước
  • When limits, differentiation and C you learnt fall into one piece. Total denouement. That guy is genius.

    SohanSohan18 ngày trước
  • 👍👍👍 *_FANTASTIC_*

    Gabriel DibbleGabriel Dibble18 ngày trước
  • Bro the world needs more of your videos

    Alok TiwariAlok Tiwari18 ngày trước
  • 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)

    MatthewMatthew18 ngày trước
    • 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.

      NemeanNemean18 ngày trước
  • Quake teaching me that I’m just a fucking casual even before it was compiled.

    UnheartedUnhearted19 ngày trước
  • 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.

    Sachin KiragiSachin Kiragi19 ngày trước
  • Fascinating... and over my head, lol. Really cool. 😎

    80s gamr80s gamr19 ngày trước
  • This is even faster: float fast_inverse_square_root(float x) { return x*x; }

    lethalsublethalsub19 ngày trước
  • "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".

    deadmaydaydeadmayday19 ngày trước
  • 06:08 and 08:24 "0.0101 = 1.01 * 2^(-2)" instead of "2^(-3)"?

    Paulo Eduardo MorbeckPaulo Eduardo Morbeck19 ngày trước
  • Great video! Are you using 3b1b's animation library?

    Ofek ShilonOfek Shilon20 ngày trước
    • No, I use Adobe After Effects

      NemeanNemean19 ngày trước
  • 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.

    John DoeJohn Doe20 ngày trước
  • ¡Fast inverse square root! sounds like an anime technique

    Andrés PrietoAndrés Prieto21 ngày trước
  • Alright that's it, sub and notification bell are locked in, I'm waiting for another

    JoeleoJoeleo21 ngày trước
  • Jesus, I don't get the WTF Part.

    Neil ChouNeil Chou21 ngày trước
  • You didn't explain what happens to the bit of the exponent that gets shifted into the mantissa at the "evil bit hack" step.

    Laurent LÊ-HEBRARDLaurent LÊ-HEBRARD22 ngày trước
  • 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.

    David TribbleDavid Tribble22 ngày trước
  • 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?

    Quinn CulverQuinn Culver22 ngày trước
    • 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

      NemeanNemean21 ngày trước
  • "I don't know what else to say, that's just how C works" An excellent explanation of all of C

    ThePuzzlemaker2ThePuzzlemaker223 ngày trước
  • i don't get that 1 in front of + at 10:24

    Neil ChouNeil Chou23 ngày trước
  • 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

    D o D oD o D o23 ngày trước
  • *Doom Eternal running at 500 fps go brrrrrrrr*

    KumaKuma24 ngày trước
  • I would like to see this outpot in pure hexadecimal format with 64bits...

    Satoshi NakamotoSatoshi Nakamoto24 ngày trước
  • sh**, take my subs and Thumbs-up

    juan sonjuan son24 ngày trước
  • I love C. Great video. Very clear.

    Noah SpurrierNoah Spurrier25 ngày trước
  • 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"*

    Kevin TanKevin Tan25 ngày trước
  • Very interesting solution to inverse root approximation. Good video.

    Alan MedinaAlan Medina25 ngày trước
  • Nice video and explanation. I didn't get it but me no smart

    Manu Barrio LinaresManu Barrio Linares25 ngày trước
  • 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...

    AdacadabraAdacadabra25 ngày trước
    • When you used packaged math fnctions from popular game engines, they are not optimized like this. they give you accurate data instead of fast data. This is why people who don't know low level programming turn out slow games because they don't even realize why it's slow.

      Khaos CeroKhaos Cero8 ngày trước
  • 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).

    Santosh P.S.S.Santosh P.S.S.25 ngày trước
  • Thank you for this video. Really well explained.

    Say ASay A26 ngày trước
  • You only have one video? The YT community needs someone to break down more cool algorithms like this

    Shaun RoseShaun Rose26 ngày trước
  • what

    retardretard26 ngày trước
  • truely remarkable, but we compute sqrt with javascript now

    Tony NgTony Ng26 ngày trước
  • 👍

    Bart GillisBart Gillis26 ngày trước
  • 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?

    AlexanderAlexander27 ngày trước
  • ahh, love me some good maths breakdowns of code

    Dallin BackstromDallin Backstrom27 ngày trước
  • 6:09 wouldn't it be 1.01e-2 ????

    ElNico56ElNico5627 ngày trước
  • 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

    Wayfarer ZenWayfarer Zen27 ngày trước
  • Plz make more

    Aleverette SAleverette S27 ngày trước
  • Oh man. Very useful 👌video

    RavikumarRavikumar27 ngày trước
  • quake devs be like: - i need a constant for three halfs - lets just write 0x5f3759df because i don't need a variable

    iamthewallrusiamthewallrus28 ngày trước
  • 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 ToseComa Tose28 ngày trước
    • In fact Quake was made on an Amiga.

      Coma ToseComa Tose27 ngày trước
  • 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.

    Steven WolfeSteven Wolfe28 ngày trước
  • actually it is very easy for me, because i am a programmer

    Pancake RilaPancake Rila29 ngày trước
  • ..... Oh ! We call it " JUGAAD ". This is great and inspiring ! Thanks a lot for sharing this !

    Shylesh SrinivasanShylesh Srinivasan29 ngày trước
  • 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;-)

    Stephen DavisStephen Davis29 ngày trước
  • Wow this algorithm is genius

    Donald DuckDonald Duck29 ngày trước
  • i agree: what the fuck

    tomatotomato29 ngày trước
  • The adamant oil subsequently sail because iran congruently injure including a fine chicken. slippery, narrow butter

    Алесандр ИвановАлесандр Иванов29 ngày trước
  • Are there videos outlined like this that explain python code? I find it very entertaining and great source of knowledge

    Hot potatoHot potato29 ngày trước
  • wtf is wrong with youtube please i don't care

    NirreNirre29 ngày trước
  • We need more videos like this!

    Wolf FusagWolf FusagTháng trước
  • what the fuck?

    Mike HawkMike HawkTháng trước