REVEALED: Quake III's SECRET Algorithm!

[@nathanmielke1977]

"If there's anything that Bill Gates taught me, it was never to name drop"... I laughed harder than I should've at that

[@DavesGarage]

I'm *really* hoping people took that as a joke and not a flex, but I don't know, it's pretty dry! ;-)

[@macaw2000]

@@DavesGarage perfect delivery

[@garisonhayne668]

@@DavesGarage If they don't like it, they can double click the thumbs down button... LOL .. You are comic gold.

[@WarrenGarabrandt]

@@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!

[@sp10sn]

A sublime moment.

[@WarriorRazor]

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.

[@munchlax633]

For most of this older games you can find communities that arrange matches

[@frankdux9254]

There are plenty people in Europe still playing Quakelive. Come join

[@alejandrocastro211]

Surprisingly openarena still has active players

[@FlyboyHelosim]

I'd argue Unreal Tournament is better.

[@aqualili]

Yeah quake live is where they all moved to

[@michaelafcadio]

"Abuses the compiler in ways I've never seen before." Classic!

[@n00blamer]

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

[@JeffJennings82]

thanks

[@rya3190]

...I should've kept up with my math classes, I could've figured that out on my own.

[@WimukthiBandara]

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.

[@migueeeelet]

Just some brute force testing perhaps? Just calculate which constant outputs the best results for a set of samples

[@migueeeelet]

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

[@migueeeelet]

@@steviesteveo1 Yeah, I can see that

[@achtsekundenfurz7876]

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.

[@hypercube33]

I've gotten mad and drunk at a problem and wrote stuff that worked great but I dont remember what I was thinking

[@geoffreyanderson2285]

I am good at math, and when I first saw that algorithm, I was completely floored. Cracking good stuff Dave!

[@DavesGarage]

Thanks! I'm not a math guy so hope I didn't embarrass myself too much!

[@BGBTech]

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

[@BGBTech]

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

[@DavesGarage]

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!

[@BGBTech]

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

[@Bobbias]

Oh man, of love to do something like that myself one day, but I've got other stuff going on.

[@firetip198]

We know we're on to something really big by the number of other people who step up to take credit for our work!

[@The_O]

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 :)

[@amorasaki]

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.

[@Cenot4ph]

it's not because of one single coding trick that's explained in this video

[@demukazz]

@@amorasaki mp_picnic 5 If I recall correctly, it converted everything to very primitive gpx, but added like 50 fps

[@mikemcgrumpy]

I’m a programmer, and I understood maybe 5% of everything Dave said. Yet I was still mesmerised by it all.

[@zeratul600]

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

[@asinzuar]

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

[@mikemcgrumpy]

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

[@asinzuar]

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

[@Aresous]

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

[@sryx]

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.

[@DavesGarage]

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!

[@emmanuelbeaucage4461]

1800 pages of pain

[@pseudocoder78]

@@emmanuelbeaucage4461 Imagine writing it.

[@Thros1]

@@DavesGarage imagine these brilliant people getting the same attention as say a "Kardashian" 🤣

[@ecarter2747]

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.

[@adamsfusion]

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.

[@Aggrofool]

I wonder if he's still in VR

[@momchilandonov]

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!

[@TheSzybas]

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.

[@Mrmaverickism]

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

[@willielast]

omg yes, red faction was doing something so unique

[@dangerouskoin4874]

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.

[@asddw4998]

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.

[@arthurarg2789]

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!

[@deedewald1707]

Excellent presentation !

[@Brahvim]

Ah! Thanks for reminding me what his name was.

[@0x6664]

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.

[@dpapa2175]

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.

[@VenturiLife]

Check out hashgraph DAG.

[@tralphstreet]

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.

[@mcgeufer]

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.

[@wadz668]

90% of all this goes over my head, yet I'm 100% intrigued by these videos.

[@jelleverest]

That fast inverse square root is a gem of an algorithm! Also, happy birthday!

[@baumstamp5989]

i wonder if there are more "hidden" algorithms that will one day be found to simplify complex instructions

