Fast Inverse Square Root - A Quake III Algorithm

[@Eidolon2003]

I love the fact that he felt the need to define a constant for "threehalfs", but just threw that 0x5F3759DF in there no problem LOL

[@otesunki]

well he used it twice... until it got commented out

[@richardbloemenkamp8532]

Well that was maybe when someone had to do refactoring thinking: "This 1.5 is something I can refactor to reduce the number of magic numbers by 50%". That other magic number I cannot refactor because I would have to name it magic_number because I don't know where it comes from. Of course turning 1.5 into a variable named threehalfs also does not improve the readability and introduces a spelling error but fine. The code metrics have improved as was the objective. Maybe I'm wrong.

[@francoiscoupal7057]

@@richardbloemenkamp8532 I think the answer is HOW C compiles code. The compiler adjust what is and what is not a constant value based on the code (and the compiler of course), and most importantly, WHERE to keep that value. In certains cases, constant are stored elsewhere in memory and does exists (or is available) at all times (it must be accessed first). Then you have constants that are stored IN the method itself, sort of like an "inlining" in JIT compilers like Java or C#. I think it is highly probable that the compiler the devs used THEN gave very slightly better results when it compiled the code when written this way, rather than otherwise. Of course, it would be the same algorithm, but the data access speed would be different (storing values in registers, in less CPU cycles), hence the choice to leave it like this. When the goal is speed at any cost, those additional CPU cycle to gather values and store them in registers can add-up quite quickly.

[@DaMonster]

People have said it here in different ways but to say it clearly, a constant is not stored in memory and is just a macro replaced with its value upon compilation.

[@VincentWoo]

@@DaMonster This is not true, since on most platforms you cannot write 1.5F as an immediate operand in assembly, so the compiler has to put 1.5F in memory somewhere. It then loads the constant into a float register at runtime.

[@owfan4134]

10:23 "for no obvious reason at all, let's take the logarithm of that expression" you basically just summed up the Electrical Engineering experience

[@martiensventer9191]

And Statistics. And pretty much any other field where approximating confusing maths becomes neccesary.

[@martiensventer9191]

necessary* damnit I hate English sometimes

[@Andrew-ri5vs]

And information theory

[@TheALPHA1550]

@@martiensventer9191 *Math

[@abebuckingham8198]

A joke among mathematicians is "What sounds does a number theorist make when they drown? Log(log(log(log(log(log(log..."

[@the_hiroman]

Performing a division AND a inverse root using only multiplications is nothing short of real world black magic. I am sincerely impressed.

@@kalpeshpatil8912 If you go to assembly, multiplication is just… multiplication. CPUs have had multiplication opcodes for decades, even for floating point.

[@fr5229]

@@kalpeshpatil8912You seem confused

[@MrRenanwill]

Newton method does this! The zeros of any function are just a bunch of sums and multiplications.

[@lugia8888]

@@MrRenanwill not all functions but yeah some of them

[@fhudufin]

@ sometimes multiplicaation is still written as add and bitshift, when that gets too hard, yes you can use imul

[@diegodonofrio]

I thought it was implemented by John Carmac, but according to Wikipedia: "The algorithm was often misattributed to John Carmack, but in fact the code is based on an unpublished paper by William Kahan and K.C. Ng circulated in May 1986. The original constant was produced from a collaboration between Cleve Moler and Gregory Walsh, while they worked for Ardent Computing in the late 1980s." Thanks for educating and for your great work.

[@RedSntDK]

It's still quite a feat to acquire that knowledge back in the day.

[@patty109109]

@@RedSntDK for the original guys definitely but quake 3 came out when the internet had been in serious use for years so I suspect not too difficult to come upon.

[@andrewhooper7603]

Isn't that what implemented means?

[@ApplePotato]

@@patty109109 I assumed they ripped it out of some existing math library without really understanding what it was doing, hence the "wtf" comment. These tricks are rarely used now days because CPU/GPU has gotten so fast in doing divisions and square roots.

@@patty109109 Please define "serious use"… because to me (and many many people), serious use is what the Internet (the actual Internet, and not timbl's Word Wide Web) was originally made for.

[@thepuzzlemaker2159]

"I don't know what else to say, that's just how C works" An excellent explanation of all of C

[@frydac]

It's one of the easier languages to understand the syntax from though, as there isn't a lot of syntax. And what is done here is a workaround for something the language wasn't designed for, so it might seem somewhat cryptic, and I'm pretty sure it's undefined behavior (meaning not defined in the standard, meaning platform/compiler dependent, as float doesn't need to be in IEEE 754 + the platform might have different alignment requirement for float and unsigned int + unsigned int doesn't need to be 32bit (all not common things though, but exist)). Maybe a clearer way to achieve the same is using a union of unsigned int and float, though you'd have to copy the value (which the compiler might optimize away, but probably not when this was written) In other words you shouldn't be doing something like this, unless you very well know what you are doing, and have testing around it to make sure it does what you expect for every target platform and compiler. To me this is what makes C and other languages like it, powerful and fun :)

[@damaomiX]

This is just how every language works, but in most of them you don't have access to pointers (address of the value), you can just access the value the pointers point to (value in that address).

[@TurboXray]

@@frydac well, it's not really any different than expecting an INT to be 32bits, when C does NOT define INT to specifically be 32bits. But it's almost always a safe assumption (or was).

[@vincei4252]

You should try modern C++. I think the original C K&R was less than 300 pages (if I remember correctly) that describes the entire C language. I just bought a book that tries to clarify just one feature of C++, move semantics, and it is almost 300 pages long. I weep for humanity.

[@ekremdincel1505]

@@vincei4252 C++ move semantics are overengineered in a stupid and useless way.

[@carykh]

Oh man, I remember taking a CS class that taught floating point representation with the exponents and mantissas, and I thought to myself "ok this is cool but I'll be programming higher-level than this, so I probably won't use this knowledge in practice." Well, this is a great example of how you might use it!

[@shaneman1114]

Wtf cary kill hitler holy shit

[@thegavinjackson]

Its cary kicks homes!

[@chickendoodle32]

It's just like fact families in math. You think it's useless right up until you need to do something.

[@XZYSquare]

lol that's actually funny

[@smallcatgirl]

Ok. I'm 5th

[@JackRackam]

I don't think I understood this well enough to explain to my friends how cool it is... but I definitely understood enough to have my mind blown, and to tell them they need to see it

[@grantgoodman8415]

Funny seeing you here!

[@krccmsitp2884]

Same here! ;-)

[@aesir1ases64]

You have just described my thoughts regarding most of the things I like lol, specially in the CS and programming field.

[@milckshakebeans8356]

Who is going to qoute Einstien first

[@flutebasket4294]

I understood it well enough to paint a picture of a dinosaur with my own feces

[@LarsSveen]

I remember when I started programming professionally in the 90's. Id's performance tuning was something that us programmers would nerd out about, and I'd often write my code to similar standards. Curious coworkers would sometimes encounter some of my "performance-tuned code" and be like "uhh, why did you do this like that?" I'd explain all about efficiencies and they'd just kind of roll their eyes and be like "okaaayy." We were, after all, just writing client-server apps for small businesses, for which performance tuning was totally pointless. But I wanted to be a game developer, damnit!

[@yusuf_kizilkaya]

Did you ever actually get into game development?

[@LarsSveen]

@@yusuf_kizilkaya Nope. And now I'm old and burned-out.

[@yusuf_kizilkaya]

@@LarsSveen never too late, and being a game developer now is easier than ever. Maybe you could still give it a shot

[@FurryWrecker911]

