REVEALED: The Quake III Secret Algorithm! Part 2

[@brucewilliams6292]

This was a lot of fun and I love hearing the history of these sort of things. There is so much of this history that will disappear in the coming decades that it needs to be gotten down while we can.

[@qpSubZeroqp]

I completely agree!

[@michaelandersen271]

I had the feeling to write a comment, only to find you had captured my thoughts exactly. Thanks! Have a like.

[@Milosz_Ostrow]

Along those lines, when I was in high school, I often wondered how Pythagoras came up with his theorem on right triangles. Well, he probably didn't, as clay tablets were discovered that suggest the Babylonians were using the theorem ca. 6,500 BC, over six millennia before Pythagoras, who probably learned of it in his travels. Where did the Babylonians learn it? It's a bottomless rabbit hole.

[@jwadaow]

@@Milosz_Ostrow there is some evidence it was used in Egypt I believe, for construction. A certain value of side lengths is referred to as 'Egyptian'.

[@FrankSelvaagPettersen]

news

[@TerjeMathisen]

Thanks for the mention Dave! I thought I had found an optimal way, inspired by Chebychev polynomials, to get higher precision with exactly the same performance: I optimized both the magic constant and the factor 0.5 used to calculate xhalf, and that gave me 1.15 extra bits of precision. However, last night I learned that Jan Kadlec did an even wider search, allowing all three constants to be optimized and he ended up with a factor of 2.7 improvement, i.e. 1.43 bits.

[@kindanyume]

ohh no you're like my friend "fluff" whom I think breathed ASM he literally could translate our custom Pascal to ASM like it was just breathing while chatting....it was scary how fast and accurate he was,,

[@-CmonMeow]

any results for 0x5f375a86 vs 0x5f3759df accuracy/speed?

[@TerjeMathisen]

@@-CmonMeow There's effectively no significant difference when you make marginal changes to the low bits of the magic constant. Since the code is the same, the performance is of course constant.

[@TerjeMathisen]

@@kindanyume That's actually quite easy, the hard/fun part is to realize while making the asm version that "there is a better way", i.e. that the algorithms should be tweaked to increase the performance, then after you've done that you go back to the HLL (typically C(++) these days) and see if it is possible to rewrite the code in such a way that it stays portable but the compiler(s) will now generate optimal machine code.

[@Baegus]

Jan Kadlec, as in Jan Rrřola Kadlec?

[@paco3447]

“Is something like an Amiga computer: way ahead of its time, but long, long ago” Nice to hear that reference. Viva Amiga!

[@kindanyume]

c64 ftw

[@darthcabs]

Haha the best sentence in the video

[@T3sl4]

And, like an Amiga against today's computers -- it might not perform as well anymore on modern machines (spoilers), but it's worth giving it a try on lower-powered embedded systems. On the off chance you need to do some quirky arithmetic on say, anything from STM32 to Raspberry Pi?

[@NeilRoy]

Agreed, loved my Amiga(s) and miss those days. People would often point out the Amiga's slower CPU speed to me back then, but what they didn't realize was that the Amiga didn't rely on the CPU and had independent processors for I/O, sound, graphics with separate memory for the CPU etc. You could literally create a program for the Amiga that didn't use the CPU at all. I still think that had it not fallen into the hands of Commodore, it could have went on to be the best computer in modern times.

[@matsv201]

@@T3sl4 one reason why amiga preformed that well was that the grapics adapter like consoles didnt use a ramdac but rather rendered the screen real time from instructions. This alowed large shift of grapics with a simple change in value from the cpu side. In theory mac would have been able to do the same thing, but they had a size limitation that amiga didnt have. Pc sort of kind of had this ability to. The issue with pc was that the sprite was fixed to a grid, making it look really ugly. There was some ways to hack around this that was used in dome bios implementation in the mid 90tys. In the late 90 Linux implemented a amiga like grapics in x-shell using 3d acceleratos, with Windows Vista that become a part of Windows as well. With sound amiga sound hardware worked pretty much the same as the grapics hardware, mixing files directly from memory, making it really cheap. While a 16 voice card in theory was far superior, becuase it was way more expensive, implementation was sparce. Ironically, pc cpu was at this point sifficently powerfull to emulate same kind of function, but was mostly not done due to lack of software. Than come ac97 for pc that was sort of a quasi software implementation that made soundcards dirt cheap.