[@NymezWoW]

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

[@snyggmikael]

@@NymezWoW ?

[@perplexedmoth]

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

[@incubuz1980]

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 :)

[@DavesGarage]

Awesome! If it was an allowed device and you solved it, I call that a win!

[@angrybirds2472]

@@DavesGarage&& @incubuz1980 TI BASIC!

[@Codeaholic1]

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.

[@DavesGarage]

Thanks!

[@soulGrafitti]

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.

[@shawno66]

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.

[@rj_chap]

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

[@KirillGorelov81]

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.

[@AdobadoFantastico]

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! 🎊🥳🍰

[@Jackarius86]

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!

[@KennethSorling]

Happy Birthday! Be advised that many causual viewers might confuse the title with "The Dreaded Algorithm", which is KZbinr parlance for KZbin'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.

[@DavesGarage]

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 KZbin audience... I guess we will see!

[@LaZZeYT]

@@DavesGarage That was the first thing I thought of before seeing the channel.

[@vvvci]

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

[@xniyana9956]

I've always found this story fascinating. The mysterious fast inverse square function in the Q3 code. Stuff of movies I tell you!

[@lucidmoses]

I think anyone that understands the floating point format can get there head around this algorithm. Creating it on the other hand.....

[@BlastinRope]

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

[@Karreth]

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.

[@definetlynotacomment1184]

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.

[@xxIONBOMBxx]

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

[@brunomazzei100]

Happy birthday, Dave! And thank you a lot for this excellent video!!

[@quincy1048]

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.

[@PemboPemberton]

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! ✌🏽😎

[@preciselyvague2912]

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.

[@Clank-j6w]

This is the most fun video discussing this algorithm I've seen so far. You're a great storyteller.

[@tomcombe4813]

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.

[@mezzanine510]

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!

[@beahydrated]

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

[@DFX2KX]

That moment when you understand just enough to look at that equation and go: That's some tomfoolery right there. It's brilliant.

[@Gummibri]

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.

[@hadireg]

😂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!

[@Carstuff111]

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

[@yiannos3009]

More like this please, LOVE numerical methods and related programming!

[@alefnull]

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.

[@UncleKennysPlace]

Proving that, in general, close enough is good enough.

[@deedewald1707]

Within 1 percent !

[@zachariahtrench7863]

It just works!

[@BlackHoleForge]

Hearing you talk about Newtonian approximation reminds me a lot about learning about sorting algorithms. How you make a guess, and then it reiterated to get a little closer, and a little closer, until it's just right.

[@MrBmxerFTW]

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

[@herrbonk3635]

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

[@Rasterizing]

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!

[@DanielLopez-up6os]

This Algorithm is what game making is about, achieveing levels of speed that are almost indistinguishable from magic.

[@Agret]

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.

[@Maadhawk]

I got to meet John Carmack at one of Id's Quakecon's back in the early 2010s. Guy's brilliance was just overwhelming.

[@Komeuppance]

Enjoyed the intro build up, set the stage very well... especially the name dropping lol Happy Bday!

[@DavesGarage]

Thank you! 😁. I hope everyone gets that was a joke!

[@Deemo_codes]

@@DavesGarage It did take me a minute to get it. But it made me chuckle for an unreasonble amount of time when it clicked

[@Komeuppance]

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

[@endermwatts]

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.

[@juanma9511]

Perfect ending !! i was wondering why it was too short, he got me

[@rjonboy7608]

Your story reminds me of 1979 when I was in Junior High School and my "Santa Claws" found me a Texas Instruments TI-99 4A computer instead of the Trash 80 I wanted. It was cheap enough that it "came" with 9 cartridges. 6 games, a typing tutor, an Advanced Basic, and Assembly Language. Some other family had it for awhile but I didn't care. First program I wrote was a bat and ball thing that became ping pong and tennis and brick breaking and all sorts of variations. Had to record them on cassette tapes because floppy drives cost more than the whole kit and kept getting interrupted because my brother wanted to watch shows on the TV because there wasn't a monitor. By summer I had that puppy doing everything but making breakfast. Using Assembly I could access hardware directly like you were describing about accessing pixel vectors on the raster lines which greatly improved both graphics and frames. Too bad they didn't release a TI 1982 model cross with the 286 and the NES architecture.

