When the Quake III Arena source code was released to the world it contained a previously unknown algorithm called the Fast Inverse Square Root. This is the story of this strange algorithm and how it works as told by retired Microsoft software engineer Dave Plummer.
Thanks to viewer Brandon Pinske for the video topic suggestion!
For more info on the FISR:
A great video with better math explanations: • Fast Inverse Square Ro...
A surprisingly complete and detailed Wikipedia article: en.wikipedia.org/wiki/Fast_in...
Amazon Affiliate links for products mentioned in the video:
Zen of Code Optimization - amzn.to/2VO7ltx
Zen of Graphics Programming - amzn.to/3AxTAh9
Zen of Assembly [Out of Print] - amzn.to/2VD7Arn
Chapter Markers:
00:00 The Story
02:10 Welcome
03:25 Vectors
04:30 Normalization
05:48 Pythagoras Redux
07:50 Behold Code
09:10 Roots and Floats
10:21 Newton, Approximately
11:14 Rate of Change
13:02 C++ Code
14:15 Gates and Allen
15:04 Outtakes and Rarities
Errata: Please let me know in the comments of any important errors or omissions, and I will update things here. Currently, the only major update is at the end - I leave you with the impression that IEEE-754 might have been based on MBF, but I don't think that's the case. I will expand on this in Part 2, but recommend these two links for the curious:
• "The IEEE Standard 754: One for the History Books,"
www.computer.org/csdl/magazin...
• "An Interview with the Old Man of Floating-Point,"
people.eecs.berkeley.edu/~wkah...
"If there's anything that Bill Gates taught me, it was never to name drop"... I laughed harder than I should've at that
I'm *really* hoping people took that as a joke and not a flex, but I don't know, it's pretty dry! ;-)
@@DavesGarage perfect delivery
@@DavesGarage If they don't like it, they can double click the thumbs down button... LOL .. You are comic gold.
@@DavesGarage The first time I heard it, I didn't think anything of it, but then I thought "wait a minute..." On the second playthrough, I had to pause because I was laughing too hard to pay attention. Excellent delivery. Bravo!
A sublime moment.
Greatest arena shooter of all time, I miss Quake 3 so much, occasionally I'll launch it and browse the countless empty servers that were once full and shed a tear.
For most of this older games you can find communities that arrange matches
There are plenty people in Europe still playing Quakelive. Come join
Surprisingly openarena still has active players
I'd argue Unreal Tournament is better.
Yeah quake live is where they all moved to
"Abuses the compiler in ways I've never seen before." Classic!
I’m a programmer, and I understood maybe 5% of everything Dave said. Yet I was still mesmerised by it all.
it´s because the real magic here isn't the programming but the brilliant math behind it. I remember that back in university one of my professor's teams, worked with european university and they were doing some surface proccesing, and each run took many many hours to complete, the team was able to reduce the running time under 15 minutes, I don't remember exactly how much, but it was amazing, that with the right math, you can solve extremely complex things with waaaaaaaaaaaaaaaaaaaaaaay less code lines and computing
That’s not ideal, you should rewatch the video, read up on these topics and try and understand. Any decent programmer should be able to understand the FISR algorithm
@@asinzuar While I understand your point, and agree with it to a point, I have been programming for 20 years, and have built a number of commercially successful products. Not once in my entire career have I even needed to know what the acronym "FISR" stands for, let alone needed to understand the algorithm. I recognise I would never get hired by a FAANG, but I find the claim that one "should" understand this topic in order to be considered decent a bit of a stretch. I deeply admire the minds of those who do understand stuff like this though. Which is why I love watching this type of content.
@@mikemcgrumpy I didn’t mean that every programmer should know about FISR even before watching this video. Just that (apart from the details of Newtonian iteration) it should make sense to a programmer once you read about it. I just wish people would work at understanding these things instead of giving up at 5%. However I realise my comment was a bit snarky so apologies for that.
@@asinzuar not everyone is passionate about learning math from the ground up. I can solve higher complexity programming problems, but will get stumped on beginner ranked problems simply because it requires moderate algebra or basic calculus which I took no interest in during highschool. Not my fault the school I went to made math seem like an imagination driven, arbitrary mess of boring numbers with no real world functionality. Physics was fun despite not having any knowledge of calculus, got a trash grade because I hadn't taken calc, but they just make it so insufferable. feels like you're working towards nothing. If I knew the power of it back then as I do now, I would have taken all the math classes.
I did some digging and found that Cleve Moler (MATLAB) had a hand in deriving the constant used in the algorithm. It's funny that no one knows how exactly it was derived in the first place.
Just some brute force testing perhaps? Just calculate which constant outputs the best results for a set of samples
@@steviesteveo1 Well, since it's representable on a graph, you could simply plot a bunch of them at the same time and visually confirm & choose the best one. Repeat a few times, with slight modifications.
@@steviesteveo1 Yeah, I can see that
As I understand it, one could newton a near-optimal constant pretty easily, and then maybe try several similar constants on a test set of 0.255, 0.265, ... , 0.985, 0.995 (factors of 4 won't change the quality of the algorithm; input a value of 4 times X, and you get a result that's twice the result of X). Test-running the algorithm for 75 values and computing either the sum of squares of errors or the worst relative error used to be inexpensive back then; the average load was ~1000 calls per frame. After each test, you could randomly modify the value again, each time by a smaller amount, until the improvements are insignificant (or maybe until you fail to get any improvement at all for 10 iterations in a row). That's not a trivial workload, but in the QIII age, CPUs had built-in FPUs (so the exact square root isn't exactly SLOW either), and it can be automated easily (coded in ~15 minutes and run for a few seconds). However, the most important issue is to use higher quality comments than "What the 🍆?" -- a comment confirmed by the code snippet uploaded to Wikipedia.
I've gotten mad and drunk at a problem and wrote stuff that worked great but I dont remember what I was thinking
I have always wondered why QIII was THAT smooth back in a day when such smoothness for such quality seemed impossible still ... and now I know. Thanks, Dave :)
Yeah! Quake 3 was stunningly smooth for how good it looked. With games like Unreal I only cared that I could get it to run smooth enough to play. With Q3 suddenly it became a fun game to tweak hardware and settings to achieve buttery smoothness and insane FPS.
it's not because of one single coding trick that's explained in this video
@@amorasaki mp_picnic 5 If I recall correctly, it converted everything to very primitive gpx, but added like 50 fps
I am good at math, and when I first saw that algorithm, I was completely floored. Cracking good stuff Dave!
Thanks! I'm not a math guy so hope I didn't embarrass myself too much!
That fast inverse square root is a gem of an algorithm! Also, happy birthday!
i wonder if there are more "hidden" algorithms that will one day be found to simplify complex instructions
@@baumstamp5989 It didn‘t simplify anything. It‘s an approximation. It saved computation time at the cost of accuracy. And it‘s actually more complicated than calculating the actual square root. And by the way on modern CPUs it‘s not useful anymore.
@@NymezWoW ?
I guess "simplify" in this context means reducing the amount of steps to execute for the CPU (in terms of cycles). That said, these kind of algorithms have always been around, one of my favorite is CORDIC (a variant of which is used in the FPU hardware, I imagine) for approximating trigonometric functions. Obviously with the modern CPUs, these algorithms lose relevance (or delegated into the HDL space).
I have a small collection of Abrash's books and I even managed to get his Graphics Programming Black Book signed by Carmack. I had gone to Oculus Connect with the hope of getting Michael's autograph but he was never available. He is such a brilliant person, to be able to just walk down the hall and pick his brain must have been an amazing perk of working at Microsoft.
He's of course publicly more well known than most, but there were just SO many people there that were amazing resources. From Raymond Chen to Dave Cutler, the access to experts was incredible!
1800 pages of pain
@@emmanuelbeaucage4461 Imagine writing it.
@@DavesGarage imagine these brilliant people getting the same attention as say a "Kardashian" 🤣
Having been a hobbyist C/C++ graphics coder for almost 30 years, I naturally bought the GPBB shortly after it released, and - now well-used and falling apart - it still holds pride of place in my bookshelf today. Even now, much of the fundamentals of Quake tech is at the core of my self-written, raytracing-capable 3D graphics engine, which I'm literally still refining to this day. Not because I have to, but because it's still a fun thing to work on. Abrash's commentaries on everything from basic axioms (such as 'there is no such thing as the fastest code'), to the math and magic behind the Quake engine's inner workings (surface caching, VSD/HSR via BSP, span rendering) quickly changed me from a young buck thinking there were only limited ways of getting things done, to a much wiser man who is never afraid to try any optimisation idea no matter how crazy it seems. People generally hail the likes of Gates and Carmack in the computing industry... but for me, Abrash was always the hero of the day.
Spoiler: it's maths.. if you raise some number to negative exponent, it's same as 1/n^m... second part of the spoiler: dividing m (the exponent) by two is same as taking a square root... think about it, 2^8 for example is 256.. square root of 256 is 16.. which is 2^4, which is (2^(8/2)) and so forth.. floats are encoded as sign * mantissa * 2^exponent, where exponent is between -126 and +127 (some values are reserved for special use like Not-a-Number, Infinity and so on..). The (i >> 1) in the code shifts exponent bits right once, which is same as dividing by two.. which is same as square root, and the subtraction does negation so is doing the reciprocal. The WTF part is the magic constant which less people would stumble on their own (yours truly included).
thanks
This is awesome. I'm aware of the FISR and had always wondered whether anyone got some kind of answers as to its origin. Looking forward to the later episodes. This is my first time on this channel but I'll be sure to come back. Also Happy Birthday! 🎊🥳🍰
For what it is worth: I made a hobby CPU on an FPGA (custom ISA, I call it BJX2, essentially a VLIW with variable-length bundles). Its FPU only does FADD/FSUB/FMUL in hardware, so I use algorithms fairly similar to the FISR in the video for doing things like floating point divide and square-root in general (just typically with a few more Newton-Raphson stages for sake of accuracy). Basically works, was cheaper than doing it in hardware, and was speed competitive with my original attempt at a hardware FDIV/FSQRT module. (The HW also does format conversions; FP-compare ops are handled via the integer ALU).
@Brandon O'Connell Yeah, this sort of thing quickly turns into acronym soup... Also, this is sort of a "hard mode" project (have thrown several years at it, still unclear if it will be useful). Also wrote a C compiler for it (in parallel), and have ports of several old games (Doom, Quake, ...). Its SIMD capabilities and similar are also strong enough that it can semi-competently run software-rasterized OpenGL (it can also run GLQuake), ... Though, on the main FPGA I am using (an XC7A100T), I am limited to ~ 50MHz, and performance is quite limited by memory bandwidth (Quake is mostly limited to single-digit framerates).
That's really cool... I've only ever done FPGAs in college! I've never done the gate logic or microcode for a division, but I've written the 6502 ASM version, and that's pretty darned close I bet!
@@DavesGarage Yeah. My core doesn't use any microcode, and doesn't have a hardware integer divider either, so this is also done in software (in ASM, using the 'binary long division' algorithm). In some cases, I also use an approach based on using a lookup table of reciprocals (and multiply by fixed-point reciprocal), but this only "wins" in certain contexts (loses most of its advantage in the "general case"). Floating-point divide is a little nicer in that it turns into what is essentially a biased integer subtract followed by a few Newton-Raphson stages and some sign-bit twiddly and similar (also SIMD friendly, in premise). Note that in my case, the FPU uses GPRs, but the GPR space is relatively large (I am doing ALU, FPU, and 64/128-bit SIMD, all in a single register space; at present 64x 64-bit or 32x 128-bit; where the 128-bit registers exist as pairs of adjacent 64-bit registers). The single register space also avoids issues like needing a redundant set of memory load/store instructions, allows for some 128-bit ALU ops, ...
Oh man, of love to do something like that myself one day, but I've got other stuff going on.
We know we're on to something really big by the number of other people who step up to take credit for our work!
Dave is like, I'm not very good at Math, then goes into a detailed breakdown of newtonian logs....Kinda lost me at this point. But watched to the end, as it is really interesting anyway. I've never considered this approach to problem solving before...I can see its value. One area where such an approach might be useful is laying out DAGs. Btw - if anyone has a decent algorithm for that based on rectangles representing nodes, let me know.
Check out hashgraph DAG.
It pains me to say tho, that most of what he said is nothing more than basic linear algebra, and I still didn't get it.
Well, that's the Dunning-Krüger effect. People that are very competent in a field tend to underestimate their skills. While incompetent, people overestimate theirs. I guess it's mainly because incompetent people lack the information about a given topic, so they underestimate the complexity of it. Just have a look at a simple old-fashioned mechanical clock, seems pretty simple at the first glance, just a few gears driving 2-3 needles. But as you open it, you might find that it is a bit more complex than the outside gives away.
Michael Abrash is one of my heroes. Ever since I was a teenager reading his Zen books, I've looked up to him as some sort of wizard. It's been decades since then and his work still amazes me every time I stumble across it.
I wonder if he's still in VR
This is the most fun video discussing this algorithm I've seen so far. You're a great storyteller.
Happy Birthday! Even though I already saw a video in which FISR was explained in detail, I had to watch your take on it. The intro was captivating. You know how to tell a story. Damn! I think I have to rewatch your stuff about task manager now.
Happy birthday, Dave! And thank you a lot for this excellent video!!
Red Faction was also insane in terms of optimization. I recall playing it around 20 years ago on 300 Mhz CPU (most likely 233 Mhz real speed), 128 SDRAM and 16 MB of video memory or overall a very similar system and was amazed at how smooth it ran!
Oh yeah! Red Faction was precursor of massive terrain destruction in FPS games. Three of my most favourite shooters were Q3, Red Faction and AVP2.
moore's law meant that our understanding of building components outpaced our ability to fully utilizze those components and the mid 80's to the mid 2000's were the golden era of matching those two curves by the human mind alone. thats my theory anyway
omg yes, red faction was doing something so unique
Red Faction was amazing. It was my favorite shooter because it had vehicles. All my friends were diehard Quake or UT or even Tribes fans (Tribes was my second fav because of base defense). Cool to see other RF nerds talk about it like this.
The destructible terrain in Red Faction was really disappointing though, you only had to use it at most 3 or 4 times and then it's just forgotten about, and then the shooting and AI is really mediocre.
This algorithm is impressively optimal and great for learning about cs, floats and binary. If you want a bit of a deeper dive into the math behind it I recommend the video "fast inverse square root" by Nemean. Looking forward to the next video about it!
Excellent presentation !
Ah! Thanks for reminding me what his name was.
Very interesting, I have been programming for 20 years and it's the first time I see code using the Math I learned in school.
90% of all this goes over my head, yet I'm 100% intrigued by these videos.
More like this please, LOVE numerical methods and related programming!
😂nice intro Dave! besides, talking about optimizations, I was lucky enough during my uni years to have some applied maths to computers and studied functions iterative models where you decide on the precision and find the loop scheme function that gets to the precision in lower cycles. once you're a programmer and having that in mind, it changes the game!
Love this channel. Thanks for taking the time and sharing these stories.
I've gone over this code a few times, first from an old usenet post. Dave's explanation is one of the better ones I've seen, aside from the hand wavy don't worry about calculus.
Thanks!
Me too. First saw it a few years ago and thought it would be pretty easy to unravel. Hah! Keep coming back to it every now and then. Totally agree that Dave is the best explainer of what it is and does.
Happy Birthday! Be advised that many causual viewers might confuse the title with "The Dreaded Algorithm", which is KZheadr parlance for KZhead's increasingly arbitrary AI way of finding things to block, ban or demonetise videos based on a set of criteria which, by now, even they probably don't fully understand.
Thanks for the tip! Now that you mention it, I bet a LOT of people are going to assume that's what I mean, now that I think about it the context of a general KZhead audience... I guess we will see!
@@DavesGarage That was the first thing I thought of before seeing the channel.
KZhead's BLOCK, BAN, & DIE (= kill) algo is based on the satanic "global" elites desire to befuddle all brains by inverting reality, directing a constant 24/7 "two mins of hate" (at whatever designated enemy du jour) and thereby enforcing a strict "criticize your masters is a capitol offense" death cult, i.e. communism....
Love Nemean's video on the topic. Great to see you covering it!
I saw your short intro video for this and looked up the algorithm. And knew I had to wait for your explanation. And I was not disappointed. It was cool for you to explain your theory of where it might have come from even if Mike was not the source. Working around him must have been a treat. I had the opportunity to work with a guy in the early ninties when you called him for support he would debug your c/c++ code calling his library and tell you what you did Wrong over the phone without ever seeing your actual source code. Blew my mind. Turns out the guys first career was in theoretical physics.
Happy Birthday Sir🎉, That was quite a cliffhanger.😆
I just got back into working on graphics for my game - I wish I would have watched your video as a refresher on vectors instead of pulling out a graphics math book. This was great!
Happy Birthday :D Really been enjoying your content. Keep at it!
I read Michael's Zen of Graphics Programming when I was a school kid back in the 90's. I was truly fascinated by those algorithms and the way Michael optimized the code step by step, first in C and then in assembly. Those were the golden years.
have watched this video 3 times now, it just speaks to me! Q3A was so far ahead of its time in terms of graphical quality and performance, love it!
I remember reading a write up explaining (or trying to explain) how this algorithm worked shortly after the source code was released. While I didn't get it, it was a fascinating algorithm.
Happy Birthday. Love all the great content, one of my favorite channels.
Happy birthday! This is the second video I've seen about this algorithm, but I am enjoying your video much more. Cheers!
Awesome! Thank you!
The 3D wireframe vector graphics in the 80's games Mercenary & Elite, made me into a hardcore maths junkie from the age of 14. It stimulated my passion for maths, by wanting to know & learn how to do it myself & improve on it. So watching that talk-through was great, understandable & clearly presented. Maths got me into coding 3D vector graphics & also texture-map routines on the C64, Amiga & PC for major games companies.l during the late 80 & early 90's. Still loving mathematics - coding OpenGL, Vulcan & DirectX to this day. As well as many DSP routines on microcontrollers... - HAPPY BIRTHDAY, feller. ENJOY! ✌🏽😎
I wrote a solution to a problem in a math exam that no one else could solve, and the "show your work" part as a basic program source code for my Texas Instruments 82. My math-teacher gave me a fail on the question, but was later overruled as the TI-82 was an allowed tool on the exam :)
Awesome! If it was an allowed device and you solved it, I call that a win!
@@DavesGarage&& @incubuz1980 TI BASIC!
Happy Birthday Dave! Thank you for sharing all this, it’s always fascinating!
That's a great video Dave. Really enjoyed it. I used Newtons method so much in my degree. The one bit of the video I felt genuinely confident about understanding!
Thanks for these videos, Dave! They're great!
Glad you like them!
I've recently started to take programming a lot more seriously and i've really been enjoying the challenge of c++, your channel is exactly what I was looking for, thank you
C is no serious language though ;) rather an ugly 70s hack of the English BCPL, where they replaced the normal =, *and, or* with silly ==, &&, | |. C++ is basically just C with classes (that the Dane Bjarne Stroustrup took from the Norwegian 1960s language Simula).
learning CNC machining, I struggled so hard and now after being done with that a while, hearing the Vector speach really brings position into perspective when it comes to learning how to sequence tool paths, to physical positioning of said material in the machine pegged on that table. How neat
These videos strike a wonderful balance between enough verbosity to satisfy my curiosity, and enough handholding to walk me through new concepts Ty Dave, very cool
Proving that, in general, close enough is good enough.
Within 1 percent !
It just works!
Talking about Newton's method at 10:40 for finding square roots took me back to my high school calculus class around 1982. My math teacher was just a great guy and a great teacher but I remember thinking how odd it was to "start with a guess". I can see him standing in front of the chalkboard, going through the entire process by hand. I remember thinking that just couldn't be right. It seemed just so un math-like. But, here we are.
Happy birthday, Dave thanks for your terrific posts!
Happy Belated Birthday Dave! As a non-programmer your channel as well as Modern Vintage Gamer are 2 of my favorite channels. I know it's your birthday but I'm going to buy myself a gift. A Dave's Garage mug.
Enjoyed the intro build up, set the stage very well... especially the name dropping lol Happy Bday!
Thank you! 😁. I hope everyone gets that was a joke!
@@DavesGarage It did take me a minute to get it. But it made me chuckle for an unreasonble amount of time when it clicked
@@DavesGarage delivery was excellent, just my kind of humor that makes people pause, "Wait... what did he just say?" Also, your story of meeting Bill Gates, and correcting him, legitimizes the joke lol
Perfect ending !! i was wondering why it was too short, he got me
You tease.... good stuff so far, brings back memories of coding in cad display drivers in assembly...
Man this has got to be the only time I've subscribed based solely off an intro. Excellent storytelling!
I think anyone that understands the floating point format can get there head around this algorithm. Creating it on the other hand.....
It just takes some math fanatic who knew there is a certain power of 2 (2^128 iirc) that you can use for technomancer level bit manipulation
I've worked in InfoSec, specifically Incident Response, for nearly 10 years. Our team and teams like ours respond to clients when threat actors have broken into their network and caused problems (which is an understatement). A common example are ransomware cases. Throughout my entire IT tenure, I've commented on how I've never needed much math. I went up through Calc 2, maybe higher, I don't even remember. I read/write C/C++ and various scripting languages often. And yet I never really need anything more than modulus. Every once in a while, I remember that game programming is a different animal. This video has *proven* that to me! I'm going to share this with all my cohorts. We all think we're sooooo special... let's see how many of us can actually following along with this video :).
Besides the massive knowledge dumps (mind blown), I love the end reel bloopers.
Happy birthday and what a wonderful video, I've been hammering out code to solve some 3d world coordinate conversion from AI cameras (without frameworks), this has helped me understand what I'm doing and I'm please to say I can now convert coordinates back to 2d accurately enough. Your outtakes were fun too, if I'd recorded my outtakes in coding on this project it would be a 3 month long video!!
That moment when you understand just enough to look at that equation and go: That's some tomfoolery right there. It's brilliant.
I've always found this story fascinating. The mysterious fast inverse square function in the Q3 code. Stuff of movies I tell you!
Dunno how I stumbled across your channel, but this was interesting and as a bonus, you have a really pleasant voice! Keep it up :)
I can't wait for part 2. What a captivating story!
"... a double thumbs-down." Hee hee. I see what you did there.
You even could quadruple thumbs down for better effect! :-)
I gave him a double thumbs down and a thumbs up too. That'll teach him!
@@taiga1295 Good Good Very Good !
This Algorithm is what game making is about, achieveing levels of speed that are almost indistinguishable from magic.
That's what game making used to be about, now it's about rushing the product to market and cashing in on early access buyers and selling overpriced lootboxes. Who needs optimization? Just ship your 150GB game.
Thanks David. Love your story’s and explanation of random computer stuff.
i 100% appreciate the bit at the end where you directly address my thoughts as i was having them - "have you had that feeling yet? the one that says 'oh no, there's no way, he can't wrap this up in time" had me almost spit out my drink all over my laptop.
I remember getting Q3A when it came out and being in the Beta. It was definitely SUSPICIOUSLY fast.
I don't remember it being any faster than other games on the market at the time, personally. My very outdated P166MMX + Voodoo2 could handle Unreal Tournament (released within a month of Q3) with playable framerates, meanwhile I was getting single digit fps numbers in Q3 on small cramped maps, with everything set to low, and 0 bots. The game was so demanding that it was played almost exclusively with r_picmip 7 in cyber cafes at the time, which completely nuked any texture detail, but increased performance, and that was on much more powerful hardware than mine. You couldn't really get playable framerates in Q3 without at least a PII 300+mhz and a Riva TNT2, and even then we're looking more at a 30fps target @800x600 and mid settings.
Everyone struggled to get Q3 to run fast when it came out. People have false memories about it. It let you turn graphics far more down then other games, still you needed a good machine to run it with decent FPS. It was just played for such long times, that everyone remembers to run it with 125fps. On release noone played anything close to like that. Everyone struggled like with every other new game. It would not run on potatoes.
I personally think that the FISR algorithm that is present in Quake III Arena, is also present in Quake II and original Quake I. Those two games however do not have an open source code, id Software never released a source code for these two games. The reason why it is refered to as "the Quake 3 FISR algorithm" is because Quake III Arena was the only game of the series which source code has been released under GPL licence.
I remember going onto the id software ftp, and finding the quake 1 source, then compiling it and running quake. It's actually slightly newer than any official release.
The Quake engine source code was released under GPL on December 21, 1999 and is the basis of a great many source ports. Quake II source was released under GPL on December 22, 2001. Last time I checked (some years ago), I found nothing resembling the FISR in either codebases. Quake III Arena source was released under GPL on August 19, 2005.
just recently watched another video about this algorithm with a colleague and now u made one too. it's still fascinating and a true gem, probably forever. It would be really fun to see if someone was able to convert this code into such verbose code that anyone could understand it. probably a very hard challenge
MBF and IEEE754 are not same (different bit order). By the way second one was "invented" by Canadian scientist William Kahan (used by Intel in early 1970 in coprocessors before it was standard as IEEE754 much later).
I agree, not the same. Also differnt bias in the exponent I believe. What I should have said, and what I do say in the next part, is that IEEE-754 was the standardized replacement for MBF, *not* that MBF was standardized into IEEE-754... I never said that, but I might have given that impression in the rush to wrap up the end of the first episode! I will correct those ambiguities in Part 2, thanks for bringit it to my attention!
@@DavesGarage Come on, that was not an ambiguity. What you said was said very clearly and it was just as clearly wrong.
Still playing Quake III Arena nearly daily. Yes still, after 22 years. Your Bday? Congrats!
Wow, I wasn't sure if folks still play it but that's cool!
@@DavesGarage Not a whole lot of servers around anymore, but a few is enough :D
@@DavesGarage Same with the OG Unreal Tournament. I decided to load it up a few months ago and was shocked there was still a lot of servers out there and people playing it. I still suck bad at both UT and Q, but still have fun!
@@lobotomizedjellyfish2171 yep UT99 is still alive, but u will probably end on a server full of chads, who will 360 headshot you midair ; D
Happy Birthday! Really enjoy the channel!
Love this, when I was releasing q3Ownerz and Q3FU as a kid back in the day, I would find pieces of gold in the logic like this. Black boxes in the system that when analyzed had risk. This kind of history is very nostalgic! Thanks for the video.
Though my programming ability is only BASIC, sounds quiet fun to see the code.
"Give it the old double thumbs down" I found this way more funnier than it probably was.
This is a great video and cannot wait for part 2! I got confused at 13:11 because the derivative of sqrt(X) is not a half of the old value (the "put it in another way"). It clicked for me when I realized that to solve sqrt we can actually transform the problem. If y = sqrt(x) --> y² = x. Finding the zero of the latter function with Newton's method results in the formula you used :)
I love the explanation of Rate of Change - so well done! When you visualise it, then it's quite lovely - and amazing for the time!
The FISR is another proof of what an absolute unit of a programmer John Carmack is.
The algorithm - You point an int at a float, push some bits around, take the magic number out and Newton as a round, and that's what it's all about. Oh the coding hookey pokey. :). I find the best innervation comes when your pushed to optimise due to hardware limitations, all too easy today to add another core etc and be lazy.
I think that with limitations, comes the creativity (to overcome them) It is pretty nice to see limitations as challanges sometimes.
A video about coding. And about Quake. And Math. AND there is a second part! It doesn't get much better than that. :) Thank you and Happy Birthday!
Happy birthday! My favourite part of the code is where they comment out the second refinement lol. Some people miss the important part of this where negative normal magnitudes are essentially meaningless in this application, which is why they completely skip the sign.
This algo is a rock! Thanks for such a pleasant presentation!
Happy Birthday, Dave!! 🎉🎊
It's my birthday too! Happy Birthday Dave! What a leg end!
When I was in trig and Calc and such in high school I also created a program on my Ti80 or whatever the graphing calculators were back around 1996-2000. On the first test for quadratic equations my teacher was impressed that I understood it well enough and was able to make the program that he let me use it on that one test.
Yay! You did it (and Happy Birthday as well) :-)
Super cool content! Stumbled on this while actually playing Quake and having Visual Studio Code open lol. New sub from me dude!
I know this is a 2 year old video, and I am about to watch part 2 here shortly, but... You sir, have helped me understand more about ALL of this in this single video than I understood in my previous 40 years of life, total. Thank you for that. See, I struggle with different forms of math as a consequence of Spina Bifida. And in this one video you helped me understand things better than any previous teacher of mine. I am watching part 2 as soon as I finish the outtakes. :)
Hope for the next part soon!
Congratulations Dave! 🎉
Great video Dave My C++ is very weak but the math was incredible that it worked way back then.
This algorithm always reminded me of ramanujan's equations. He was an indian, maths prodogy who'd come up with these amazingly accurate (but still only approximate) equations with crazy constants that he'd never explain....they just worked, and that was good enough for him.
Happy Birthday! August 11 was my brother's birthday. he woulda been 38 this year :) thank you for your hard work on these videos. they are always well written and excellent presentation!
I think you said that MS binary format became IEEE 754. I have worked on floats in assembler for decades, and seem to recall the MS floats were NOT IEEE 754. You also mentioned that you worked on machines that lacked some basic arithmetic operations. I had similar experiences. I had to write multiplication code for one CPU, and taking a square root was an early project when the IBM PC was brand new. Those were fun days! You learned so much.
Ah this is a marvel of Engineering that comes back to me every once in a while. Thanks for making a long discriptive Video about what i painfully dwelled through a few years ago. I still dont claim to have understood it. But its beautiful nonetheless. Whenever the conversation about "There is no Art in Coding" pops up, i pull out this brilliant piece of engineering. Just Art.
Loved the "Vector" drop. First thing I thought of when he mentioned it
I can tell that most of the people gathered here really enjoy programming and the challenges that come with it. It takes a certain willingness to torture oneself and a willingness to learn constantly. People should really watch videos like this before they decide to go into game/game engine development or other math heavy concepts like machine learning. They need to understand what they might be getting into before they commit to paying for CS college classes. The same goes for any programming really... it can be a brain twisting journey sometimes. It's always great to have people like Dave who are willing to share their amazing experience with us.
Happy Birthday, Dave!
Congrats 🎉🎉🎉 Keep up the great work.
Quality channel, thanks for the content!
Happy Birthday Dave!!!
as a non-math programmer, I love the idea that (essentially) a loop that progressively gets closer to blowout is the fastest way to do a hard function. also, excellent instruction on how vector maths works with some code