[@romanpul]

I remember back in the day when both me and my brother were studying computer science at different universities, they covered this piece of code in their first semester and he showed it to me. I didn't believe him that this was a genuine piece of code, because back then it looked like total BS to me. A couple of years later (now at my masters degree) I came across it again and was blown away by the genius behind it.

[@DavesGarage]

Wow, impressed they'd have mentioned it in a computer science class, that's pretty cool actually!

[@romanpul]

@@DavesGarage Unfortunately I don‘t remember why they included it in the course. I believe it was to illustrate the exotic solutions it sometimes takes to optimize for a specific problem. And this is definitely one of the coolest and most exotic optimizations I‘m aware of.

[@cbuosi]

-Dave, just a tip: dont put the text/pictures in the botton of the video, there are some of us that are not english native that watch the videos with subtitles. Thanks.

[@AtreidaeChibiko]

I knew it's a nuisance but you can move the subtitle bar if needed.

[@AtreidaeChibiko]

Just click and drag it

[@almostinfamous42]

@@AtreidaeChibiko ok my youtube viewing just got a lot better thank you

[@zeratul600]

@@AtreidaeChibiko this has been my best day at youtube since I learned about ray william johnson when he was funny

[@cbuosi]

@@AtreidaeChibiko wow, tks

[@clairekholin6935]

With two's compliment, you can consider the "sign" bit of an 8-bit integer as a -128's place, which gives it a convinient mathematical meaning.

[@pazu8728]

This is a work of art combining maths, knowledge of how ALU works, and establish standards. These people are the earliest "hackers" in my book.

[@itwsntme]

This is one of the best explanations of FISR I've seen. Seen several other videos on the subject, and whilst what the code is doing has always been clear, why it works always went over my head. This one got be a bit closer, not that I can claim I understand now, but thanks Dave.

[@just_jimmy]

I really appreciate your contribution in computer science history. It's so amazing to hear out these kind of stories and the origins of such topics.

[@icorper]

I actually properly understand the floating point notation now it's finally clear in my head, Amazing stuff

[@DavesGarage]

Thanks! That was actually my hope, that I could make floating point understandable for people who previously didn't know how it worked!

[@Dong_Harvey]

@@DavesGarage yeah, you definitely broke me for a second, but the explanation and illustrations made sense in the end, Admittedly, though, I'd probably rewatch just to lock it in later

[@hagar2167]

I'm out and going to turn myself in.

[@seanys]

I’m not sure if enjoy your dry humour or amazing array of industry contacts more. Also, yay, Amiga!

[@Nebol]

It brings a tear to my eye that there are still people around who used and loved Amiga. I mean, of course there are... but it just seems so long ago now that I can get the lonely feeling that it's just me.... but then sometimes, like now, I'm reminded that no, most of us are still here. We're just older... but we still remember.

[@saulocpp]

And just in case you are curious, FISR is also slower than CUDA's __frsqrt functions.

[@DimitriMoreira]

I think given how obvious that is, nobody is curious about that.

[@DavesGarage]

I'm curious! I'm actually more curious about when frsqrt() functions came into the pipelines, and how new they have to be for it to be present?

[@DimitriMoreira]

@@DavesGarage there goes my faith in GPUs out of the window! You're actually curious about this?! Well, let's hear it from @Saulo Silva then.

[@whollymindless]

The drag race deepens...

[@DeanHorak]