That sounds like my life being a graphics artist in the military simulation industry. The bar is set so low, even in 2022, that people we hire on that have been in the industry since the 2000s are either A, are asking why on earth we are wasting time experimenting with dynamic lighting and PBR materials, or B, blown away by how awesome our graphics are (which, considering we have hired GFX artists that think A, we do have a mixed bag of high quality art, and people who think blockouts are good enough). I'm in talks with a programmer friend about making an indie game just to take the edge off.

[@reedlaww]

Lol this is me right now. I’m working on some iterative/list code that I’ve managed to get ~30% faster than the leading industry library. But even over 1M iterations it’s only a difference in milliseconds lol

[@Owen-bk5fc]

You know an algorithm is good when one of the steps includes "C doesn't think we should ever do this, so we have to trick it into letting us"

[@francoiscoupal7057]

It's also one of the best way to explode something in your code (or better yet, corrupt your data in tiny, nearly invisible ways). Some people learned that the hard way.

[@WXKFA]

pointers, references and type casting is the best part of c/c++

[@Evan490BC]

@@WXKFA ... or the worst.

[@geiger21]

@@Evan490BC they are the worst for the same poeple who are afraid of goto

[@Evan490BC]

@@geiger21 You basically have no idea what you're talking about, do you? No one is afraid of horse carts but we have cars in the 21st century.

[@jamesmelton7637]

I'm reminded of the single greatest code comment I've ever read: "I do not understand the following line of code, but I've verified it is required for this function to work correctly." It was in a bit of Perl code, a language with several peculiar syntactic quirks.

[@xyrus345]

Saying Perl has a few peculiar syntactic quirks is like saying a porcupine has a few sharp points.

[@gironic]

Perl : a write-only language.

[@RME76048]

The best coding that I ever did in C and in which I got a big smile and patted myself on the back for the effort, was using an array of pointers to functions where the correct function would execute based on the array index. Man, was I ever impressed with the poetic beauty of such a simple and short series of characters that commanded so much! I ran my code, it worked fine, but it was much slower than using a simple switch/case construct. LOTS slower. So, I went back to what I had before. That was back when I was using a 16-bit MS-DOS C complier, so no doubt all the crazy addressing shenanigans going on behind the scenes really mucked things up. I wonder how well it would run today as a native 64-bit compile, but the working version that I still use is from (with one, semi-recent and tiny data update) twenty years ago and written as a 32-bit Console app. Still, pointers-to-functions are really cool to invoke.

[@redbaron07]

Officially "Practical Extraction and Reporting Language". Unofficially "Pathologically Eclectic Rubbish Lister".

[@gandalf8216]

I once saw a version of Hangman encoded in five characters long Perl script. Won some award in crypto coding I think.

[@neofox2526]

"you don't need to be good at maths to do programming" The Code:

[@Naburgondux]

That's true in web dev xD

[@neofox2526]

@@Naburgondux Yeah luckily loll

[@JeffThePoustman]

​@@Naburgondux I think it's perhaps true everywhere-- and this case illustrates it. You could say that id used a very tiny library, in principle . That's being a good programmer:don't reinvent wheels if you can use wheels made by geniuses. Carmack is a genius who invented many of his own wheela. As such he had no ego limits against learning from other geniuses.

[@Coldsteak]

you need to be good at maths to be godly at programming

[@ajreukgjdi94]

I'd say both programming and math can be branches of logic. Specifically, the formalization of logic as well as the expansion/generalization of logic. They're two pathways to accomplish essentially the same goal. One doesn't necessarily follow from the other. But being good at one implies you're either good at, or it would not take long to become good at the other.

[@rijaja]

Some of my computer science classmates wonder what good learning the IEEE 754 standard and Newton's approximation could possibly do, and the answer is that it helps us to understand a cool video about a quake III algorithm

[@sgtblu3]

I found out about that inverse square root in 2010 (about) and only now, a decade later, has it been explained well. Thank you!

[@fredg8328]

It has been explained many times. Even on youtube, if you search for "0x5f3759df" or "fast inverse square root" you can find many videos, some dating back to 8 years ago... Or you can look at the wikipedia page for more informations.

[@General12th]

@@fredg8328 I think this explanation is better than those explanations.

[@Kyrelel]

This video takes far too long and too many unnecessary steps :/ Oh, and one of them is wrong, see if you can spot it.

[@General12th]

@@Kyrelel I disagree. Every step is necessary. Anything less won't give a sufficently complete understanding of the subject.

[@Jawis32]

@@Kyrelel seems correct to me? Where do you spot a mistake?

[@johnfaustus1]

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.

[@IkethRacing]

it's not Gary T. as mentioned at 10:41?

[@jcsc2001]

@@IkethRacing no it's Gary v. He discovered it when his entire NFT stock portfolio plummeted.

[@franklydoodle350]

@@jcsc2001 Hahahahaha

[@generalbutz8477]

What is this methods name

[@davidrossington9756]

I think we still call it John Carmack's Function since he was the first guy to talk about it

[@jgcodes2020]

If you're wondering why μ ≈ 0.0430: We know that log_2(x+1) ≈ x. If we want to see the relative error between them, we can use the function f(x)=log_2(1+x)-x. We want to find the maximum of this function, and we know that it only has one maximum. Since the function is continuous, we can find its maximum by finding when its derivative equals zero. Using a bunch of rules, we have f'(x)=1/((1+x) ln(2)) - 1. Setting this derivative equal to zero, we see that the maximum of the function occurs at x=(1/ln(2))+1. Substituting this number back into our first function, the maximum value is log_2(1/ln(2)) - (1/ln(2)) + 1 ≈ 0.860. To minimize the error between this maximum and our minimum, we want μ to be halfway between them. Taking the average of (0, 0.0860) yields our constant, 0.0430.

[@reddistone]

Thanks for the nice explanation, but at the second paragraph you have an error: the maximum of the function occurs at *x=(1/ln(2))-1*

[@horleckshelmos8472]

So like, I'm curious: The way we find the average value of the difference function is through finding the integral and dividing by our integrating interval length (1 minus 0 in this case). Wouldn't it be better to subtract by this amount to reduce the error on average? I realize that the 0.430 mu term is used to make sure the absolute value of the error is always less than or equal to 0.430, which means we can say a statement like "our error is always less than x%". But is there a good reason to prefer this over subtracting by the average value? Avg value seems a lot more relevant if you want error to be closest to 0.

[@ObtecularPk]

I ain't reading all that man

[@Daniel-ns71617]

​​@@ObtecularPkshort attention span?

[@jgcodes2020]

​​​@@horleckshelmos8472 The _maximum_ error is actually more important. If most cases give a close enough result, but there are outliers, your graphics will look weird when you run into those outliers. System math libraries typically want to minimize the maximum error when calculating functions; that's where the term "minimax polynomial" comes from.

[@jansenart0]

The breakdown of IEEE 754 is... mind-blowing. That's so supremely clever, both the standard and the explanation.

[@kethernet]

FYI for anyone learning C/C++: the "i = *(long*)x" approach is not standards compliant. It obviously worked for Quake III, but for a modern compiler under high optimization, this could produce bugs. The reason is complicated (search "strict aliasing" if you want to know more), but the correct alternative would be "memcpy(&i, &x, 4)". It's also a good idea to use "uint32_t" instead of "long" to ensure "i" has 4 bytes. Modern systems often have "long"s that are 8 bytes.

[@Debrugger]

Also FYI for learners: there is no reason to write any code like this ever today. A lot has happened since the 90s and modern compilers are smarter than 99% of programmers will ever be.

[@SuperMarkusparkus]

@@Debrugger So how would you go about this today?

[@sddndsiduae4b-688]