[@Real28]

I remember getting Q3A when it came out and being in the Beta. It was definitely SUSPICIOUSLY fast.

[@piobu5357]

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.

[@felicksos160]

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.

[@Quaker763]

A note on the history here. This algorithm goes back as far as Gary Tarolli (of 3Dfx fame) while he was working at SGI. He says he got it off someone else, so it must've been floating (pun intended) around between graphics programmers at the time.

[@harshgandhi100]

Happy Birthday Sir🎉, That was quite a cliffhanger.😆

[@luisdanielmesa]

I first discovered the video from Nemean called "Fast Inverse Square Root", I go back to that from time to time... Let's see how good this video is, with a fresh set of eyes explaining everything...

[@HeavyD6600]

Thanks for these videos, Dave! They're great!

[@DavesGarage]

Glad you like them!

[@deus_ex_machina_]

Man this has got to be the only time I've subscribed based solely off an intro. Excellent storytelling!

[@mrlazda]

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

[@DavesGarage]

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!

[@peterfireflylund]

@@DavesGarage Come on, that was not an ambiguity. What you said was said very clearly and it was just as clearly wrong.

[@tursilion]

Very nice explanation... but what caught me the most was I also have a Sharp EL-5103S that I got from my grandmother for my first year of high school. That was in 1989 and I've only had to change the batteries once. It still works!

[@quesoestbonne]

I got mine sometime around 1978/9. Be wary of leaving it in the original the plastic wallet these days, the brown plastic on mine started to decompose last year leaching out sticky plasticiser all over the calculator. Messy to clean up and has fogged the disply.

[@johnsonlam]

Though my programming ability is only BASIC, sounds quiet fun to see the code.

[@microcolonel]

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.

[@CZghost]

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.

[@theresnobodyhere5474]

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.

[@GarrettInShadows]

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.

[@aronseptianto8142]

can i say, inventing the literal format for world's bulk of computation need is one hell of a legacy the kind you won't be remembered for, but the kind that will last

[@paulmichaelfreedman8334]

Still playing Quake III Arena nearly daily. Yes still, after 22 years. Your Bday? Congrats!

[@DavesGarage]

Wow, I wasn't sure if folks still play it but that's cool!

[@paulmichaelfreedman8334]

@@DavesGarage Not a whole lot of servers around anymore, but a few is enough :D

[@lobotomizedjellyfish2171]

@@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!

[@quadro1337]

@@lobotomizedjellyfish2171 yep UT99 is still alive, but u will probably end on a server full of chads, who will 360 headshot you midair ; D

[@andrewthomasfinney752]

I was using CAD in the late 80's, specifically AutoCAD and while watching this remembered that the PC's of that time were useless at running it unless there was a separate maths processor on board!

[@DavesGarage]

Yes! Back when it mattered if you had a 287 or whether it was an SX/DX chip!

[@KennethSorling]

"... a double thumbs-down." Hee hee. I see what you did there.

[@igorthelight]

You even could quadruple thumbs down for better effect! :-)

[@taiga1295]

I gave him a double thumbs down and a thumbs up too. That'll teach him!

[@deedewald1707]

@@taiga1295 Good Good Very Good !

[@billybollockhead5628]

The number of times I tried to teach vector math/normalization to students - and I always failed to get the entire room to understand it, I couldnt figure out a good way to keep it simple so everyone could understand how/why/etc.. But yet - you did it here brilliantly, If I was still teaching part time (for fun) I'd have totally have stolen this explanation :D And your Newton explanation was top notch too. (I doff my hat to you sir)

[@paulgray1318]

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.

[@Ferdam]

I think that with limitations, comes the creativity (to overcome them) It is pretty nice to see limitations as challanges sometimes.

[@Gunbudder]

i had just started programming when FISR started making the rounds. i will always have fond memories of it