GPUs aren’t all that fast on single operations. Their power comes from massive parallelization. Now, I suspect if you modified the algorithm such that instead of iterating over the rsqrt one at a time, you execute the rsqrt function over a large vector the rsqrts per second might be competitive - depending of course on the GPU in question.

[@onejdc]

This was the dorkiest and somehow best intro I've seen to a video in a long time. Thank you. Good content.

[@RoamingOdin0778]

Wow, the space cadet pinball sounds I had completely forgotten about that gem of a game. I loved it so much.

[@sparkyenergia]

Quake 3 was by far the most impressive thing I had ever seen in 1999 when it arrived. Always wondered what kind of witchcraft powered it.

[@jayd1687a]

Loved these two videos. It made me appreciate C all the more. The trick of going from float to long seems mystic at first but then makes complete sense when it clicks. I wish I had gotten farther into programming but at least I can live vicariously through these retrospectives.

[@nolan412]

Another good algorithm: Carmack's sprite scaling function.

[@alexloktionoff6833]

Is there a video about it?

[@nolan412]

@@alexloktionoff6833 Just a mention that it was generated on maybe Lex Fridman's podcast.

[@mikehensley78]

Loved the show! Computer/Software history stories are great, imo. Can't wait till you do another one.

[@Matmus]

Long time subscriber here. Dave your mix of knowledge and wit is brilliant. Hope you’re enjoying making it as we are watching it. All the best.

[@lassi4855]

Just wanted to say thank you for these kind of videos coming from someone with such a prestigious career. I'm a new software developer in beginning of his career who doesn't have much experience yet with low level and this sort of content (and the older assembly videos, even if assembly isn't super practical today) are hugely appreciated :) Keep up the good work!

[@NickyDee01]

As someone who taught themselves programming at 13 (about 30 years ago) without a strong math' background, I really appreciate this. I can read code all day and sometimes wish maths was taught using something like C. I think it would make it easier to grasp. More of this good stuff!!

[@memyselfishness]

As someone who studies math, I am glad you appreciate the C notation for the mathematics, but I barely understand a word of what's actually going on.

[@ScubaAnt72]

I'm and Engineer but struggled with maths from in high school integration onwards. If maths were taught with comments like coding is I think I wouldn't have lost my way maths-wise.

[@stolenlaptop]

I'm the same way I can read code all day but maths notation is sloppy to me, like reading roman numerals instead of just getting to the point you have to decipher the damn thing first.

[@Texas1FlyBoy]

I taught myself programming around the age of 16 (close to 50 years ago). This is cool stuff!

[@legion_prex3650]

@@ScubaAnt72 Hi, me too! I studied Computer Science and had always problems with Math, not all parts of math, but some. My brain works imperative, whereas maths works declarative. Math somehow isn't hard at all, its bad thaught.

[@dimasveliz6745]

Oh man, I hope that this KZbin effort you're making pays you off one day! This videos are great, informative and very interesting. Love from Barcelona, Spain 🇪🇸❤!

[@mmaranta785]

He doesn’t need the money

[@CRBarchager]

He is only in it for the subs and likes :)

[@Binxalot]

It's ridiculous that there are channels on KZbin with millions of subscribers showing videos of cakes and cookies being decorated, and here is a guy who built the code that made modern PCs possible and thus KZbin with less than 200k subscriptions..🙄

[@UmVtCg]

@@Binxalot There's a channel that unboxes toys for children. That tends to attract more viewers than watching a master programmer talk about his passion. Every kid loves presents and not every adult finds programming interesting. It's just common sense really.

[@vigilant_1934]

@@Binxalot Probably because more people like to bake or at least eat baked goodies than those who care about computer programing. Nothing wrong with that. Just watch what you enjoy and educate and/or entertain yourself as you see fit.

[@RBLevin]

Thanks for the effort you put into these videos. Clearly many weeks of research, writing, shooting, and editing. Great stuff and super educational and informative.

[@SpinStar1956]