@@Debrugger and here you wrong, compilers bound by standard, so it can't do most of tricks used in the code, as each of trick which makes calculation faster also makes it less precise and there is no standard way to say for compiler how much accuracy it needs to preserve. p.s. gcc has option --ffast-math to makes some optimization which do lose precision (compared to standard), but again option itself is not part of c standard, nor it allows to say precise how much precision can be lowered. (i.e. it will never go to such low precision as used in this code, even with such option), and which part of code it should be applied to.

[@Reydriel]

@@SuperMarkusparkus Literally just write 1/sqrt(x) and let the compiler optimise

[@sddndsiduae4b-688]

@@SuperMarkusparkus while Thomas is wrong, answer to your question depends on which cpu you want to use for example for intel cpu there is instruction rsqrt14_ps obviously its still your problem to organize your data so you do 16 calculation of normales at once, otherwise no 16x profit.

[@kennyotsu4357]

This is how legends are born: *man appears out of nowhere, disintegrates the fuck out of ancient code and vanishes into silence*

[@KevinTan]

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"*

[@Korbert]

Well no that made him become the CTO for Oculus

[@sbravoo]

@@Korbert how do you know that ?

[@Korbert]

@@sbravoo This is not the only impressive thing John Carmack has done, he's a "famous coder" if you will so you can bet i took notice when he left ID Software and went to Oculus as CTO.

[@sbravoo]

@@Korbert yeah i know carnamak i misunderstood i thought he was talking about Nemean cause he uploaded this video and then disappeared

[@undefined6947]

"You simply _______ then obviously you ______, it's super easy!" Nearly everything in this video is so far over my head it's insane and fantastic, maybe one day I'll understand what you're talking about.

[@TerjeMathisen]

I worked between 2016 and 2019 on the latest revision of the standard, ieee754-2019. You should probably note that the "evil bit hack" which I've used myself many times over the years, is no longer canonical C: You should instead use either a union, or memcpy() to move the bit pattern between the types. In reality, modern compilers will convert all three into the exact same code, i.e. either nothing (if integer and floating point use the same registers), or a move from one type to the other.

[@ScienceDiscoverer]

If the result is still same, I prefer to use the "evil" hack. As it is more clear what is being done and also it has some old-school vibe to it.

[@ThbopCoder]

The evil bit hack has much more style

[@Robbe1912]

you just explained IEEE 754 better than any tutorial i could find and better than any university teacher i listened to. the animations helped a lot with the understanding process.

[@RezzaBuh]

And in just five minutes...

[@traida111]

Im glad someone understands it. I just did a motorboat and thought ''glad I didnt study maths''

[@oliviapg]

@@traida111 The exponent is how big the number is, the mantissa is specifically what number that is. It's the equivalent of saying "37 billion" instead of "37,000,000,000"

[@icegod4849]

My best understanding of it came from another video game video by Pannenkoek about Super Mario 64 and floats lol

[@secularph8424]

I totally agree

[@kuroexmachina]

the "what the fuck" comment was probably added by another engineer reading the code. The creator was a chad.

[@normalmighty]

Either that, or the dev that wrote it got that line from an online forum and had no freaking idea why it was subtracting from 0x5f3759df. As a dev I understood the rest of what this video covered by just reading through the code for a few seconds. The math behind using the constant 0x5f3759df still just made my brain freeze up. Either the dev had a degree in math (totally possible), or he was just accepting that the line worked.

[@RagbagMcShag]

it's another way of saying "dont ever touch this, just hope it never breaks"

[@aurorastarfury]

@@normalmighty I think we all end up occasionally taking a solution from the Web without fully understanding how it works, but when I do that I include a link to the webpage in the comments for future reference.

[@thewaver8]

@@normalmighty "Either that, or the dev that wrote it got that line from an online forum and had no freaking idea why it was subtracting from 0x5f3759df. " Yeah, an online forum before 1998... sure.

[@jlewwis1995]

@@thewaver8 Well IRC and BBS existed back then, and there were newsgroups too I think, so maybe they got it from one of those places 🤷‍♀️

[@meiowalot7570]

Your 20 minute video explained things better than most of my college courses. The explanation and the way you showed the bit values was really nice. C is the language that keeps on giving. I’ve dabbled in C for many years and I still feel like I haven’t mastered the basics.

[@yut8204]

2 years ago when I watched this, I had no idea what I was looking. After majoring for comp sci for the next 2 years and took Calc 2, Data Structures, and Computer Organization and Architecture, I have come back to video and finally understood the video.

[@shotgun3628]

Wait. This is his only video? Holy shit, what a start

[@rayaqin]

he is not fucking around

[@matiasmiraballes9240]

wow, didn't realize. 20k subs in one video, Holy shit.

[@pablomuzzobar8940]

probably hacked youtube and made himself trending LOL

[@rerere284]

reminds me of that channel that uploaded those gameboy cpu videos, went viral, then never uploaded again.

[@ArnoldsKtm]

Guess he won the KZbin lottery

[@compuholic82]

In the immortal words of my CS professor: "I'm sure that this approach is somewhere in between sloppy mathematics and black magic".

[@uwufemboy5683]

That's how all of my code ends up. I write on intuition alone, so when something eventually works even I don't know why.

[@kiatahi3381]

@@uwufemboy5683 a slow subconscious warning giving me anxiety that this code won’t work and ends up working anyway

[@comatose3788]

Far from sloppy. This is old Amiga Assembly tricks.

[@TheRedeyerecords]

Hilarious 🤣

[@dummybugstudios6450]

Why sloppy?

[@vanderkarl3927]

One of the most inspirational techniques for me. When I learned about this, I began to look for ways of optimizing things that had been taken for granted, no matter for how long.

[@5ilver42]

being someone who never passed any of my calculus classes, this was actually surprisingly easy to follow.

[@BladeOfLight16]

If you couldn't pass calculus, you weren't being taught correctly. Calculus is incredibly intuitive once you're exposed to its principles.

[@user-kk1ys2oo2t]

calc mad simple but this shit is intense

[@prithvidhyani2002]

Calculus is honestly a glorified symbol pushing course imo.

[@MichaelRasch]

I enjoys math and and it's been years since I've opened a calculus book, a professor like this would have made my advancement much more quicker. super easy to understand him and get the full concept.

[@jumpydino3015]

wait what there was no calc im here tho they said newton iteratiom but didnt go into it

[@GucciCaligula]

The original programmers were just maths majors. Now we see why. The closer to the metal you work, the more helpful high level math can be.

[@Sorcerer86pt]

Exactly

[@revimfadli4666]

Especially when you design the metal itself. As a semiconductor engineer :P

[@Sorcerer86pt]

@@revimfadli4666 for example for those who want ultimate cryptocurrency mining nothing beats custom made boards that implement the algorithm in hardware. The so called ASIC miner

[@revimfadli4666]

@@Sorcerer86pt agreed, getting hardware-baked performance, without taking away gpus from people who need them & resigning them to that single use, is a win-win Although I was talking about materials scientists/engineers who formulate the semiconductor material itself & its manufacturing:P

[@OMGclueless]

It's not just being close to the metal. Math helps a lot any time you have a very hard problem to solve -- for example, the folks at OpenAI for example are 90% math PhDs and they don't spend much time programming bare metal I would guess. In the old days every problem was hard so math was valuable for everyone. Now there are lots of problems that programmers can solve that are not "hard" in a traditional sense; making things pretty for customers, implementing simple business models for yet-another-market, taking someone's prototype idea and making it into an app or a website, etc. But if you try to solve cutting-edge problems you will get much further if you understand mathematics deeply, especially linear algebra and multi-variable calculus which come up over and over if you know how to recognize them.