[@Mattski_83]

"Give it the old double thumbs down" I found this way more funnier than it probably was.

[@dvandamme00]

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

[@jonasglanshed]

The FISR is another proof of what an absolute unit of a programmer John Carmack is.

[@litjellyfish]

Finally? Has not this been known for ages

[@piotrd.4850]

Well, these were golden years of Computer Science. People who went through thorough basics, unbriddled experimenting, had passion, imagination, fewer distractions and worked hard. They did demo scene intros, fought with debuggers, understood machine internals, knew assembly and architecture (which was possible back then...) and were constantly creatively pushing the envelope.

[@ToBeeOrNotToBeHoney]

You tease.... good stuff so far, brings back memories of coding in cad display drivers in assembly...

[@joshman1019]

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.

[@reeboothemad5514]

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!

[@dillonrobinson2179]

So much respect for the og programmers that built everything we take for granted today. I've tried learning simple visual script for gaming and it still hurts my brain.

[@marcosgazamanes6165]

Happy Birthday Dave! Thank you for sharing all this, it’s always fascinating!

[@ericmyrs]

When I saw the title of this video, I knew it could only be about the Fast Inverse Square Root. My favorite piece of absolute Deep Magic.

[@LoesserOf2Evils]

From Japan: デイヴさん、お誕生日、おめでとうございす！ /deivusan otanzyoubi omedetou gozaimasu/ Happy Birthday, Dave!

[@FluffyAnvil]

But why is this attributed to Mike Abrash who has absolutely nothing to do with this? This algorithm was invented by Greg Walsh in the 80s. Mike Abrash is a legend but give credit where credit's due.

[@SeanCMonahan]

Learning that IEEE-754 was invented by one person was pretty cool. I'm excited for part 2!

[@michelecarla598]

Don't think that was the case... Several people were involved and probably none of them payed by Microsoft (although I could be wrong on this last point). People tend to get carried away while telling stories.

[@PatrickAustin]

Happy Birthday Dave...thanks for the great videos!

[@DavesGarage]

Thanks 👍

[@garryiglesias4074]

Michael Abrash... One of the "code gods" of my Youth... The Zen of assembly language/code optimization,, was one of my fav. books with the Dragon one and "Computer Graphics" from Foley, Van Dam & Hughes. It was so fun to code in the 90s...

[@AirZeee]

I confess, I'm 45 years old, rarely use Math beyond the absolute basic in day to day life, so have at best a weak grip on much of this, but Dave, well you're such an engaging host that I keep coming back for more! :D

[@natetolbert3671]

THIS is the side of programming I love. Whatever happened to blazing a trail? This is why I started and now the unknown no longer exists. Is this just me? Does anybody else ever get the feeling that trying something else (now it is less about algorithms and more about the abstractions and object models that lay above, but the addage still applies, imo) is just called "the wrong way."

[@Bdoserror]

@12:15 - I still have my EL-5103S too. Got me 3/5ths of the way through my Comp E degree before matrices became a big part of my work. Then I broke down and got an HP like everyone else, but the 42s instead of the 41C that everyone else had.

[@Diemermakes]

I just bumped in to the IEEE-754 spec today at work. How timely!

[@steveschwartz2814]

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.

[@m1kr0kosmos]

What a cool story. I have been studying this code for a while, but did not know about all of those books. I will definitely go buy them

[@xxIONBOMBxx]

This video will explain the fundamental beginning of the first person 3 dimensional video games we play and crave today. What a Lad

[@jamesgann560]

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!

[@niallrussell7184]

late to the party, but I remember Bresenham's algorithm (1962) used in games quite a bit, where maps were tiled - especially useful for calculating if one tile was in line of sight of another tile. I remember having to install a 287 co-pro to raytrace back then, and I'm sure they could have done more with Integers.

[@DerogativePeanut]

It's my birthday too! Happy Birthday Dave! What a leg end!

[@JohnnyAllsop]

This is why, despite my other gripes with Oculus, their standalone headsets work so well. They have both John and Michael on their team.

[@InfernalOd1n]

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.