Happy to see he got named 'The-Stack' seemed like such an natural corollary! Great Video!. And, keep the research on the history going; things need to get preserved before we all drop like flies...

[@turbo3922]

I loved The Stack. Great reference to The Stig from Top Gear

[@AlphasysNl]

When we all drop like flies, who do we preserve this for then? Aliens that come to see what the heck happened?

[@SpinStar1956]

@@AlphasysNl I was referring to all of us that are getting older, are the ones that know the history so that it can be passed on to succeeding generations. Just as historians are in a rush to interview soldiers of previous wars, so also we need to also preserve our technological history. There always comes a time, unfortunately after a lot of people have passed, the current generation gains a heightened interest in what actually went on but there’s nobody there to tell the story…

[@MrRobbyvent]

@@turbo3922 I had the same thought!

[@Jeff-ss6qt]

Documenting and writing your code clearly and correctly is also nice. There's a saying like you should write your software like if you have the looming threat of getting hit by a bus. So that other people (Most likely you) can understand it even some time later.

[@CodeJeffo]

I knew about the FISR and some of the tricks before. But I truly loved and enjoyed this video. The history & trivia behind are just excellent. Just wonderful, thank you for your time to put it all together also with benchmarks.

[@sean7899]

Thanks for another great video @Dave's Garage! And I have to throw a big thanks out to John Carmack for helping to push the industry forward back in the day by releasing source code to games still way ahead of their time.

[@joejoesoft]

A few months ago, I watched a somewhat long video explaining that had part that explained more about the what the magic number represents ("Fast Inverse Square Root - A Quake III Algorithm"). The video didn't do any historical digging, but it showed that when you convert from log(x)=-1/2*log(y) to a bit representation for log and reduced, you get the magic number (a scaling factor) and the shifted portion. It showed a bit more of the math that's over my head, but I'll trust that 3/2(2^23)(127-u) is the scaling factor the magic number represents.

[@tchiwam]

I did something similar in the late 90s when packing and packing float 32 in uint16 normalized from 0 to 1. I was able to save a lot of memory BW, packing and unpacking plus operations fast orders of magnitude faster and scalar became "free" when applied to the domain.

[@omegahaxors9-11]

The way Fast Inverse Square works seems to be an example of Applied Haxorian Chaos Theory. Essentially you take two or more fields and smash them together to gain an exponential increase of performance. In this case it uses the "magic number" as a static field to modify the dynamic field in a way that simulates a function. The information for encoding the Int -> Float -> Int is contained within that static field, serving as a form of instruction.

[@SW-tech]

Thanks Dave - these are better than TV broadcast quality! Great to explore the early days. Reminds me of the PDP-8 in my dad's lab back in the early 70s.

[@makethingsbetter]

I was so hooked into the history floating point I truly got disappointed that we did not find out. Always loved history, this video mixes both of my keen interests. Thank you Dave.

[@sammyfromsydney]

Part 2 was much better than part 1, but it's still difficult to follow in parts and I think there were some missed opportuntiies when it comes to a simple explanation of the math. For example in part 1 explaining the genius of Newton's method in using how much the function is changing (change of rate/derivative) to get closer to the root would have been cool. Ie the more than function is changing at that point the further you're going to go in approaching that root. My eyes widened when you said you were going to go into how changing the float to integer and back works and the origin of the magic constant, but ultimately I found it very hand wavy and not at all satisying. It's still a hell of a lot better than anything I could have put together and I'm impressed that you're able and willing to reach out to some of the people on the ground for the algorithm. Keep it up. Overall I really enjoy your channel.

[@sushantrocks]

If the result is monotonic for values < and > the magic constant. It is highly probable that someone took a known square root and brute forced to find the best value of the constant based on some small epsilon.

[@TerjeMathisen]

Exactly wrong: You search through all possible fp values between 1.0 and 4.0, finding the constant(s) that result in the smallest max relative error. In order to speed up the search you have to use a progressive approach, sampling the interval at 100-1000 different positions, pick those which show the worst error and do a more fine-grained search around each of them.