[@graf]

honestly one of the best made videos I've seen on KZbin

[@Wigtor]

Wszędzie bym się spodziewał.. ale nie tutaj

[@carlosmspk]

@@Seagateee Was gonna say the same thing. Even the animation style is similar

[@cannaroe1213]

Frankly, i prefered this German dude, he just shows you what is going on from first principles, didnt try to 'blow your mind', and i learned something.

[@carlosmspk]

@@cannaroe1213 What's wrong with "blowing your mind"?

[@n00blamer]

This one is 2nd best? kzbin.info/www/bejne/ap-2mYebiqp9f7M

[@peterpiksa5130]

As a teenager I spent countless hours playing Quake III and I am just amazed about Carmacks trickery. I would love to see a performance comparison between his code and the usual non-optimized approach.

[@eddievhfan1984]

Additional commentary (as it wasn't super-touched on, but I feel is worth mentioning): the need for this algorithm was because at the time Quake III came out, very few 3D graphics cards had dedicated hardware for calculating lighting and geometry transformations (T&L, it's called), requiring the CPU to do the heavy lifting of doing it advance before pushing the results to the GPU for drawing. Therefore, CPU efficiency was paramount, and integer math is typically much faster than floating-point math in most applications-in most CPUs, you have to send the floating-point values to a separate computing unit (the FPU) and wait to get the results back. And even in the integer math world, multiplication and division by factors other than 2 could be costly operations where every cycle counted. A year before this game launched, AMD came out with the "3DNow!" instruction set extensions, and Intel followed a year later with "SSE," both of which could do the inverse square root in one instruction on multiple data points simultaneously. However, since most people buying the game wouldn't have these new processors immediately to hand, it made the software algorithm a necessity all the same. The first consumer PC graphics card to have hardware T&L support was the Nvidia GeForce 256 in 2001.

[@benpapp8860]

The video goes kind of light on the Newton iteration part so I wanted to clarify some things: f(y) = 1/(y^2) - x y is our estimated inverse square root, and we’re trying to get a better estimate. To do that we want to get f(y) close to zero, which happens when y is correct and x equals the number that we’re taking the inverse-square-root of, ie the input named ‘number’. The x from the above formula isn’t being updated, we know it exactly already. The derivative of f(y) is -2/(y^3). This is because the x is constant, 1/y^2 is the same as y^-2, so multiply by -2 and subtract 1 from the exponent. I was confused about why it looked like we were solving for a new value of x but we aren’t we’re getting a new value of y so the line is really ynew = y - f(y)/f’(y), which after we enter the function and its derivative is ynew = y - (1/(y^2) -x)/(-2/(y^3)) = y + y/2 - x*(y^3)/2 = y * (3/2 - y * y * x/2) …and then it matches the code

[@cosmos555]

Thanks, I was confused by that part as well!

[@artey6671]

Yeah, I think he could have said that x and y have different roles in the graph and the code.

[@trentlangford9050]

Incredible

[@Gnefitisis]

Maybe obvious, but can you explain to me how you know f(y)? Everything else I follow, but as I see it f(x) = y and y ~ (1/x^2), so f(×) ~ 1/x^2. What am I missing?

[@Heydan164]

@@Gnefitisis before i say anything, i would first like to clarify i am no CS student and I also do not 100% follow this, but i think i understand where this part comes from. i think the answer to your question comes from the sequence of steps revolving around why you want to use newtons method and the rearanging of the formula to aquire f(y) instead of f(x). Since you origionally have the function f(x) from the initial steps of this code, but you want to find a more accurate approximation of what "y" would be equal to after the "wtf" line, you need to rearange the formula to make it become a function of "y". This is because you are no longer using "x" in the function you are now using "y" to find "ynew". So technically they are both using the "y" variable, but after performing the newtons approximation it reassignes the calculated value to the variable "y" again, meaning that it was a "function of y to calculate a new y value". I'm not sure if I answered your question, but if you want me to try and explain anything better i can try. But from how i interpretted your question, it seemed like more of a misunderstanding of the use of the applications of the variables in the video, not that you don't understanding the actual pure math being used. I hope this helped, if not I can try again if you'd like lol ✌

[@mousermind]

"But it does hint that there are three steps to this algorithm." Step 1: *Evil Bit Hack* Step 2: *What The Fuck* Step 3: *Newton Iteration*

[@shurik121]

Step 4: Profit!

[@bertusbasson45]

@@shurik121 Step 5: Open source it!

[@SomeFreakingCactus]

Eh, it hints a little. “Evil Bit Hack” = Exploiting the data in a way you’re not supposed to. “What The Fuck” = Black magic sorcery. “Newton Iteration” = Applying a mathematical law.

[@mousermind]

@@shurik121 My man!

[@SquirrelTheorist]

@@SomeFreakingCactus That's what I saw too! It does seem pretty straightforward as far as what it does, but tbh the actual process still hurts my brain to try to figure out

[@LeoStaley]

KZbin has decided that this is my favorite video on all of youtube. It puts it in my recommended videos on AT LEAST every other video, no matter what kind of video it is. I've watched it a couple of times since it was released, but I've watched dozens of other videos more than this one. KZbin has been doing this to me for about 2 weeks now, and It's getting quite amusing.

[@yafiwala]

This is what true content is explaining the reasons behind most of my unanswered questions

[@extremespartan117]

I can't believe someone explained this piece of ancient code so eloquently. I remember reading about this routine years back and not having a single clue how this slice of magic worked. Thank you good sir and have a fantabulous day!

[@elFlexor]

You've explained this legendary piece of code and the concepts super well! One small nitpick (from an HW engineer working on FPUs, not a programmer). The "that's just how C works" part, where pointer aliasing is used for type punning, is actually undefined behavior (in two ways): 1. Using two pointers to the same memory location independently is not guaranteed to work like that in the C standard, but compilers mostly are nice enough to allow it and it works in this case. Using `union` would be better, though I think it's also not 100% clean. The "proper" way of doing it would probably involve explicit `memcpy` calls which would be much less performant. 2. Interpreting IEEE 754 values as anything other than floats is undefined behavior, as there are no guarantees how the bit patterns actually look in the processor. The formats in question are the "interchange formats" for when you need to transfer float values as binary strings. Implementations are allowed to store the values however they like as long as the operations are numerically equivalent, but most CPUs just use the format you've shown, so it works in this case. PS: Nowadays, processors have built-in instructions for inverse square root, so this fast inverse square root is much slower and less accurate than what a modern CPU can provide.

[@tomtravis858]

Haha yes, I really hope this video didn't make anyone actually use this code.

[@dennis8636]

So if pointer aliasing would be generally undefined behavior, basically every HTTP, RTP, etc. parser would be illegal, since it takes a chunk of bytes dropping out of a socket and re-interprets it as e.g. an http-header struct. What you are referring to is breaking the 'strict aliasing rule', which does have some exceptions for legal and well-defined pointer aliasing.

[@sub-harmonik]

In C you can use unions I think (but not in c++ apparently)

[@the_biggest_chungus7508]

