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
@otesunki3 жыл бұрын
well he used it twice... until it got commented out
@richardbloemenkamp85323 жыл бұрын
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.
@francoiscoupal70573 жыл бұрын
@@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.
@DaMonster3 жыл бұрын
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.
@VincentWoo3 жыл бұрын
@@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.
@owfan41343 жыл бұрын
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
@martiensventer91912 жыл бұрын
And Statistics. And pretty much any other field where approximating confusing maths becomes neccesary.
@martiensventer91912 жыл бұрын
necessary* damnit I hate English sometimes
@Andrew-ri5vs2 жыл бұрын
And information theory
@TheALPHA15502 жыл бұрын
@@martiensventer9191 *Math
@abebuckingham81982 жыл бұрын
A joke among mathematicians is "What sounds does a number theorist make when they drown? Log(log(log(log(log(log(log..."
@the_hiroman2 жыл бұрын
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.
@lugia88889 ай бұрын
@@MrRenanwill not all functions but yeah some of them
@fhudufin8 ай бұрын
@ 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.
@thepuzzlemaker21593 жыл бұрын
"I don't know what else to say, that's just how C works" An excellent explanation of all of C
@frydac3 жыл бұрын
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 :)
@damaomiX3 жыл бұрын
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).
@TurboXray3 жыл бұрын
@@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).
@vincei42523 жыл бұрын
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.
@ekremdincel15052 жыл бұрын
@@vincei4252 C++ move semantics are overengineered in a stupid and useless way.
@carykh3 жыл бұрын
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!
@shaneman11143 жыл бұрын
Wtf cary kill hitler holy shit
@thegavinjackson3 жыл бұрын
Its cary kicks homes!
@chickendoodle323 жыл бұрын
It's just like fact families in math. You think it's useless right up until you need to do something.
@XZYSquare3 жыл бұрын
lol that's actually funny
@smallcatgirl3 жыл бұрын
Ok. I'm 5th
@JackRackam2 жыл бұрын
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
@grantgoodman84152 жыл бұрын
Funny seeing you here!
@krccmsitp28842 жыл бұрын
Same here! ;-)
@aesir1ases642 жыл бұрын
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
@LarsSveen2 жыл бұрын
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_kizilkaya2 жыл бұрын
Did you ever actually get into game development?
@LarsSveen2 жыл бұрын
@@yusuf_kizilkaya Nope. And now I'm old and burned-out.
@yusuf_kizilkaya2 жыл бұрын
@@LarsSveen never too late, and being a game developer now is easier than ever. Maybe you could still give it a shot
@FurryWrecker9112 жыл бұрын
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.
@reedlaww2 жыл бұрын
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-bk5fc3 жыл бұрын
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"
@francoiscoupal70573 жыл бұрын
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.
@WXKFA3 жыл бұрын
pointers, references and type casting is the best part of c/c++
@Evan490BC3 жыл бұрын
@@WXKFA ... or the worst.
@geiger213 жыл бұрын
@@Evan490BC they are the worst for the same poeple who are afraid of goto
@Evan490BC3 жыл бұрын
@@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.
@jamesmelton76373 жыл бұрын
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.
@xyrus3452 жыл бұрын
Saying Perl has a few peculiar syntactic quirks is like saying a porcupine has a few sharp points.
@gironic2 жыл бұрын
Perl : a write-only language.
@RME760482 жыл бұрын
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.
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:
@Naburgondux5 ай бұрын
That's true in web dev xD
@neofox25265 ай бұрын
@@Naburgondux Yeah luckily loll
@JeffThePoustman5 ай бұрын
@@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.
@Coldsteak3 ай бұрын
you need to be good at maths to be godly at programming
@ajreukgjdi942 ай бұрын
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
@sgtblu33 жыл бұрын
I found out about that inverse square root in 2010 (about) and only now, a decade later, has it been explained well. Thank you!
@fredg83283 жыл бұрын
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.
@General12th3 жыл бұрын
@@fredg8328 I think this explanation is better than those explanations.
@Kyrelel3 жыл бұрын
This video takes far too long and too many unnecessary steps :/ Oh, and one of them is wrong, see if you can spot it.
@General12th3 жыл бұрын
@@Kyrelel I disagree. Every step is necessary. Anything less won't give a sufficently complete understanding of the subject.
@Jawis323 жыл бұрын
@@Kyrelel seems correct to me? Where do you spot a mistake?
@johnfaustus13 жыл бұрын
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.
@IkethRacing2 жыл бұрын
it's not Gary T. as mentioned at 10:41?
@jcsc20012 жыл бұрын
@@IkethRacing no it's Gary v. He discovered it when his entire NFT stock portfolio plummeted.
@franklydoodle3502 жыл бұрын
@@jcsc2001 Hahahahaha
@generalbutz84772 жыл бұрын
What is this methods name
@davidrossington97562 жыл бұрын
I think we still call it John Carmack's Function since he was the first guy to talk about it
@jgcodes20202 жыл бұрын
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.
@reddistone9 ай бұрын
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*
@horleckshelmos84728 ай бұрын
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.
@ObtecularPk8 ай бұрын
I ain't reading all that man
@Daniel-ns716177 ай бұрын
@@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.
@kethernet3 жыл бұрын
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.
@Debrugger3 жыл бұрын
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.
@SuperMarkusparkus3 жыл бұрын
@@Debrugger So how would you go about this today?
@sddndsiduae4b-6883 жыл бұрын
@@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.
@Reydriel3 жыл бұрын
@@SuperMarkusparkus Literally just write 1/sqrt(x) and let the compiler optimise
@sddndsiduae4b-6883 жыл бұрын
@@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.
@kennyotsu43573 жыл бұрын
This is how legends are born: *man appears out of nowhere, disintegrates the fuck out of ancient code and vanishes into silence*
@KevinTan3 жыл бұрын
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"*
@Korbert3 жыл бұрын
Well no that made him become the CTO for Oculus
@sbravoo3 жыл бұрын
@@Korbert how do you know that ?
@Korbert3 жыл бұрын
@@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.
@sbravoo3 жыл бұрын
@@Korbert yeah i know carnamak i misunderstood i thought he was talking about Nemean cause he uploaded this video and then disappeared
@undefined69472 жыл бұрын
"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.
@ScienceDiscoverer8 ай бұрын
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.
@ThbopCoder3 ай бұрын
The evil bit hack has much more style
@Robbe19123 жыл бұрын
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.
@RezzaBuh3 жыл бұрын
And in just five minutes...
@traida1113 жыл бұрын
Im glad someone understands it. I just did a motorboat and thought ''glad I didnt study maths''
@oliviapg2 жыл бұрын
@@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"
@icegod48492 жыл бұрын
My best understanding of it came from another video game video by Pannenkoek about Super Mario 64 and floats lol
@secularph84242 жыл бұрын
I totally agree
@kuroexmachina3 жыл бұрын
the "what the fuck" comment was probably added by another engineer reading the code. The creator was a chad.
@normalmighty3 жыл бұрын
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.
@RagbagMcShag3 жыл бұрын
it's another way of saying "dont ever touch this, just hope it never breaks"
@aurorastarfury3 жыл бұрын
@@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.
@thewaver83 жыл бұрын
@@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.
@jlewwis19953 жыл бұрын
@@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.
@shotgun36283 жыл бұрын
Wait. This is his only video? Holy shit, what a start
@rayaqin3 жыл бұрын
he is not fucking around
@matiasmiraballes92403 жыл бұрын
wow, didn't realize. 20k subs in one video, Holy shit.
@pablomuzzobar89403 жыл бұрын
probably hacked youtube and made himself trending LOL
@rerere2843 жыл бұрын
reminds me of that channel that uploaded those gameboy cpu videos, went viral, then never uploaded again.
@ArnoldsKtm3 жыл бұрын
Guess he won the KZbin lottery
@compuholic823 жыл бұрын
In the immortal words of my CS professor: "I'm sure that this approach is somewhere in between sloppy mathematics and black magic".
@uwufemboy56833 жыл бұрын
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.
@kiatahi33813 жыл бұрын
@@uwufemboy5683 a slow subconscious warning giving me anxiety that this code won’t work and ends up working anyway
@comatose37883 жыл бұрын
Far from sloppy. This is old Amiga Assembly tricks.
@TheRedeyerecords3 жыл бұрын
Hilarious 🤣
@dummybugstudios64503 жыл бұрын
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.
@MichaelRasch11 ай бұрын
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.
@jumpydino301510 ай бұрын
wait what there was no calc im here tho they said newton iteratiom but didnt go into it
@GucciCaligula3 жыл бұрын
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.
@Sorcerer86pt3 жыл бұрын
Exactly
@revimfadli46663 жыл бұрын
Especially when you design the metal itself. As a semiconductor engineer :P
@Sorcerer86pt3 жыл бұрын
@@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
@revimfadli46663 жыл бұрын
@@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
@OMGclueless3 жыл бұрын
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.
@graf3 жыл бұрын
honestly one of the best made videos I've seen on KZbin
@Wigtor3 жыл бұрын
Wszędzie bym się spodziewał.. ale nie tutaj
@carlosmspk3 жыл бұрын
@@Seagateee Was gonna say the same thing. Even the animation style is similar
@cannaroe12133 жыл бұрын
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.
@carlosmspk3 жыл бұрын
@@cannaroe1213 What's wrong with "blowing your mind"?
@n00blamer3 жыл бұрын
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.
@eddievhfan198410 ай бұрын
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.
@benpapp88602 жыл бұрын
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
@cosmos5552 жыл бұрын
Thanks, I was confused by that part as well!
@artey66712 жыл бұрын
Yeah, I think he could have said that x and y have different roles in the graph and the code.
@trentlangford90502 жыл бұрын
Incredible
@Gnefitisis2 жыл бұрын
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?
@Heydan1642 жыл бұрын
@@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 ✌
@mousermind2 жыл бұрын
"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*
@shurik1212 жыл бұрын
Step 4: Profit!
@bertusbasson452 жыл бұрын
@@shurik121 Step 5: Open source it!
@SomeFreakingCactus2 жыл бұрын
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.
@mousermind2 жыл бұрын
@@shurik121 My man!
@SquirrelTheorist2 жыл бұрын
@@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
@LeoStaley2 жыл бұрын
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
@extremespartan1172 жыл бұрын
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!
@elFlexor3 жыл бұрын
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.
@tomtravis8583 жыл бұрын
Haha yes, I really hope this video didn't make anyone actually use this code.
@dennis86363 жыл бұрын
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-harmonik3 жыл бұрын
In C you can use unions I think (but not in c++ apparently)
@the_biggest_chungus75082 жыл бұрын
@@tomtravis858 :( just threw it into my own little tinkering library....
@mshopf2 жыл бұрын
@@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.
@MisterShnig2 жыл бұрын
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!
@jyutzler2 жыл бұрын
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.
@MisterShnig2 жыл бұрын
@@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.
@jyutzler2 жыл бұрын
@@MisterShnig That's just it, there is hardly any practical real-world application.
@acasualviewer58612 жыл бұрын
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.
@ethanh597810 ай бұрын
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
@whiskyguzzler9823 жыл бұрын
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.
@oreganorx73 жыл бұрын
Lol manager level understanding. Thanks, gonna start using that XD
@hasrulmuhammad82713 жыл бұрын
AD
@Roald943 жыл бұрын
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
@ryzenforce3 жыл бұрын
@@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...
@whiskyguzzler9823 жыл бұрын
@@ryzenforce Ah Knuth!
@EmanueleShows3 жыл бұрын
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.
@lolilollolilol77733 жыл бұрын
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.3 жыл бұрын
@@lolilollolilol7773 Um... how does that relate to the original comment? The comment was written by someone else, not john carmack
@JohnSmith-sh1sy3 жыл бұрын
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.
@lolilollolilol77733 жыл бұрын
@@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.
@deViant142 жыл бұрын
Personally if I wrote code that devious I'd write What The Fuck next to it myself 🤓🤜🤛😎
@cronicas_imemoriais2 жыл бұрын
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!
@DsiakMondala2 жыл бұрын
Boa sorte na sua formação fren :3
@cronicas_imemoriais2 жыл бұрын
@@DsiakMondala obrigado, amigo, boa sorte com tudo também!
@GlyphicEnigma3 жыл бұрын
19:46 "Now we finally understand the fast inverse square root." Hey, speak for yourself, buddy! XD
@HueghMungus2 жыл бұрын
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!
@maxtadeu1812 жыл бұрын
I love that I can understand 99% of the words but 20% of the meaning.
@stephanebadol38422 жыл бұрын
@@maxtadeu181 XD, nice one bud'
@pirufihho2 жыл бұрын
@@HueghMungus i work as a programmer, and i didnt understand also lol, too much mathematics
@phenomanII2 жыл бұрын
@@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.)
@TheKingLikesArt3 жыл бұрын
Quake developers: spend months coming up with an algorithm for fast inverse square root All FPS gamers: **turns off all shading**
@your_neko3 жыл бұрын
I guess you've forgotten to disable dynamic lighting too.
@davidwest60193 жыл бұрын
At least FPS gamers in 1998. In 2021, we are all a bit spoiled with compute shaders and all...
@your_neko3 жыл бұрын
@@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.
@MasthaX3 жыл бұрын
All graphics off playing competitive Medal of Honor (which ran on Q3E) was the way to go back in the day.
@likizsna3 жыл бұрын
/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 :)
@CrazyFanaticMan2 жыл бұрын
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
@joeblo11112 жыл бұрын
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.
@kitape0073 жыл бұрын
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.
@KyotecYT3 жыл бұрын
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
@kikko773 жыл бұрын
same here
@markkeeper77713 жыл бұрын
He's probably using the animation code made by 3b1b
@ItzTheFury3 жыл бұрын
great voiceover too :)
@Niosus3 жыл бұрын
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!
@hellobye91783 жыл бұрын
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.
@tens0r8842 жыл бұрын
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-xv9cu9 ай бұрын
Thats optimized coding for ya
@dec136662 жыл бұрын
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.
@akajette3 жыл бұрын
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
@igorstasenko91833 жыл бұрын
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 :)
@RagbagMcShag3 жыл бұрын
but you were a very good boy in doing so
@igorstasenko91833 жыл бұрын
@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 :)
@mateocsaba88013 жыл бұрын
@@igorstasenko9183 Can you do all that by tomorrow and also teach me so I don't gave to hire you again? I have $5...
@peterantonaros64613 жыл бұрын
@@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.
@funkenjoyer3 жыл бұрын
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?
@skilz80983 жыл бұрын
Obfuscation!!!
@redgeneral57923 жыл бұрын
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.
@funkenjoyer3 жыл бұрын
@@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
@LOLmomentsandfails3 жыл бұрын
@@funkenjoyer I've seen them refered to as "Magic Strings"
@marcossidoruk80333 жыл бұрын
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.
@waynedick69892 жыл бұрын
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.
@rijuchakraborty76793 жыл бұрын
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"
@budabudimir13 жыл бұрын
The reason why "The Evil Bit Hack" is indeed Evil, is because according to the C standard, this is actually Undefined Behavior.
@michaelterrazas13253 жыл бұрын
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.
@budabudimir13 жыл бұрын
@@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.
@RushilKasetty3 жыл бұрын
Really? Which part is undefined? Is it the last part where you dereference the long pointer?
@michaelterrazas13253 жыл бұрын
@@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.
@nullplan013 жыл бұрын
@@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.
@clay10862 жыл бұрын
This explained IEEE754 in 20 min much better than weeks in my college class... nice
@Jono.2 жыл бұрын
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!
@Manusmusic3 жыл бұрын
"You might already see where this is going". No, no I do not.
@pleasecontactme42743 жыл бұрын
lol same feeling
@skorlupkaskorlupkovich24153 жыл бұрын
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
@_xiper3 жыл бұрын
No, I don't think I will.
@achtsekundenfurz78763 жыл бұрын
> "You might already see where this is going" "Yeah, same direction as the original vector, but at a different speed"
@schifty18093 жыл бұрын
I have a master's degree in CS and I was not seeing where he was going.
@dino28083 жыл бұрын
The WTF step made my day The approximation of the log of a float to its own binary representation is amazing
@redguard1283 жыл бұрын
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.
@deedewald17073 жыл бұрын
@@redguard128 Measures twice cuts once is one's process !
@deedewald17073 жыл бұрын
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.knowmysteelo2 жыл бұрын
Ironically, this is the best explanation of IEEE 754 I've ever seen.
@Minitomate3 жыл бұрын
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_3 жыл бұрын
the IEEE float explanation is so damn good
@AncientYaky2 жыл бұрын
This was fun to watch right after my FE exam, great video! Explained really well, especially for someone burnt out
@empressredbird2 жыл бұрын
the fact that somebody came up with that shows such a good understanding of math and software workings
@thomasburette91293 жыл бұрын
The almighty youtube recommendation algorithm brought me to this video. Nemean : I cannot overstate how good this video is. Please make more of this!
@tobyfitzpatrick39143 жыл бұрын
I found a bug...."threehalfs" should actually be spelt "threehalves"
@mastermati7733 жыл бұрын
Commit accepted. You are now a contributor! Congratulations!
@benwest52933 жыл бұрын
"halfs" is a nonstandard plural of "half", but that doesn't necessarily make it _incorrect_... After all, it's an acceptable Scrabble word 🤔
@garethevans97893 жыл бұрын
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.🙄
@akhilesh60723 жыл бұрын
@@garethevans9789 Agree, camel case
@Kyrelel3 жыл бұрын
@@akhilesh6072 *CAML
@matwilcoxson28492 ай бұрын
It's remarkable how clearly you were able to explain this extreme algorithm. Please continue to teach us!
@bombardygamer42482 жыл бұрын
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.
@sammyfromsydney3 жыл бұрын
Code review: Missing about a dozen comments.
@farhanyousaf56163 жыл бұрын
Please re-write, not readable code. And use math.h, and please, add faster processors to get the same speed. PR sent back. :)
@KnishG3 жыл бұрын
@@farhanyousaf5616 lmao it hurts
@metalpachuramon3 жыл бұрын
@@farhanyousaf5616 hahaha exactly my thoughts, they might've not gotten away with it nowadays. I feel like code reviews sometimes miss the point
@mapron13 жыл бұрын
@@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.
@agustinsida88773 жыл бұрын
@@mapron1 this is why no one likes you
@NomadUrpagi3 жыл бұрын
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.
@revimfadli46663 жыл бұрын
So like a robotics guy?
@NomadUrpagi3 жыл бұрын
@@revimfadli4666 general industrial process automation. That can include robotics, but rarely. I only look after 1 robot.
@NomadUrpagi3 жыл бұрын
@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.Leeroy3 жыл бұрын
@@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.
@fcw2bom3 жыл бұрын
@@revimfadli4666 if he wanted to say robotics he would've said that.
@___-._.-___4 ай бұрын
best explanation I have seen on IEEE-754 , I understood more in those 5 min than my prof's 1hr lecture
@wolcamophone47834 ай бұрын
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.
@hansangb3 жыл бұрын
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.
@Andre2997924582 жыл бұрын
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.
@JoffreyBion9 ай бұрын
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.
@vapeurdepisse2 жыл бұрын
Q III memories... Wow going way back! Golden era.
@Bhuyakasha3 жыл бұрын
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.3 жыл бұрын
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.
@Bhuyakasha3 жыл бұрын
@@Ruben_M. x is not a function of y here, so it just drops out of the equation there
@Ruben_M.3 жыл бұрын
@@Bhuyakasha Ah that makes sense I suppose, thanks for the clarification!
@deadlypoe5_7102 жыл бұрын
Excuse me, maybe I’m lost; But what the fuck is this?
@deadlypoe5_7102 жыл бұрын
I’m joking
@EnderFlop3 жыл бұрын
This video is actually incredible. I've seen this piece of code before and this explanation made it super clear and understandable. Amazing!
@windwatcher4602 жыл бұрын
Love it when the calculus is the trivial part. Thanks for the explanation
@brockobama2572 жыл бұрын
Literally watch this video every other month because it’s fascinating
@SecondQuantisation3 жыл бұрын
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.
@krishgarg28062 жыл бұрын
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”
@lightning26653 жыл бұрын
This guy explained the standard ieee 754 better than my professor
@silakanveli3 жыл бұрын
Sure. Professor just did not understand it himself.
@Lindaine3 жыл бұрын
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
@DaelinTV3 жыл бұрын
Lmao this guy is so confident in me 😭
@botlarry44373 жыл бұрын
He believes in your ability to understand. Do you?
@botlarry44373 жыл бұрын
@Victor Joseph Yeah me too. Snek language is fun :) Variable type? Whats that?
@ko-Daegu3 жыл бұрын
@@botlarry4437 wait you guys only did python never touched C or Assembly?
@botlarry44373 жыл бұрын
@@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-Daegu3 жыл бұрын
@@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
@tomkandy3 жыл бұрын
"Premature optimisation is the fast inverse square root of all evil" - Donald Knuth, probably
@minastaros3 жыл бұрын
@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.
@MichaelPohoreski3 жыл бұрын
@@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.
@nicholaswood32503 жыл бұрын
@@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.
@nicholaswood32503 жыл бұрын
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.
@MichaelPohoreski3 жыл бұрын
@@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.
@sidgar111 ай бұрын
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
@SUPERNOOB2011 ай бұрын
@@sidgar1 I see. Helpful insight, thank you for adding that up!
@SpritzMcSoda7 ай бұрын
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."
@rhettorical3 жыл бұрын
The fact that no one knows exactly who wrote the code is my favorite part of the whole situation.
@kurzackd3 жыл бұрын
Where is this said? It was John Carmack who wrote the code.
@Vizimech3 жыл бұрын
@@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.
@macaw20003 жыл бұрын
Almost certainly Michael Abrash. This is not Carmack-esque code.
@kurzackd3 жыл бұрын
@@macaw2000 ...source?
@macaw20003 жыл бұрын
@@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)
@Nature1120917773 жыл бұрын
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...
@khaoscero3 жыл бұрын
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.
@roberte29453 жыл бұрын
@@khaoscero That explains a lot of Unity trash that looks terrible and makes your graphics card hot enough to fry eggs.
@madezra643 жыл бұрын
@@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.
@snooks56073 жыл бұрын
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)
@naprava75223 жыл бұрын
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.
@RJNoe2 жыл бұрын
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
@Nemean2 жыл бұрын
Wikipedia claims that nobody actually knows how exactly they got their 0x5f3759df because, as you said, the other constant would be better.
@RJNoe2 жыл бұрын
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.
@teson20003 жыл бұрын
"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
@fye77853 жыл бұрын
"// What the fuck?" Killed me
@jimhalpert98033 жыл бұрын
I too like to cuss in code comments
@achtsekundenfurz78763 жыл бұрын
That's what I said at 06:09. Why does every math youtuber display at least ONE wrong example???
@ArnoldsKtm3 жыл бұрын
@@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