[@sushantrocks]

@@TerjeMathisen excellent optimization

[@IlhanNegis]

love the last second amiga ref. which raises the question, when we're going to see nerdy amiga content flowing?

[@PaulMJohnson]

Loved that video. Right until the kick in the guts reminding me that the Amiga lost!

[@DavesGarage]

You and me both!

[@BeheadedKamikaze]

It's OK, though - the Amiga already won my heart

[@SkippiiKai]

Not gonna talk about those Quake Comments, huh? ;) I first heard about this a year or so ago, and was just blown away at the genius of it. Your explanation of Newton's Method in the first video was one of the best ones I've heard - great job making it understandable. The only thing I wish you'd done in these videos was to use the algorithm to work out an example of the math by hand - that would really help to make it click and so we see what's really going on. Oh, and it would have been cool to show the constant in decimal numbers instead of hex, as hex doesn't mean much to some of us. But great job on the video - my favourite ones you've done so far.

[@DavesGarage]

I figured this guy already did a really good job of working the math, so I'd aim for a little more general audience. Check out his version! kzbin.info/www/bejne/pmnYkJ5oga6Nr9E&ab_channel=Nemean

[@collinkruger5476]

"If you look at the top right hand corner you'll see the most important number... 9" 😂 My wife and I are rolling.

[@TomasBlackAuthor]

A well produced and crafted video. I remember, back in the day, having to learn 2s complement calculation and FPA. But that's when I almost exclusively programmed in assembler! Many thanks for an interesting channel.

[@DavesGarage]

Glad it was helpful! I haven't actually worked out twos complement since college, but did it enough to know it works!

[@technowey]

Great video! Thanks for posting this. I'm going to share this with some former Digital Equipment Corporation employees to see if they can provide any insight into the PDP-8's floating point implementation.

[@skf957]

I now have an understanding of how FP works, so thanks for that. But, thanks also for this two-parter. The historical aspect is facinating.

[@markteague8889]

Another approach that can be used involves storing results in a lookup table within memory. This technique can be used when performing the computation (or calculation) takes longer than the memory accesses to lookup the value. I first encountered this technique when implementing code to store floating point values captured by an analog-to-digital converter employed by a lab instrument used in an electrical engineering lab. If my memory serves me, the integer and fractional portions of the digitized value were presented as separate/distinct binary values. On machines with clock speeds in the sub 100 Mhz range, it was quicker to lookup the conversion for the fractional values rather than to employ the CPU's floating point unit to perform the calculations.

[@sydneybiscuit]

The stack! I love it! 10/10 Dave. Thanks for the entertaining education - edutainment if you will

[@fusedtoast5367]

One of the few KZbinrs that doesn't annoy me. Great stuff.

[@rorychivers8769]

13:47 *scribbles while nodding* "Mmmh, Yes, nine, exactly"

[@BrianMarshall1]

A few years ago I was writing code for an 64 mhz ARM microcontroller and needed a loop time of about 20uS, but was struggling. I thought it was the loop constantly calling on input and output pins. Those did take up some time, but when I tested different parts of the code I had a few log calculations taking hundreds of cycles each to complete. Without knowing about the Quake III code I did something similar with a union holding a float and int value and multiplying the result. It probably wasn't the most elegant solution, but it got the calculations down to a few clock cycles and I felt pretty proud of my self.

[@Vagabundo74]

Recently found your channel so ive been catching up on your videos. I didnt think that I could love the channel more but then you hit me with a Top Gear reference!

[@Kalamatee]

I love your videos Dave - always informative. I also always get a warm feeling whenever you mention Amigas in your videos. I do wonder though, how they where viewed from within Microsoft during the time they where relevant? perhaps you can give us some insight into how it was viewed, and how it may have influenced Windows over the years?

[@mog068]