@@tomtravis858 :( just threw it into my own little tinkering library....

[@mshopf]

​@@dennis8636 Actually, not *pointers* alias, but memory locations. You are always allowed to address any memory with byte (char) pointers, but memory containing a float may not be accessed by a int pointer (may not meaning it has undefined behavior). Modern gcc will actually optimize the memory access away... been there, got my whole function optimized away. unions are the way to access bit patterns of floats.

[@MisterShnig]

Why don't they show us this kind of stuff in my college courses? Part of what we learned in CS was the flag-exponent-mantissa calculation and we had to write and interpret numbers using it, and although I thought it was very fascinating I only thought of it as a fun fact and nothing more. Never knew it - along with derivations - could be used like this, this is simply awesome!

[@jyutzler]

Because there is virtually zero practical application of this technique. It is so niche it is ridiculous. If anything it would be irresponsible of a professor to waste time on such a thing.

[@MisterShnig]

@@jyutzler I'm not saying they need to show this one specifically - rather, I'm arguing that real-world examples of its usage would make the topic far more interesting and make otherwise seemingly pointless material purposeful.

[@jyutzler]

@@MisterShnig That's just it, there is hardly any practical real-world application.

[@acasualviewer5861]

Computer graphics books are full of weird hacks.. for example, the algorithm for efficiently drawing a straight line in the legendary Foley, Van Dam, et al book. CG is all about hacks like this. The Q3 developers just continued this tradition.

[@enginerdy]

You should know how IEEE floating point _works_ because it’s fundamental to just about any system that’s not ancient or using a decimal library. (For example, understanding why when creating a list of numbers in NumPy, incremented by 0.1, you get …interesting… results) But learning bithacks is pretty useless and not generalizable except as an interesting study.

[@ethanh5978]

Man I’ve had this video saved in my watch later for like a year now and chose the perfect time to watch it. I’m taking computer architecture right now and my teacher is not the greatest at explaining things. Your explanation of IEEE 754 just saved me a ton of trouble 😂 thanks

[@whiskyguzzler982]

I have long heard of this magic, but never understood it. After watching your presentation, I held manager level understanding just for a moment. It’s gone, but that felt good. Thanks for making this understandable, even if only for a moment while you held our hands.

[@oreganorx7]

Lol manager level understanding. Thanks, gonna start using that XD

[@hasrulmuhammad8271]

AD

[@Roald94]

well funny thing is, they actually used engineering methods to solve their computer problem, this is the things that if i did use them, would not make me question myself why am i studying software engineering

[@ryzenforce]

@@Roald94 Well, software engineering today vs the one I studied 30 years ago are way different. It is also the reason why I quit developing and went to the infrastructure side of computing and can now yell at developers that they are not creative anymore and are not unable to optimized anything (my major was algorythmics) : they just copy code and use design patterns because they is no creativity anymore. Also Java...

[@whiskyguzzler982]

@@ryzenforce Ah Knuth!

[@EmanueleShows]

John Carmack is my spirit animal, even just for releasing all of his games' source codes after a couple of years. An absolute genius of a programmer, and a blessing to the gaming world since 1990.

[@lolilollolilol7773]

Just to be clear: he isn't the inventor of the algorithm. It was in use at SGI. In fact, he didn't fully understand how it worked, hence the "WTF" comment. Nevertheless, he is a genius programmer.

[@jonnyj.]

@@lolilollolilol7773 Um... how does that relate to the original comment? The comment was written by someone else, not john carmack

[@JohnSmith-sh1sy]

I remember reading that John Carmack hired someone to optimize Quake 1 code back in the days. So, it doesn't mean that all of Quake source code was written by him.

[@lolilollolilol7773]

@@jonnyj. How do you know ? Any source to back up your claim ? Let's assume the author of the comment wasn't Carmack. Surely he could talk to him since the comment was on the original source code. So it's rather unlikely that the "WTF ?" and the magic constant would have stayed if Carmack knew where they came from. And even then, the algorithm was not invented by John Carmack, that is a well known fact. As soon as the Quake source code was made public, this algorithm was singled out as a source of interest and its origins were traced back to SGI.

[@deViant14]

Personally if I wrote code that devious I'd write What The Fuck next to it myself 🤓🤜🤛😎

[@cronicas_imemoriais]

I watched this video a few months after it came out iirc, it only took me 3 semesters of computer science college, calculus 1 and numeric calculus classes to understand it. Nice!

[@DsiakMondala]

Boa sorte na sua formação fren :3

[@cronicas_imemoriais]

@@DsiakMondala obrigado, amigo, boa sorte com tudo também!

[@GlyphicEnigma]

19:46 "Now we finally understand the fast inverse square root." Hey, speak for yourself, buddy! XD

[@HueghMungus]

IDK why I watched this, I don't even code, I'm still confused as when I started and when I left... What The Fuck!

[@maxtadeu181]

I love that I can understand 99% of the words but 20% of the meaning.

[@stephanebadol3842]

@@maxtadeu181 XD, nice one bud'

[@pirufihho]

@@HueghMungus i work as a programmer, and i didnt understand also lol, too much mathematics

[@phenomanII]

@@HueghMungus I kind of grasped it because it combines what I was taught during the time I spent chasing a degree in CS that I probably won't end up finishing due to other stuff and mental health issues. So yeah, approximately 2 years spent living and breathing CS. (At one point a professor told us we should be spending 8 hours a day, 5 days a week, working with C outside of school, with his class being one of 3 equally difficult classes out of the 6 classes in that semester alone. I wonder where the mental health issues came from.)

[@TheKingLikesArt]

Quake developers: spend months coming up with an algorithm for fast inverse square root All FPS gamers: **turns off all shading**

[@your_neko]

I guess you've forgotten to disable dynamic lighting too.

[@davidwest6019]

At least FPS gamers in 1998. In 2021, we are all a bit spoiled with compute shaders and all...

[@your_neko]

@@davidwest6019 I get spoiled (a bit) with cloth, houses, electricity and computational algorithms every day. I rate it 9/10, but I'd still recommend it to anyone.

[@MasthaX]

All graphics off playing competitive Medal of Honor (which ran on Q3E) was the way to go back in the day.

[@likizsna]

/picmip :)

[@Katianie9]

I was a senior in High School (around 2007) and did this program that was supposed to pair you up with people from the industry you wanted to go into. I love game programming and programming in general. I had a "mentor" that gave me this problem and said "if you cant solve this I cant help you". I'm a professional game programmer now and when I see this problem I still remember me trying to ask professors about fast square root or newtons method and they had no idea. Never was able to solve it, the guy ditched me, and I had to scramble for a new project. About 13 years later I find out it it was a crazy algorithm developed for Quake 3. Good news is I'm a game developer now :)

[@CrazyFanaticMan]

In case anyone is curious, John said in a recent podcast that he was not the one who coded this and is surprised he gets credited for it. It might have come about due to his prolific reputation as one of the best programmers ever. kzbin.info/www/bejne/f2mXZoJrbL-Gr5Y

[@joeblo1111]

Correct. It's the reason for the comment 'what the fuck?' in the code. Id Software didn't fully understand the code at the time when they used it either.

[@kitape007]

Greetings from France. This video kicks a thousand arses. This Quake III algorithm is a mix between mathematical analysis, computer science and wizardry. Thank you.

[@KyotecYT]

What an insane piece of code This just goes to show how much coding is about thought as it is about actual code Amazing explanation, this is almost 3Blue1Brown level quality, you've earned yourself a subscriber

[@kikko77]

same here

[@markkeeper7771]

He's probably using the animation code made by 3b1b

[@ItzTheFury]

great voiceover too :)

[@Niosus]

Sadly, golden nuggets like these are few and far between. Even in good codebases, there is a lot of poorly structured code that tends to build up when bugfix after bugfix after bugfix gets applied without looking at the bigger picture again. And this is not even the fault of the developer, because you also don't want to redo large portions of code every time a bug fix or small feature is inconvenient. Planning and thought are definitely important, but from my experience: Most of the time you'll spend coding is being reactive to the code that already exists. You try to apply minimal changes to it while still making it do what you want to do. Everyone likes small commits!

[@hellobye9178]

I'd actually consider this 3Blue1Brown quality, this is insane! Is this algorithm faster than the normal square root algorithm if you inverse it? I think I'll actually test that.

[@tens0r884]

I love how absolutely simple this is, too often algorithms for seemingly simple tasks become unwieldy but this is so compact

[@B20C0]

Well, I wouldn't say it's "simple". It's short. It's like the first time you learn about recursion and binary trees and find out that you can do insane things with just three lines of code but the thought process behind it can be daunting for beginners. And then you wonder why it's so inefficient and then dive into dynamic programming. It's beautiful really.

[@Crissaegrim-xv9cu]

Thats optimized coding for ya

[@dec13666]

I love how this video has brought several branches of engineering, where doing things _"just by chance, otherwise it won't work bro"_ is eerily common, and unbelievably, very functional.

[@akajette]

I'm sure this is well explained and a mindblowin concept. I'm unsure however why this popped up in my feed and further why I watched the whole thing without understanding even half of it. Now I know how my dog feels when it talk to him

[@igorstasenko9183]

This is why i refrain talking about programming to most of people i meet in my life. Don't wanna humiliate them with my dog-speech down to them :)

[@RagbagMcShag]

but you were a very good boy in doing so

[@igorstasenko9183]

@Sum Ting Wong yes i can. i can also fix your pc, reload paper in your printer, and write a smartphone app which will make you rich overnight :)

[@mateocsaba8801]

@@igorstasenko9183 Can you do all that by tomorrow and also teach me so I don't gave to hire you again? I have $5...

[@peterantonaros6461]

@@igorstasenko9183 Someone's got an EGO lol. Surround yourself with people at or above your level and you can talk about programming all day all night.

[@funkenjoyer]

i love it how they put 1.5 in a constant but the god damn 0x5f3759df is just left as a magic number, like rly?

[@skilz8098]

Obfuscation!!!

[@redgeneral5792]

From what I can gather, its from the formula at 17:10. 3/2 * 2^23 + (127 - mu) If you set mu to 1 3/2 * 2^23 + (127 - 1) ~= 1.58 x 10^9 which converted to hex roughly becomes 0x5f3759df So its not really that magic, although bitwise operations seems that way sometimes.

[@funkenjoyer]

@@redgeneral5792 by "magic number" i dont mean actual magical number but a hardcoded not named number in code, they did make a const float threehalves for 1.5 but no such const has been made for this coefficient

[@LOLmomentsandfails]

@@funkenjoyer I've seen them refered to as "Magic Strings"

[@marcossidoruk8033]

That line is more beautiful like that, if aliens invaded earth we would just need to send that single line and they would resign.

[@nourgaser6838]

I come back to this video every 6 months or so, assessing my learning progress against how much I understood from it. Waiting for the day when I can finally say I fully understand this video.

[@waynedick6989]

That was really fun. I used to write code generators for compilers. We did that crazy stuff all the time. I was down the hall from the math functions group. You should see what is inside something like a library square root function.

[@rijuchakraborty7679]

Nemean: "Take a moment to look at it again" Also Nemean after 3 seconds: "Well, the longer you look at it the less it makes sense"

[@budabudimir1]

The reason why "The Evil Bit Hack" is indeed Evil, is because according to the C standard, this is actually Undefined Behavior.

[@michaelterrazas1325]

Absolutely true. And if the code were meant to be implemented on several platforms, it would fail horribly (e.g. most modern processors have 64 bit longs, but that compiler on that processor had 32). But when you have to eke out the last few cycles and you don't need portability, it can work wonderfully. I have a lot of code flying around in space that uses UB because we needed the memory space or cycles to succeed. Pragmatism can be a virtue.

[@budabudimir1]

@@michaelterrazas1325 Yep, I agree, there are even situations where you cannot get the performance you want if you were to follow the standard to the letter. And you shouldn't; all you *need* to do is solve your problem and that's it. This case, however, you can solve with modern compilers without breaking the standard by just using memcpy. This wasn't the case back in the day of Q3.

[@RushilKasetty]

Really? Which part is undefined? Is it the last part where you dereference the long pointer?

[@michaelterrazas1325]

@@RushilKasetty 1) Casting a pointer of one type into another and then accessing the object stored there. 2) Looking at the bit patterns in a float. 3) Assuming a congruence between the size of a float and a long. 4) Performing integer arithmetic on a float object.

[@nullplan01]

@@michaelterrazas1325 OK. But the algorithm can be made portable by using a union instead of type-punning, using uint32_t instead of long, and testing for IEEE 754, for which there is a macro in C99. Then you know that a float is an IEEE 754 single prec number (so 32 bits), and the union takes care of the rest.

[@clay1086]

This explained IEEE754 in 20 min much better than weeks in my college class... nice

[@Jono.]

I enjoy greatly that the creator of this video just blew my mind with IEEE 754 structuring, number modification through bit manipulation, and just concludes the video once everything was said. This video was so cool!

[@Manusmusic]

"You might already see where this is going". No, no I do not.

[@pleasecontactme4274]

lol same feeling

[@skorlupkaskorlupkovich2415]

The misunderstanding there comes from not knowing why a length of a vector is calculated in such a way. First, you should keep in mind that this vector exists in 3 dimensions, not 2. Second, the math - kzbin.info/www/bejne/a2LZmHycmaefd80&ab_channel=rootmath

[@_xiper]

No, I don't think I will.

[@achtsekundenfurz7876]

> "You might already see where this is going" "Yeah, same direction as the original vector, but at a different speed"

[@schifty1809]

I have a master's degree in CS and I was not seeing where he was going.

[@dino2808]

The WTF step made my day The approximation of the log of a float to its own binary representation is amazing

[@redguard128]

Well, real numbers can't be represented in memory anyway since they have an infinite number of digits. So everything in the end is an approximation. Usually after 8 digits it's "good enough". For me usually 2 digits is good, but I work with milisecond. So for me 3.27 miliseconds is a good approximation, having 3.2698 is just useless.

[@deedewald1707]

@@redguard128 Measures twice cuts once is one's process !

[@deedewald1707]

If it saves a milli-second, done a million times saves lots of computation time any time !

[@YuriPlanzo]

The right way to watch it is to watch it two times in a row. Absolutely amazing!!

[@u.knowmysteelo]

Ironically, this is the best explanation of IEEE 754 I've ever seen.

[@Minitomate]

The explanaition among the smooth animations and the genius of Quake's III engineers makes this one of the best explainatory videos I ever seen in this platform.

[@roboto_]

the IEEE float explanation is so damn good

[@AncientYaky]

This was fun to watch right after my FE exam, great video! Explained really well, especially for someone burnt out

[@empressredbird]

the fact that somebody came up with that shows such a good understanding of math and software workings

[@thomasburette9129]

The almighty youtube recommendation algorithm brought me to this video. Nemean : I cannot overstate how good this video is. Please make more of this!

[@tobyfitzpatrick3914]

I found a bug...."threehalfs" should actually be spelt "threehalves"

[@mastermati773]

Commit accepted. You are now a contributor! Congratulations!

[@benwest5293]

"halfs" is a nonstandard plural of "half", but that doesn't necessarily make it _incorrect_... After all, it's an acceptable Scrabble word 🤔

[@garethevans9789]

Half is the noun. Halve is both the verb and the plural. (I only know as I looked it up last year). Personally, I prefer the nouns for variable names and verbs for methods. Even though three halves is the correct English. A bigger issue is that they couldn't be bothered to capitalise the leading character of the second word.🙄

[@akhilesh6072]

@@garethevans9789 Agree, camel case

[@Kyrelel]

@@akhilesh6072 *CAML

[@matwilcoxson2849]

It's remarkable how clearly you were able to explain this extreme algorithm. Please continue to teach us!