The ALMA radio telescope embedded computer for the 'front end' which is the first down-converter from sky frequencies (25 GHz to 970 GHz) to a slightly more manageable 4-12 GHz runs DataLight ROM DOS. It works fine for the most part. I maintain the C software which was originally developed by Dr. Andrea Vaccari. I was programming DOS from 1991 to 2005 and am doing so again now, having made several major revisions lately. We are thinking of moving to an embedded Linux + FPGA platform in the next few years bit have not started work. So, no graphics angle though I get it. But I love that you are putting this out there.

[@stephenbroderick7002]

I’d be interested in the RISC timing comparison for calculating FISR vs the CISC values you presented. Thanks for the video.

[@kuhljager2429]

Does RISC not have that command? I would think that even in a reduced instruction set, a math function this versatile would still be included

[@matsv201]

@@kuhljager2429 neither cisc or risc reallt exist any more. Risc does not sugest that the instruction them self is less complex, but rather the instruction set, more specifically the exicution time. Cpu like arm cortex have a fixed set for main instruction, and a set for floating points. This is not the same, making them non true risc. Most x64 cpu have a fix length for fpu making the fpu risc like. So a x64 and a arm can theoretically have the same fpu

[@benjaminolry5849]

So fun how a 2 decade old function can be used for a round trip through computer history spanning 6 decades and involving many icons. Thank you for both videos.

[@richardclarke376]

this is just awesome ! Thanks for doing it! I suspect this video is going to get millions of views in the future

[@DavesGarage]

That'd be sweet, but I'm not sure what one has to do for that to happen!

[@FilippoVitaleIT]

19:32 “The FISR is something like an Amiga computer: way ahead of its time, but long, long ago”

[@nightraven836]

thinking of old games just makes me remember Frontier: Elite II, and how it was somehow almost magically compressed to the size of a floppy disc yet fully playable without prior unpacking

[@gaslitgames]

14:00 Brilliant transition. I'll have to remember to steal that later.

[@mohammadarshad65]

4:30 Two's compliment can better be explained by saying that the MSB's place value is taken as negative. So in case of Eight bits you have place values 1,2,4,8,16,32,64, and -128.

[@landrec2]

Hi Dave, I've become addicted to your content, keep up the great work!

[@niczoom]

Interesting as always. Im interested in hearing from these 'chip' engineers!

[@jamiesandell4405]

Great stuff. Nice analogy with the Amiga to wrap up. :D

[@Albertovidanamanjarrez]

Friday night after hanging out with some friends at a bar and come home to see this video, it makes me feel weird in a good way. keep the good job Dave.

[@Pistoletjes]

Oh man, this is getting better each video.

[@chrisengland5523]

I'm not sure whether this algorithm is pure brilliance or an absolute nightmare. I'm retired now but in my early career days, I spent my time writing code in assembler and such 'clever' tricks that worked but that nobody could understand were highly frowned upon because when something went wrong (which was usually the case), nobody would ever be able to fathom out what was going on. Either way, the algorithm was extremely well explained in the video.

[@unknown50ct]

These videos are so densely packet with information, its almost like a program 👍

[@WastedDad]

Just found this channel and have been binge watching

[@ElNeroDiablo]

That bit intro'ing The Stack cracked me up being such a good homage to Top Gear's The Stig. XD

[@muddyexport5639]

An aside: REF. 1st episode. The calculator brute force method reminded of my time in the USN as a gunner's mate. We were taught how to bring the naval guns to target when the electronic range finders were knocked out. "Bracket and half". Put one over or under the target. If under add enough range to go over (reverse for over on the first) then divide the adjustment by 2 and fire again. Usually in 3 or 4 times after the initial bracket you were on target. With a high explosive shell you did not have to be pin point accurate. Just like horse shoes and hand grenades, with HE shells close is good enough. ;~)

[@willd4686]

I can't wait to have as many stories as you do!

[@wasitthat]