[@bombardygamer4248]

Great video! Great explanation of IEEE 754, and all of the calculations here. One thing that I couldn't ignore though is that whether long is 32 bits or 64 bits is platform dependent. For example, Windows likes to be weird and have long be 32 bits (iirc), and UNIX-like systems tend to make long 64 bit, though I think it also depends on what the pointer width is.

[@sammyfromsydney]

Code review: Missing about a dozen comments.

[@farhanyousaf5616]

Please re-write, not readable code. And use math.h, and please, add faster processors to get the same speed. PR sent back. :)

[@KnishG]

@@farhanyousaf5616 lmao it hurts

[@metalpachuramon]

@@farhanyousaf5616 hahaha exactly my thoughts, they might've not gotten away with it nowadays. I feel like code reviews sometimes miss the point

[@mapron1]

@@metalpachuramon What do you mean "miss the point" ? First point for every code is being readable and maintainable. We are sacrificing this only if the performance is important. And as I wrote a lot of perf-critical code, I can say that on review colleagues of mine always asked to improve readability without penalizing a performance. And if in your company reviews are equal to "check for code style" than you have a problems with expertise and/or review culture. It should be the experience sharing first of the place.

[@agustinsida8877]

@@mapron1 this is why no one likes you

[@NomadUrpagi]

I am an PLC engineer myself but man, these IT guys always seemed too smart for me. God. That guy knows coding, math AND physics.

[@revimfadli4666]

So like a robotics guy?

[@NomadUrpagi]

@@revimfadli4666 general industrial process automation. That can include robotics, but rarely. I only look after 1 robot.

[@NomadUrpagi]

@Qimodis the rules of physics had to be applied in the game as well for realistic lighting, so yes, this is really physics. Anytime you are dealing with animation and lighting you have to give objects in the program properties and rules that resemble real life physics behavior, in that way only it will look realistic.

[@Mr.Leeroy]

@@NomadUrpagi Remember that it was not a single person behind this engine and there was some level of separation, who deals with physics, who is modeling, level designing... So we a probably forgetting how important teamwork and knowledge sharing between those teammates was. IMO, it is possible that people who coded this were not that level of Gods as we now think, but their teamwork was so synergetic, that they were able to come up with such brilliances.

[@fcw2bom]

@@revimfadli4666 if he wanted to say robotics he would've said that.

[@___-._.-___]

best explanation I have seen on IEEE-754 , I understood more in those 5 min than my prof's 1hr lecture

[@wolcamophone4783]

I started my freshman year in an 8 week course for Intermediate Algebra and got to have fun talking with the tutors in the library over the more nerdy high-concept math bits I wanted to eventually try studying for my game. This was brought up as a discussion and I still don't quite get it. On top of this though, computers are way better than they were back then so we typically don't focus on micro-optimizing like this anymore, but it's still good to be conscious of as opposed to the current generation that is cosying into the idea that machines just do everything for you with one push of a button and that being slow is just something we either deal with or splurge to upgrade our rig.

[@hansangb]

He came dangerously close to the most hated words for eng students. "It can be easily shown that...." and he ACTUALLY used the corollary of the above hated words "It's left as an exercise for the reader...." LOL. Thanks for the video.

[@Andre299792458]

This video is made so well, that I actually managed to understand it without a C programming experience. Far better than any other video on this topic.

[@JoffreyBion]

The quality of this video is absolutely through the roof. The animations and colors are just on point. It's perfect. I just keep coming back to re-watch it with some fellow developers everytime we talk about hacks and being "smart". And I'm still amazed by the quality every single time.

[@vapeurdepisse]

Q III memories... Wow going way back! Golden era.

[@Bhuyakasha]

For anyone wanting to see the final derivation at 19:10: f(y) = 1/y^2 - x f'(y) = -2/y^3 y_new = y - f(y)/f'(y) = y + (1/y^2 - x)*y^3/2 = 1.5*y - 0.5*xy^3 = y*(1.5 - 0.5*xy^2)

[@Ruben_M.]

Been a while since I have done derivatives and partial derivatives, but for this case, dx/dy is ignored or removed? Unless I’m misinterpreting the math here, which is possible since these calculations were never easy for me.

[@Bhuyakasha]

@@Ruben_M. x is not a function of y here, so it just drops out of the equation there

[@Ruben_M.]

@@Bhuyakasha Ah that makes sense I suppose, thanks for the clarification!

[@deadlypoe5_710]

Excuse me, maybe I’m lost; But what the fuck is this?

[@deadlypoe5_710]

I’m joking

[@EnderFlop]

This video is actually incredible. I've seen this piece of code before and this explanation made it super clear and understandable. Amazing!

[@windwatcher460]

Love it when the calculus is the trivial part. Thanks for the explanation

[@brockobama257]

Literally watch this video every other month because it’s fascinating

[@SecondQuantisation]

I love examples like this. They aren't "Wow, what a mathematical genius" but instead "The person who thought this up clearly has a genius level mastery of their craft". I know about Newtonian iteration, logs, the physics related to using normed vectors etc but I would never. EVER. think of this. A friend of mine does coding where to get extreme speeds out of the computer they'll do compiler tricks specific to the architecture of the CPU so they can do similar stuff to this. I don't understand what he does.

[@krishgarg2806]

oh boi, do they mess with assembly?

[@78anurag]

Most of the computer scientists and game developers are trained in algorithm making and mathematical methods, so it is no surprise they made this

[@rkmag1141]

They know how to get into the “Flow”

[@lightning2665]

This guy explained the standard ieee 754 better than my professor

[@silakanveli]

Sure. Professor just did not understand it himself.

[@Lindaine]

Even a random indian girl on yt, giving example of converting decimal to IEEE 754 explain it better than my professor.

[@LunarSoul255]

'Evil Bit Hack' is a good band name

[@alvarobarboza5730]

thank you, you helped me understand IEEE 754

[@DaelinTV]

Lmao this guy is so confident in me 😭

[@botlarry4437]

He believes in your ability to understand. Do you?

[@botlarry4437]

@Victor Joseph Yeah me too. Snek language is fun :) Variable type? Whats that?

[@ko-Daegu]

@@botlarry4437 wait you guys only did python never touched C or Assembly?

[@botlarry4437]

@@ko-Daegu I've played around with it for Arduino projects but in no way efficient at it. C is not really suited for most of the work I do.

[@ko-Daegu]

@@botlarry4437 ooh that's fine as far as you get a taste for low-level prog you are good better than never touching something and staying only in py/js world

[@tomkandy]

"Premature optimisation is the fast inverse square root of all evil" - Donald Knuth, probably

[@minastaros]

@Michael: the most important word in the quote is "premature". I don't think that Knuth was against optimization in general. And I agree with you in the sense that one shouldn't cluelessly waste cycles (or memory, or both). But it doesn't make sense to fiddle around with bits at every place in the code from the beginning, unless you find some really hot spots that lead to a huge performance gain when optimized later. Many other early "optimizations" might turn out as nearly useless.

[@MichaelPohoreski]

​@@minastaros The first problem is that shitty programmers solely focus on "premature" and use it as an _excuse_ to _never_ optimize. Their "solution" is to just throw more money (hardware) at the problem. **FACEPALM** The second problem is that the **entire sentence** _"Premature optimization is the root of all evil_" itself **is complete bullshit.** Optimization is NOT the problem, let alone premature optimization. Shitty class designs such as mis-using OOP with deep hierarches, ignoring performance, ignoring memory management, shitty function and variable names, never looking at the assembly output of the compiler, etc. are MUCH more important then optimizing the "wrong" thing. Third, there is no such thing as "premature optimization". You are gathering a data point about potential performance! However it needs to be done in the CONTEXT of the larger problem. Are you being _efficient_ at WHAT you are optimizing? i.e. The most bang for the buck? Software engineering is all about managing decreasing returns. Optimization doesn't magically make that go away. First, you CALCULATE the maximum theoretical speed "best case". You will NEVER be faster then this! How do you KNOW your implementation is slow? By comparing to the best case! Next, you write a REFERENCE implementation because it doesn't matter how fast you are if you return the wrong results. Then once you have a working algorithm you can then focus on the what _exactly_ is happening to the data. You then write a DATA ORIENTED DESIGN version because it is simple to write, and fast. So yeah, the entire phrase is entirely misleading, inaccurate, and generally treated as dogma by programmers who are generally clueless.

[@nicholaswood3250]

@@MichaelPohoreski I think the point of that somewhat glib saying is that a lot of inexperienced programmers focus way too much on optimizing their code before they have a clear idea of what level of optimization is appropriate for the task at hand. In my experience there very much *is* such a thing as a premature optimization. It happens when you spend days or weeks making something perform like, 10% faster or smaller when that 10% doesn’t add up to more than what that engineering time was worth to you in the first place. Sometimes, like with Quake 3, coming up with something like this is necessary due to hardware limitations. Very often, it’s really not, and the not-clever solution is fine. I also find it really annoying when people hold up this sort of programming math trick as the line that separates good programmers from “shitty programmers”. It’s kind of elitist.

[@nicholaswood3250]

Also, I’ve read Carmack’s writings on programming, and I can’t recommend him enough. He’s a genius, but I also find him to be a very practically minded engineer as well, and his approach to design and software architecture is really insightful.

[@MichaelPohoreski]

@@nicholaswood3250 Optimization starts _before_ you write code -- not after. If you aren't thinking of cache lines and HOW the data is being accessed you are a shit programmer. There is **a reason** Fred Brooks stated: _Show me your flowcharts and conceal your tables and I shall continue to be mystified. Show me your tables and I won't usually need your flowcharts; they'll be obvious._ The modern vernacular is: _Show me your code and I'll have to guess at your data structures. Show me your data and I won't have to see your code; I'll already know it._ Bad programmers think about code / algorithms first. Good programmers think about data first. Optimization **begins** at day zero. _Not after the fact._ This is why that ignorant statement by Knuth is complete bullshit. The people who don't know how to optimize constantly make excuses for why they remain stupid.

[@the5thalmond]

After taking classes in Computer Engineering, Approximation Theory, and Programming, and this being at least my 3rd watching of this video I think I can confidently say I actually understand it. Actually felt amazing, the only grayish area still is how they ended up on that 0x5f37 constant(more so actually calculating it), but the explanation in the video was really good. Now maybe in a year on my 4th watching ill actually understand that as well.

[@sidgar1]

From what I gathered from other comments, the original author of the function (not Carmack, who never claimed he was), found the constant through trial and error and produced only a 0.175% error , and later, a coder named Chris Lomont updated this number to 0x5F375A86 which drops the error to only 0.09% after just 1 iteration

[@SUPERNOOB20]

​@@sidgar1 I see. Helpful insight, thank you for adding that up!

[@SpritzMcSoda]

This has become my absolute favorite youtube video. It makes me miss doing calculus in high school, because I was actually good at it and understood it, but because there were literally ZERO jobs out of high school that used high math, I never continued. I'm kind of pissed off that I came of age before game development was a multi billion dollar industry. Anyways this video is so good, it blows my mind...as does id's algorithm.

[@JCMinaya]

Note. This became obsolete "in 2009 a benchmark on the Intel Core 2, this instruction took 0.85ns per float compared to 3.54ns for the fast inverse square root algorithm, and had less error."

[@rhettorical]

The fact that no one knows exactly who wrote the code is my favorite part of the whole situation.

[@kurzackd]

Where is this said? It was John Carmack who wrote the code.

[@Vizimech]

@@kurzackd It predates Q3A, the Q3A source code is just where it became mainstream knowledge. Apparently one of the earliest known usages was in the SGI Indy but it predates that as well.

[@macaw2000]

Almost certainly Michael Abrash. This is not Carmack-esque code.

[@kurzackd]

@@macaw2000 ...source?

[@macaw2000]

@@kurzackd Dave Plummer basically told us in his last video. But you can also just see it in the code (Abrash's books and timing at iD also give it away)

[@Nature112091777]

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...

[@khaoscero]

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.

[@roberte2945]

@@khaoscero That explains a lot of Unity trash that looks terrible and makes your graphics card hot enough to fry eggs.

[@madezra64]

@@roberte2945 Unity is wasted potential in my eyes. They should have just stuck with C++ like unreal engine. Using C# as a scripting language is great, but NOT for fast 3D graphics.

[@snooks5607]

no shame in not being able to recreate original Pong as a programmer since it wasn't software in the first place but discrete logic chips. first 4bit CPU had only just been invented (building computer in a game machine out of discrete chips would've been cost-prohibitive before that)

[@naprava7522]

If you can’t do pong, I question the fact that you are actually a programmer. It’s very important to understand the basics. Try and do it! You will learn a tone !

[@quakecon2009]

I'm too dumb to understand, but will take your word for it.

[@RJNoe]

I've seen my share of evil bit hacks in my day (started UNIX/C programming at Bell Labs 40 years ago) but this is among my favorites. Very well done video! No one's asked, but if anyone is wondering where that mu value is from, here are the nasty details ["log2" denotes base 2 logarithm, "~=" denotes approximately equal]. So you want to approximate f(x) = log2 (x + 1) for 0

[@Nemean]

Wikipedia claims that nobody actually knows how exactly they got their 0x5f3759df because, as you said, the other constant would be better.

[@RJNoe]

So I got to wondering, can we find a value of mu that makes the approximation g(x) = x + mu optimal, i.e. minimizes the total error over the interval [0,1] for estimating f(x) = log2(x + 1)? Turned out to be easier than I expected. What we want is to minimize the result of the integral from x=0 to 1 of [f(x) - (x + mu)]^2 dx. This is not as hairy as it might look. Expanding the square, we get an integral of sums, but can ignore any term in the sum that doesn't involve mu, as that will result in a constant. You can integrate f(x)^2 by parts, it's not hard, but completely unnecessary. Ignoring the constant term, what we get is a quadratic equation in mu: mu^2 - c mu where c = 3 - 2 log2(e). This is minimized when mu = c/2 = 1.5 - log2(e) ~= 0.057304959, just a little greater than what we had. The upshot is if you wanted to slightly increase the accuracy of estimating f(x) over this interval, change the bizarre constant in the algorithm to 0x5f34ff59.

[@teson2000]

"The algorithm was originally attributed to John Carmack, but an investigation showed that the code had deeper roots in both the hardware and software side of computer graphics. Adjustments and alterations passed through both Silicon Graphics and 3dfx Interactive, with Gary Tarolli's implementation for the SGI Indigo as the earliest known use. It is not known how the constant was originally derived, though investigation has shed some light on possible methods." /Wikipedia

[@fye7785]

"// What the fuck?" Killed me

[@jimhalpert9803]

I too like to cuss in code comments

[@achtsekundenfurz7876]

That's what I said at 06:09. Why does every math youtuber display at least ONE wrong example???

[@ArnoldsKtm]

@@achtsekundenfurz7876 because you learn from mistakes. Seeing mistakes is a part of it.

[@xDFoRcEzZ]

I literally have no idea what I just watched but I watched it all.

[@FrappuccinoAlfredo]

19:47 "Now we finally understand..." You mean YOU understand