Love the nod to The Stig and all at Top Gear!

[@tamertakato]

I was looking for this comment xD!

[@leafylotus]

Love the top gear reference, thanks Dave I enjoy seeing the magic behind code, please do more reviews and explanations

[@vyzia]

Is The Stack a Top Gear reference? LMAO Loved the vid!

[@DavesGarage]

Yup :-)

[@rodbeaudry1660]

Dave you might be the smartest humble person I have ever watched on the tube

[@JakeGuilbo]

God this video is so cool. A large period on the mystery of FISR and whether it's even still relevant. Bravo!

[@armlessjohn666]

Charismatic, windows and a good programmer! Dave's the opposite of myself 😍

[@_pixelpicnic]

Dave, This is great! Thanks for a well researched history of this algorithm. It made for a great story!

[@teletesselator]

Nice.. The most interesting part of this video was the mention of the Amiga computer, and well worth a subscription... :)

[@fredericmokren9737]

Another great video Dave. If feels like you really walking us through the whole story. I especially enjoyed the side discussion on floating points.

[@thejolicious]

I toyed with using this in FPGA based image processing algorithm but in the end a really course approximation was adequate and saved me from building a 32 bit float module in Verilog which I wasn't keen on! Interesting to hear its history, thanks

[@zbnmth]

10:25 "...last time I counted..." - I approve so very much your humour.

[@alejmc]

The Stig now has some competition going on… The Stack. Great episode and actually quite happy to hear that hardware nowadays takes care of being the most efficient one by default to be honest.

[@chessprogramming591]

Sir, this was an amazing research! I've watched both parts without skipping. The way of floating points representation in regards to side effect of data types inter-transitions was incredibly insightful. Thank you for sharing all the historical reveals as well for it gives an extra weight to the mystery behind FISR! P.S. I feel very noob after watching your videos and sometimes wondering why did I actually start coding but anyway there's probably no better motivation to improve!

[@DavesGarage]

Glad it was helpful!

[@BennyR92]

I understood absolutely nothing what you explained and found it extremely interesting.

[@jharris947]

😂👍

[@slimebuck]

back in the day I had a trash computer, sales men ripped off my parents and sold them a trash can. 366 Mhz with 48 Megs of Ram, had a Voodoo 2 in it which I upgraded to Voodoo 3. My machine was under CPU and RAM minimum specs for QUAKE 3, but for some reason with that voodoo 3, quake 3 not only looked AMAZING, it RAN fast, and FLAWLESS on my machine. I was AMAZED back in the day at how good it ran, when I first installed it for the first time I was expecting a slide show, and I got the greatest gaming experience of my life, I love Quake 3, and I love ID Software and John Carmack for releasing the source code for it. Releasing their source codes was the biggest GIGA CHAD move anyone could have ever done. Any lesser companies would have horded it and the IP and rights to it like mad, but not, let everyone have it, what the hell, absolute legendary

[@StefanHolmes]

A fellow Amiga appreciator. A man of fine taste!

[@Jerhevon]

These are fascinating. I do love these approaches that take advantage of how a value is stored to achieve faster operations than doing it the "proper" way. Sort of like the way older code such as Formula Nibble did now verbotten things like self modifying code. Grab the bit value for a line (ala the bits for green) then store in your code 5 steps later. The code you then iterate on in a tight loop to paint that green bit pattern down 20 rows of the screen.

[@matt_b...]

The Stack .. I remember having an Intel Bunnyman back in the late 90s or early 2000s! Blast from the past.

[@firesoul453]

This youtube channel is refreshing!

[@KrisRatliff75]

And at 10:03... my brain exploded. Thank you for the awesome explanation of how to represent the floating point Dave. Couldn't follow to save my life, but great video on FISR regardless.

[@Gunbudder]

I love the history of fast inverse square root. i got some street cred at my first job by not only knowing about it and what it was for, but i also knew it only worked on 32 bit IEEE 754 floats (NOT doubles). i actually ended up using it for something not related to graphics at all. i didn't actually need the speed though, i just wanted to use it because of the history lol. now if only we could get a fast matrix multiply that doesn't suck...

[@danielfmyers]

This was helpful towards comprehending how my computer can process upwards of 40 channels of 48k audio and spit the mix out in milliseconds.

[@SimonBuchanNz]

CPUs laugh in the face of your puny thousands.

[@nickwallette6201]

This has nothing to do with that. This is just vector math useful for processing coordinates in a 3D space. What you're talking about is done by magic. Completely different principle.

[@ahrenmorris6053]

Love the history deep dives. It might be a little esoteric, but how about tracing the history of compilers. If memory serves there are some interesting chicken & egg problems in the early days where a compiler was written in asm, to provide an intermediate HLL, that would be used to write a compiler, that would define & compile the actual HLL the designer wanted. Thus creating the great circle of software.

[@MrRobbyvent]

this topic was covered on the computerphile channel by Professor Brailsford. Go check it.

[@NullStaticVoid]

Love the Top Gear reference. I'd suspected we were the same age, now I got confirmation.

[@willemvdk4886]

It would be very interesting to know exactly how the RSQRT function is implemented in modern day CPU's. Would it use the same sequence of steps and the magic constant?

[@TerjeMathisen]

It is almost certainly a lookup table, possibly combined with a very simple (shift & add type) polynomial. The state of the art is to return ~12 correct bits, so that a single NR gets you to

[@DavesGarage]

How big would the lookup table in the FPU have to be? Or put another way, how many points do you need for a reasonable first approximation in the LUT?

[@AndreasTeardrop]

Not too surprised Cleve Moler was involved in this sorcery . . .

[@TerjeMathisen]

Cleve is a nice guy, I worked with him on the FDIV sw workaround: He had all the contacts while I wrote most of the asm code. :-)

[@kurzackd]

4:56 -- he actually means *SUBTRACTING 1 (one)* , in the *MATHEMATICAL* sense. (but, in the BINARY sense, you ADD a 1 (one), yes...)

[@GeFeldz]

The FISR is just so impressive when it comes to performance, years before there were specific instructions in CPUs.

[@__--JY-Moe--__]

some super history that doesn't need forgotten/wasted!! gosh! I remember how I felt, when I discovered my 1998 modable activision video game. used a program, for all of it's texture work! that got me started learning code processes, instead of tedious texturing!!

[@alexandermaasland3494]

Thanks for the brilliant explanation Dave! I much enjoy these episodes :)

[@DavesGarage]

Glad you like them!

[@ronaldroe4548]

These intro set pieces are the best

[@orisphera]

4:52 Here's a way to describe two's complement I found: the highest bit's value is subtracted from the value instead of adding it (or, equivalently, is negative)

[@SimonBuchanNz]

I prefer: imagine that there is an implicit 1 just to the left for positive numbers. Now as you subtract 1 from a number, you are borrowing from the rightmost 1, but when you get to 0, the rightmost 1 is that off the left 1, so that goes to 0 and everything else is set to 1 for -1. The next step is to then realize that if you keep going this repeats, so it doesn't matter what's actually to the left, you can effectively "borrow from infinity". The only bit (ha) missing from this is detecting if any particular value is negative or not, but it's useful to understand that that is only ever a convention the way two's complement works: there's no difference between x and x + 2³² in many situations, and C in particular is quite happy to let you treat any signed value as unsigned or vice versa.

[@FelixBank]

The intro got be hooked! Great educational video!

[@justsomeperson5110]

LOL This two-parter is a perfect example of two things: First, how optimizations can utilize under-the-hood knowledge to do really wacky things that seemingly make no sense, but work much faster than the clear and understandable approach. Second, how important it is to add comments and make code self-documenting so that people years later can understand WTAF you're doing and why. ROFL Optimization is important, but the results are not always clear even when they work.