It's crazy to think just what a modern computer might be capable of if we had the time and expertise to optimize code to this degree...
@ENCHANTMEN_5 ай бұрын
Where is that lost time going to? A big company can do it
@mariotheundying5 ай бұрын
modern CPUs actually have built in optimized instructions for exactly these types of things. For example, intel CPUs have an operation that does 8 inverse square root operations with perfect accuracy in just one clock cycle. These types of operations are called SIMD, and are majorly underutilized Edit: not quite perfect 2^-14 is the maximum accuracy they guarantee For a game though, that difference will be practically indistinguishable
@tonygamer43105 ай бұрын
Right? Game developers need to pay attention. We wouldn't have so many issues with modern games being unoptimized if they used more advanced optimization. Doom Eternal is a perfect example of that
@clouds-rb9xt5 ай бұрын
@@mariotheundying Layers and layers and layers of virtualization, security, memory safety, compatibility, APIs, threading, and more before you even get close to running instructions on the bare metal
@vesuvianprime5 ай бұрын
@@vesuvianprime a big company has all the time, all the people and all the money in the world for that, I'm talking about stuff like Microsoft
@mariotheundying5 ай бұрын
everyones gangsta till kaze finds an one cycle improvement in the most cracked function ever existing
@michi.785 ай бұрын
I'm kind of surprised it was made popular by Quake III. I could've sworn Mike Abrash put it in the original Quake, but it's been years since I saw the source.
@Sol_Rosenberg5 ай бұрын
i thought it was from doom before i made this video lmao
@KazeN645 ай бұрын
@@KazeN64 You accidentally still said Doom in one part of the video.
@arciks115 ай бұрын
ahhh shit, i thought i edited it out haha
@KazeN645 ай бұрын
@@KazeN64 Twice actually, lol. 5:00 and 8:30
@TheGershon5 ай бұрын
@@KazeN64 ah yes, DOOM with all of it's real time reflections and shading and floating point numbers that it definitely used. /s seriously though, i thought it was funny. because DOOM is pretty much always the first game people think of when IdSoftware is mentioned. so sometimes people think the FastInverseSqrt is also from DOOM, even though the game doesn't even use floats at all because they were way too slow at the time.
@proxy10355 ай бұрын
Silas' idea with the error cancelling is very cool, there are probably many other examples where we can reduce the error of one problem by dividing it into two sub-problems with opposite error
@ethanpayne41165 ай бұрын
This feels like reading a data book wrong every time with the wrong indicator Perfectly balanced as all this should be
@Sh1penfire5 ай бұрын
Error is a fickle issue. While I don't know for sure, usually these types of strategies have smaller error, in return they have larger error when values get extremely big or small.
@M0liusX5 ай бұрын
@@M0liusX I definitely believe that, there are usually very specific cases where one algorithm is better than another, and in general there is no "optimal" algorithm which always works best for all situations, it always depends on the specific example.
@ethanpayne41165 ай бұрын
We were doing this analogue style in the 1930s with balanced cables. Letting you run small voltages hundreds of feet with no interference.
@Creabsley5 ай бұрын
We use similar algoritms in land surveying to estimate coordinates with high accuracy. By using a GPS reading and comparing it to a GPS reading, at a control station, we can see which sattelites are visible in both readings. By subtracting the differences between the readings, the accuracy of the initial GPS reading goes from 5-10m(15-30feet) of accuracy, to 2-3cm(1-1.5inches) of accuracy. This only works when the same satelites are visible in both readings, if the control reading is to far away, then the algorithm wouldn't work. But this cancels out errors like the density of the atmosphere, refraction errors, and random errors, since you work with more data.
@sjurursteinholm53684 ай бұрын
2:00 So they gave it a race car engine and a can of beer for a gas tank?
@arciks115 ай бұрын
The gas tank's just fine, actually, especially with the Expansion Pak ... The problem is that the hose from the gas tank to the engine is the size of a curly straw.
@Nerdule5 ай бұрын
Cutting corners in the strangest of ways.
@benjaminoechsli19415 ай бұрын
yeah that's pretty much a good metric for why the n64 is slow lol
@RedstoNeman05 ай бұрын
Yeah, I remember some N64 dev from the time made a similar anology.
@someoneelse48115 ай бұрын
They started with designs used for SGI workstations and cut stuff waaay down. They were not going to make a new CPU design for the N64 and clocking it slower wouldn't have saved any money. It's not like today where we have ARM cores at every performance level you might want.
@ssl35465 ай бұрын
Nice video! Just one small point: If you want to use invsqrt(x) to calculate sqrt(x), you can use x*invsqrt(x) instead of 1/invsqrt(x). That might save a few cycles? But I still agree that the quake3 fast inverse square root algorithm is probably not that useful on N64.
@possible-realities5 ай бұрын
oh true, somehow i just forgot
@KazeN645 ай бұрын
to do regular sqrt you would just use a different magic constant. float fast_sqrt(float x) { int i = *(int *)&x; i = 0x1fbd1df5 + (i >> 1); return *(float *)&i; }
@nicholaswallingford36135 ай бұрын
If I understood that table correctly from the start of the video, does that imply that the 0 newton iteration would take 6 cycles to complete just the fast inverse portion? How long does * take, may deserve another video...
@andersama22155 ай бұрын
Did a little reading, it sounds as though hardware implementations of sqrt make have taken a few different routes, common ones apparently were a lookup table for rough approximation followed by a number of newton iterations, or alternatively some process similar to long division. Without digging too deeply, my guess is that might be why the cycle counts for division and sqrt are the same. Since long division's one of the slower approaches to dealing with floats, it could be that the fast inverse sqrt is the way to go, since the n64's hardware was developed before the algorithm was discovered it could be that its implementation could be beaten via software. Newton iterations roughly double the precision of the result so a better initial guess can rapidly decrease the time cost.
@andersama22155 ай бұрын
I like to think that whatever piece of his soul John Carmack lost when Oculus got acquired by FB/Meta ended up possessing Kaze
@603840Jrg5 ай бұрын
Is "now try it with the fast inverse sqrt" the programmer version of how every musician content creator is asked/forced to attempt Rush E and other meme songs
@TypingHazard5 ай бұрын
I didn't actually expect it to work at all. Because I remember you said that square roots on the N64 are relatively fast. Of course Kaze will find a way to eek out that tiny extra bit of performance and then some.
@mrmimeisfunny5 ай бұрын
you're forgetting this is the reverse sqrt not just sqrt
@Brad_Script3 ай бұрын
@@Brad_Script I didn't forget. I just thought that it's not worth it compared to the performance gains on old Pentiums.
@mrmimeisfunny3 ай бұрын
Both editions of the book Hacker's Delight mention the fast inverse square root (or as they call it, an Approximate Reciprocal Square Root Routine) and give various improvements of the algorithm. In the books they already mentioned FISR without Newton iterations: > deleting the Newton step results in a substantially faster function with a relative error within ±0.035, using a constant of 0x5F37642F.
@simjans76335 ай бұрын
All of your videos are so incredible. I love how you mix maths and humour in the way you do. Even if I can't comprehend everything, I love each and every second
@torvusbolt2015 ай бұрын
have you thought about writing some small research papers for these findings and experiments? like, even if they're extremely specific for your use case, they're still cool as hell and might even help someone some day
@RatcheT24975 ай бұрын
It's amazing to me how you can make deeply complex topics so easy to understand by explaining them based on a use case. Programming is like black magic to me, yet I can follow your videos along without any issue. God bless.
@HappyLittleBoozer5 ай бұрын
7:20 That poor shyguy....
@MR0KITTY5 ай бұрын
For the graph at 9:19, it probably would have been more clear if you'd labeled it as "Error (%) vs Cycles," since that's what the numbers actually represent. In both cases, a lower number is better, which is the inverse of what is implied by "Accuracy vs Performance" (which suggests that a higher value is more accurate or has higher performance).
@caliburnleaf93235 ай бұрын
The truth about why my dad never came back from the grocery store 😢😢😢 Edit: Yooo my mind was blown w/ Silas’s idea. Mathematically it seems obvious but getting that much accuracy improvement with the 2 fourth-root calcs multiplied together is insane! Thanks for the good content as always!
@Flamefreeze15 ай бұрын
don't worry, he's just building up speed for 12 years
@howisthis88495 ай бұрын
Wha
@thehedgehoggamer84715 ай бұрын
RAM Bus is my favorite recurring character on this show, glad to see Them back!
@cozmictwinkie92605 ай бұрын
I said I would watch this and I’m keeping my word. Thanks for taking the effort!
@Xtermo5 ай бұрын
Damn! optimizing the optimization! That's inception level of programming artistry. ❤ good job!
@NeoShameMan5 ай бұрын
Your videos are really fascinating to me. I don't have a background in computing science, but I do know mathematics and videogames. Appreciating your research! :)
@gravytraindrumming51675 ай бұрын
The inverse square root sure went through a journey, didn't it? From being cumbersome to calculate, to an ingenious bit hack, to becoming its own CPU instruction.
@DelayRGC5 ай бұрын
Another fun and educational video Kaze, thank you!
@ZintomV15 ай бұрын
Nice research, and interesting results. Bravo!
@Seamusoboyle5 ай бұрын
The amount of raw joy i felt when you said rambus goes vroom vroom
@hedgiehogdudeu_u4065 ай бұрын
I didn't know how much I missed hearing you say vroom vroom until now. lol
@linkfain15 ай бұрын
I forgot about making the RAMBUS go VROOM VROOM! I don't program stuff like this at all, but it is still always interesting to see your work.
@bobrossdahoss5 ай бұрын
The levels in the beginning of this video look really pretty! This is starting to look like one of the best Mario games ever designed... And it's a rom hack of Mario 64!
@supersmily58115 ай бұрын
I'm honestly impressed at the grind. In your shoes I would probably have ignored the FISR comments for being more pop comp sci than actual well-informed optimisation tech but good on you for actually investigating it and finding a place it excels even on a chip with hardware floats
@scoreunder5 ай бұрын
Not sure why hardware floats matter for FISR. Quake III was written for Pentium processors, all of which have hardware floats.
@jimmyhirr57734 ай бұрын
babe wake up, Kaze just uploaded a new video
@notarandom75 ай бұрын
Kaze Emanuar: The only person that can explain to me how to optimise a 26 year old game in high technical detail I can't even begin to understand, while keeping me invested until the end.
@SilicatYT5 ай бұрын
i used to watch your videos
@cubedude86905 ай бұрын
Every time you you upload I get amazed. Just hoping to play the mod at some point too.
@VideoGameBoxReviews5 ай бұрын
Kaze's coding gives me the feeling of when the Vtech kicks in
@pockpock63825 ай бұрын
Hi Kaze, love your coding tech video but, frankly, I almost don't understand them, surely you are very talented indeed. One simple question: what do you think about Saturn processing power? The SCU 48-bit DSP inside SS can actually be helpful in matrix transformation aside from the sual indipendet 32bit CPUs?
@slashrose32875 ай бұрын
Damn, Kaze's take on fast inverse square root is really interesting.
@leroymilo5 ай бұрын
you're amazing thank you for making this
@Meleeman0115 ай бұрын
great vid as always!! negligible (3:36) should be pronounced like "neg-*lij*-able", whereas you said "neg-li-able". again amazing work!!
@Heavenira5 ай бұрын
Love this. One of my favourite algorithms because it looks like magic from today's point of view, and apparently back then too, going by the comments. I don't know about you but I study IT at University and it's really funny to me how obvious the algorithm gets once you grasp the mathematical concepts behind it, and how floats are implemented.
@hummel63645 ай бұрын
I used to think there was no reason for a Mario 64 sequel to exist, but seeing how much there was to improve.on the base engine, and how many level possibilities it opens up, it's obvious they should have made one
@chungus11495 ай бұрын
This is beautiful. I've no idea what you're saying but it sounds great.
@gunnmetal1155 ай бұрын
this video is basically melatonin, with all the zelda songs and random math. I love it. good job
@VictorTaelin5 ай бұрын
I am always fascinated by your content, i'm too dumb to understand all the maths and algorithms involved in your work, but its insane what you achieved with N64. of course specially with Mario 64.
@DavidCoutinhoCG5 ай бұрын
I was certain it was absolutely "useless" in the Nintendo 64 hardware, I'm amazed you actually found a place to use it! Also, you know your audience very well, @06:58 I chuckled and @07:23 I almost laughed. Great content!
@prgnify5 ай бұрын
Really. N64 is not my platform, but if it was Gameboy code I might legit have paused the video to count the cycles.
@Gameboygenius5 ай бұрын
I know the project is aimed at maintaining real hardware compatibility, but maybe consider to patch a n64-emu and give one extra rambus to the console to see how far your game can go?
@wfzyx5 ай бұрын
It's been a minute since I did any programming, but this is super interesting stuff.
@BenjaminGlatt5 ай бұрын
love watching these videos
@snork_games5 ай бұрын
Amazing work.
@mantislazuli2 ай бұрын
Oh yeah. This makes complete sense. We need more compute stuff. I understand everything you said…… I still listened to the whole video.
@NunyaBitness-xq9ed5 ай бұрын
Hi Kaze, very cool video. i have a question about a mario 64 port for the playstation classic, it runs very well (60fps) but in under water scenes the framerate drops below 60fps. i watched you videos and question myself: is it possible to build a port for the playstation classsic with your enhanced version of the source code and will it reduce or completely remove the stutters ( framerate drops)?
@gamegear86135 ай бұрын
My best guess.. Some optimizations might be helpful but Kaze has made a lot of very N64 hardware specific improvements, and since the hardware is different, It's not at all certain they would work as well.
@Mireneye5 ай бұрын
Oh fuck yeah I am excited for this video. I really dig the deep dives on code optimization like Michael Abrash's Graphics Programming Black Book.
@etansivad5 ай бұрын
The game runs so smoothly its amazing, what do you think, could you afford a simple shadow map pass? Is the n64 buffer enough to hold a depth pass or two?
@pixboi4 ай бұрын
The maths sounded nice, but I can appreciate the music at the end from a technical standpoint. And it also sounds great lol - did you make it?
@thephoenixsystem67655 ай бұрын
when i was tutoring, i told students that there is a time and place to use the fast inverse square root. the place is on 32 bit windows PCs and the time was 1999. The trick only works for single precision IEEE 754 floats, and essentially any modern PC made after probably 2007 or so is so fast that the gains of the float hack aren't worth it lol. its important to teach though because i think it demystifies the IEEE 754 standard and helps students understand that its essentially just scientific notation but with 2 instead of 10 as your base. and if you go into embedded systems, you do need to understand how that stuff works because you will eventually need to convert a 754 float to a DEC float (or vice versa) and that has its own little hacks.
@Gunbudder5 ай бұрын
The same trick works for doubles too, but it needs a different magic constant (which has been listed on wikipedia) Otherwise, yeah, it's role is obsoleted by the dedicated reciprocal square root approximation instruction, where available.
@kitlith5 ай бұрын
these types of optimizations are fun on microcontrollers. they're kind of the final frontier of optimization shenanigans.
@Bp10334 ай бұрын
Wow, awesome analysis
@3rdGen-Media5 ай бұрын
I made my own using weighted quadratic beziers. It's only 4% less accurate than the sine and cosine operations using the squirt, at a fraction of the performans cost. I know it can be improved, but so far so good. :3c
@colonthree5 ай бұрын
I didn't even bat an eye at "squirt" the first time I read this comment because that's exactly how I say it in my head
@cubedude86905 ай бұрын
LETS GOOOOO ANOTHER N64 OPTIMIZATION VIDEO
@jakob_ch5 ай бұрын
Fast Inverse Square Root my beloved
@rose_allen5 ай бұрын
9:22 hey, don't need to call me out like that. i get it, its some cool math. i honestly had to do a double take when you mentioned 4th roots being multiplied by 2 magic number to cancel out each other's error. that kind of line up is nonsensically precise to land on, and tis just here now.
@Gameatronic90005 ай бұрын
Haha ^^ you and john carmack are my idols for me striving to get better at programming every day 😊
@skylo7065 ай бұрын
Great video!
@Pedritox09535 ай бұрын
Quake 3? I'm almost certain it was back in Quake 1. There was a discussion about whether it was Carmack or Mike Abrash, and turns it could have been Gary Tarolli at 3dfx? My memory of that era has long faded.
@d5kenn4 ай бұрын
that's jaw on the floor type stuff
@higherquality5 ай бұрын
I can't wait for the optimized robot uprising
@DessertArbiter5 ай бұрын
8:57 ooo, reminds me of Romberg integration (more generally Richardson extrapolation), add together approximations at different step sizes to cancel out one error term in the taylor expansion. Takes me back to intro to scientific computing :)
@johanngambolputty53515 ай бұрын
7:32 nice detail on the map
@igorgiuseppe18625 ай бұрын
Me (comp Sci grad but for enterprise software): "mhmm ahh yes I understand some of these words"
@megacherv5 ай бұрын
with all of your improvements, I bet you could make an N64 game engine for building anything. Not just Mario
@jmillart5 ай бұрын
Im using fixed-point so i kinda need the algorithmic versions, not the mantissa hack. Interested in researching these... In a few years, when i have time to spare this issue
@smokeydops5 ай бұрын
I don't know where your journey takes you, but the amount of data you took upon you, is painfully large. You are like a character from literature, the giver. In the story a certain character carries the memory of the world as it was. At this point it's safe to bet you are in the top 5 most knowledgeable n64 programming/development person in the world.
@m4r_art5 ай бұрын
He has the relative luxury of only concerning himself with one set of hardware (the N64) and one set of software (the relevant programming language(s)) for decades. Almost no (game) programmer out there enjoys this kind of laser focus. Instead it's 2-3 things at a time and every other year one thing is discarded and another thing added.
@forasago5 ай бұрын
You know, for as terrible as most everything in the world is right now, the fact that we have people like Kaze who is relentlessly optimizing Mario 64 and making great romhacks is a welcome ray of sunshine. Never stop buddy!
@unclerukmer5 ай бұрын
You don't need to do 1/fastinvsqrt or x*fastinvsqrt to get fastsqrt, you can use the exact same method, just instead of constant-(i>>1) use constant+(i>>1) (and of course the constant is different). You can use this method to calculate any nth power, the general formula is constant+i*n (which for -½ simplifies to constant-(i>>1)).
@vytah5 ай бұрын
oh shit that actually seems like a good idea
@cubedude86905 ай бұрын
Which mario mods are been shown? Some look stunning! I wannah try them
@startrekmodelmaker44575 ай бұрын
this is a great example of how optimization is a very specific problem that always requiring profiling before you can say something is gonna be a "good optimization"
@tompov2277 күн бұрын
At 1:30 you seem to be suggesting that the best way to get sqrt(x) from 1/sqrt(x) is to take the reciprocal via a division, but you could also just multiply by x since x/sqrt(x) = sqrt(x). I don't know if this changes anything you're saying.
@quelfth44135 ай бұрын
it does not
@cubedude86905 ай бұрын
what's crazy to me is that stuff like this proves geniuses are out there. I struggle writing methods in java ffs, I didn't understand a thing going on except that Kaze has an immense IQ
@Adrastus_5 ай бұрын
Keep at it and you'll get better. I don't know how long you've been programming, but I'm sure that Kaze has been doing it for a long time.
@jimmyhirr57734 ай бұрын
I just fucking died laughing after saying "YOOOO" outloud & IMMEDIATLY got called out for it by the video.
@vgahayden5 ай бұрын
1:30 I'm sure finv + div is more expensive than sqrt, but I am certain there is a way to make a finv-like function that only computes the square root without taking the reciprocal. That would be a fairer comparison in that part of the video.
@MasterHigure5 ай бұрын
I didn't understand a single thing in this video, but it was fun to watch!
@Netsuko5 ай бұрын
Will you release a optimation patch for Super Mario 64? Awesome content as usual 😊
@jonasskjtt55425 ай бұрын
Not only is your explanation easy to understand, you also are a chad innovator. 🍻
@RedBerylFTW5 ай бұрын
I wonder if you’ll ever do optimization for the n64 bios… I know Nintendo didn’t give very many developers access to the bios but there are a few games which load a different bios into the n64 and allow even more optimized code to be run for whatever game was developed…
@drewynucci90375 ай бұрын
You mean the RSP Microcode, and that's a whole different problem. I don't know how doucumented the microcode is. Nintendo certainly didn't want developers messing with it, and just use the ones they provided.
@watchm4kerКүн бұрын
rambus go vroomvroom
@Ghennesph3 ай бұрын
Can you explain what the accuracy loss is doing to the view matrix in that one clip? I don’t have enough information to spot the difference
@ar_xiv5 ай бұрын
Definitely at the end of the video a shocked Pikachu face for myself.
@XerShadowTail5 ай бұрын
are any of these optimizations or complete mods available already on a cartridge?
@evanpaulsmithfalconfogolin61475 ай бұрын
And don't forget, if the only reason you're using sqrt to normalize your vectors is for distance comparisons, you don't even need it at all.
@DrEnzyme5 ай бұрын
RAM BUS IS BACK. LET'S GOOOOOOOOOOOOO
@smileyzrevenge5 ай бұрын
Is there anyway to upgrade the ram's speed on a N64? I'm a bit curious just how much horsepower is locked away behind having 4 miners share one pickaxe.
@Alexaction2235 ай бұрын
The N64 uses a type of RAM called RDRAM. That's where you would need to start your search. There are faster versions of it that were made for PCs, but they were uncommon and the last ones were made around 2003. The PS2 also uses RDRAM, so that might be an easier source to find. After you find some RDRAM, you would need to find out how to make it work. The RDRAM is connected to the RCP, so you would need to find some way to speed up the RDRAM without affecting the RCP's timings.
@jimmyhirr57734 ай бұрын
Bro the inside of the factory looks soooooooo goood
@DragAmiot5 ай бұрын
Hmmmm. . . I didn't notice much documentation on the code you shared. Is there manual I can rtfm? 😘
@lunaumbra51795 ай бұрын
Could another use case be to compute 1/x, with the same idea of multiplying two estimates of 1/sqrt(x)? I don't know if inaccurate division is ever helpful though.
@johnnygodoy83294 ай бұрын
bro is just casually improving wikipedia algos
@bananaboyTS4 ай бұрын
Thank you for once again augmenting the collective knowledge of humanity.
@wgolyoko5 ай бұрын
The camera normalization makes it look like the camera guy is tipsy. Neat
@IndellableHatesHandles4 ай бұрын
Thank you for reminding everyone it also screws up the rendering temporarily! Most forget that
@Magikarp-yk7io5 ай бұрын
2:48 i've watched quite a vew of your videos but only now got ramBUS goea vroom vroom pun
@crusaderanimation69675 ай бұрын
Can anyone tell me which romhack is played at the beginning? Is it the upcoming Return to Yoshi's Island or something already public?
@NickJerrison5 ай бұрын
this is relevant to my interests.
@_ipsissimus_5 ай бұрын
Even though this is mostly specific to the N64 I'm going to save it to my game dev list anyway :) Maybe some day I'll find myself optimizing some code where this is useful and remember that it's in there
@livipup5 ай бұрын
Am I the only one who doesn’t understand most of this stuff? Yet I’m always excited to see them. And when I see “vroom” I get happy too
It's crazy to think just what a modern computer might be capable of if we had the time and expertise to optimize code to this degree...
Where is that lost time going to? A big company can do it
modern CPUs actually have built in optimized instructions for exactly these types of things. For example, intel CPUs have an operation that does 8 inverse square root operations with perfect accuracy in just one clock cycle. These types of operations are called SIMD, and are majorly underutilized Edit: not quite perfect 2^-14 is the maximum accuracy they guarantee For a game though, that difference will be practically indistinguishable
Right? Game developers need to pay attention. We wouldn't have so many issues with modern games being unoptimized if they used more advanced optimization. Doom Eternal is a perfect example of that
@@mariotheundying Layers and layers and layers of virtualization, security, memory safety, compatibility, APIs, threading, and more before you even get close to running instructions on the bare metal
@@vesuvianprime a big company has all the time, all the people and all the money in the world for that, I'm talking about stuff like Microsoft
everyones gangsta till kaze finds an one cycle improvement in the most cracked function ever existing
I'm kind of surprised it was made popular by Quake III. I could've sworn Mike Abrash put it in the original Quake, but it's been years since I saw the source.
i thought it was from doom before i made this video lmao
@@KazeN64 You accidentally still said Doom in one part of the video.
ahhh shit, i thought i edited it out haha
@@KazeN64 Twice actually, lol. 5:00 and 8:30
@@KazeN64 ah yes, DOOM with all of it's real time reflections and shading and floating point numbers that it definitely used. /s seriously though, i thought it was funny. because DOOM is pretty much always the first game people think of when IdSoftware is mentioned. so sometimes people think the FastInverseSqrt is also from DOOM, even though the game doesn't even use floats at all because they were way too slow at the time.
Silas' idea with the error cancelling is very cool, there are probably many other examples where we can reduce the error of one problem by dividing it into two sub-problems with opposite error
This feels like reading a data book wrong every time with the wrong indicator Perfectly balanced as all this should be
Error is a fickle issue. While I don't know for sure, usually these types of strategies have smaller error, in return they have larger error when values get extremely big or small.
@@M0liusX I definitely believe that, there are usually very specific cases where one algorithm is better than another, and in general there is no "optimal" algorithm which always works best for all situations, it always depends on the specific example.
We were doing this analogue style in the 1930s with balanced cables. Letting you run small voltages hundreds of feet with no interference.
We use similar algoritms in land surveying to estimate coordinates with high accuracy. By using a GPS reading and comparing it to a GPS reading, at a control station, we can see which sattelites are visible in both readings. By subtracting the differences between the readings, the accuracy of the initial GPS reading goes from 5-10m(15-30feet) of accuracy, to 2-3cm(1-1.5inches) of accuracy. This only works when the same satelites are visible in both readings, if the control reading is to far away, then the algorithm wouldn't work. But this cancels out errors like the density of the atmosphere, refraction errors, and random errors, since you work with more data.
2:00 So they gave it a race car engine and a can of beer for a gas tank?
The gas tank's just fine, actually, especially with the Expansion Pak ... The problem is that the hose from the gas tank to the engine is the size of a curly straw.
Cutting corners in the strangest of ways.
yeah that's pretty much a good metric for why the n64 is slow lol
Yeah, I remember some N64 dev from the time made a similar anology.
They started with designs used for SGI workstations and cut stuff waaay down. They were not going to make a new CPU design for the N64 and clocking it slower wouldn't have saved any money. It's not like today where we have ARM cores at every performance level you might want.
Nice video! Just one small point: If you want to use invsqrt(x) to calculate sqrt(x), you can use x*invsqrt(x) instead of 1/invsqrt(x). That might save a few cycles? But I still agree that the quake3 fast inverse square root algorithm is probably not that useful on N64.
oh true, somehow i just forgot
to do regular sqrt you would just use a different magic constant. float fast_sqrt(float x) { int i = *(int *)&x; i = 0x1fbd1df5 + (i >> 1); return *(float *)&i; }
If I understood that table correctly from the start of the video, does that imply that the 0 newton iteration would take 6 cycles to complete just the fast inverse portion? How long does * take, may deserve another video...
Did a little reading, it sounds as though hardware implementations of sqrt make have taken a few different routes, common ones apparently were a lookup table for rough approximation followed by a number of newton iterations, or alternatively some process similar to long division. Without digging too deeply, my guess is that might be why the cycle counts for division and sqrt are the same. Since long division's one of the slower approaches to dealing with floats, it could be that the fast inverse sqrt is the way to go, since the n64's hardware was developed before the algorithm was discovered it could be that its implementation could be beaten via software. Newton iterations roughly double the precision of the result so a better initial guess can rapidly decrease the time cost.
I like to think that whatever piece of his soul John Carmack lost when Oculus got acquired by FB/Meta ended up possessing Kaze
Is "now try it with the fast inverse sqrt" the programmer version of how every musician content creator is asked/forced to attempt Rush E and other meme songs
I didn't actually expect it to work at all. Because I remember you said that square roots on the N64 are relatively fast. Of course Kaze will find a way to eek out that tiny extra bit of performance and then some.
you're forgetting this is the reverse sqrt not just sqrt
@@Brad_Script I didn't forget. I just thought that it's not worth it compared to the performance gains on old Pentiums.
Both editions of the book Hacker's Delight mention the fast inverse square root (or as they call it, an Approximate Reciprocal Square Root Routine) and give various improvements of the algorithm. In the books they already mentioned FISR without Newton iterations: > deleting the Newton step results in a substantially faster function with a relative error within ±0.035, using a constant of 0x5F37642F.
All of your videos are so incredible. I love how you mix maths and humour in the way you do. Even if I can't comprehend everything, I love each and every second
have you thought about writing some small research papers for these findings and experiments? like, even if they're extremely specific for your use case, they're still cool as hell and might even help someone some day
It's amazing to me how you can make deeply complex topics so easy to understand by explaining them based on a use case. Programming is like black magic to me, yet I can follow your videos along without any issue. God bless.
7:20 That poor shyguy....
For the graph at 9:19, it probably would have been more clear if you'd labeled it as "Error (%) vs Cycles," since that's what the numbers actually represent. In both cases, a lower number is better, which is the inverse of what is implied by "Accuracy vs Performance" (which suggests that a higher value is more accurate or has higher performance).
The truth about why my dad never came back from the grocery store 😢😢😢 Edit: Yooo my mind was blown w/ Silas’s idea. Mathematically it seems obvious but getting that much accuracy improvement with the 2 fourth-root calcs multiplied together is insane! Thanks for the good content as always!
don't worry, he's just building up speed for 12 years
Wha
RAM Bus is my favorite recurring character on this show, glad to see Them back!
I said I would watch this and I’m keeping my word. Thanks for taking the effort!
Damn! optimizing the optimization! That's inception level of programming artistry. ❤ good job!
Your videos are really fascinating to me. I don't have a background in computing science, but I do know mathematics and videogames. Appreciating your research! :)
The inverse square root sure went through a journey, didn't it? From being cumbersome to calculate, to an ingenious bit hack, to becoming its own CPU instruction.
Another fun and educational video Kaze, thank you!
Nice research, and interesting results. Bravo!
The amount of raw joy i felt when you said rambus goes vroom vroom
I didn't know how much I missed hearing you say vroom vroom until now. lol
I forgot about making the RAMBUS go VROOM VROOM! I don't program stuff like this at all, but it is still always interesting to see your work.
The levels in the beginning of this video look really pretty! This is starting to look like one of the best Mario games ever designed... And it's a rom hack of Mario 64!
I'm honestly impressed at the grind. In your shoes I would probably have ignored the FISR comments for being more pop comp sci than actual well-informed optimisation tech but good on you for actually investigating it and finding a place it excels even on a chip with hardware floats
Not sure why hardware floats matter for FISR. Quake III was written for Pentium processors, all of which have hardware floats.
babe wake up, Kaze just uploaded a new video
Kaze Emanuar: The only person that can explain to me how to optimise a 26 year old game in high technical detail I can't even begin to understand, while keeping me invested until the end.
i used to watch your videos
Every time you you upload I get amazed. Just hoping to play the mod at some point too.
Kaze's coding gives me the feeling of when the Vtech kicks in
Hi Kaze, love your coding tech video but, frankly, I almost don't understand them, surely you are very talented indeed. One simple question: what do you think about Saturn processing power? The SCU 48-bit DSP inside SS can actually be helpful in matrix transformation aside from the sual indipendet 32bit CPUs?
Damn, Kaze's take on fast inverse square root is really interesting.
you're amazing thank you for making this
great vid as always!! negligible (3:36) should be pronounced like "neg-*lij*-able", whereas you said "neg-li-able". again amazing work!!
Love this. One of my favourite algorithms because it looks like magic from today's point of view, and apparently back then too, going by the comments. I don't know about you but I study IT at University and it's really funny to me how obvious the algorithm gets once you grasp the mathematical concepts behind it, and how floats are implemented.
I used to think there was no reason for a Mario 64 sequel to exist, but seeing how much there was to improve.on the base engine, and how many level possibilities it opens up, it's obvious they should have made one
This is beautiful. I've no idea what you're saying but it sounds great.
this video is basically melatonin, with all the zelda songs and random math. I love it. good job
I am always fascinated by your content, i'm too dumb to understand all the maths and algorithms involved in your work, but its insane what you achieved with N64. of course specially with Mario 64.
I was certain it was absolutely "useless" in the Nintendo 64 hardware, I'm amazed you actually found a place to use it! Also, you know your audience very well, @06:58 I chuckled and @07:23 I almost laughed. Great content!
Really. N64 is not my platform, but if it was Gameboy code I might legit have paused the video to count the cycles.
I know the project is aimed at maintaining real hardware compatibility, but maybe consider to patch a n64-emu and give one extra rambus to the console to see how far your game can go?
It's been a minute since I did any programming, but this is super interesting stuff.
love watching these videos
Amazing work.
Oh yeah. This makes complete sense. We need more compute stuff. I understand everything you said…… I still listened to the whole video.
Hi Kaze, very cool video. i have a question about a mario 64 port for the playstation classic, it runs very well (60fps) but in under water scenes the framerate drops below 60fps. i watched you videos and question myself: is it possible to build a port for the playstation classsic with your enhanced version of the source code and will it reduce or completely remove the stutters ( framerate drops)?
My best guess.. Some optimizations might be helpful but Kaze has made a lot of very N64 hardware specific improvements, and since the hardware is different, It's not at all certain they would work as well.
Oh fuck yeah I am excited for this video. I really dig the deep dives on code optimization like Michael Abrash's Graphics Programming Black Book.
The game runs so smoothly its amazing, what do you think, could you afford a simple shadow map pass? Is the n64 buffer enough to hold a depth pass or two?
The maths sounded nice, but I can appreciate the music at the end from a technical standpoint. And it also sounds great lol - did you make it?
when i was tutoring, i told students that there is a time and place to use the fast inverse square root. the place is on 32 bit windows PCs and the time was 1999. The trick only works for single precision IEEE 754 floats, and essentially any modern PC made after probably 2007 or so is so fast that the gains of the float hack aren't worth it lol. its important to teach though because i think it demystifies the IEEE 754 standard and helps students understand that its essentially just scientific notation but with 2 instead of 10 as your base. and if you go into embedded systems, you do need to understand how that stuff works because you will eventually need to convert a 754 float to a DEC float (or vice versa) and that has its own little hacks.
The same trick works for doubles too, but it needs a different magic constant (which has been listed on wikipedia) Otherwise, yeah, it's role is obsoleted by the dedicated reciprocal square root approximation instruction, where available.
these types of optimizations are fun on microcontrollers. they're kind of the final frontier of optimization shenanigans.
Wow, awesome analysis
I made my own using weighted quadratic beziers. It's only 4% less accurate than the sine and cosine operations using the squirt, at a fraction of the performans cost. I know it can be improved, but so far so good. :3c
I didn't even bat an eye at "squirt" the first time I read this comment because that's exactly how I say it in my head
LETS GOOOOO ANOTHER N64 OPTIMIZATION VIDEO
Fast Inverse Square Root my beloved
9:22 hey, don't need to call me out like that. i get it, its some cool math. i honestly had to do a double take when you mentioned 4th roots being multiplied by 2 magic number to cancel out each other's error. that kind of line up is nonsensically precise to land on, and tis just here now.
Haha ^^ you and john carmack are my idols for me striving to get better at programming every day 😊
Great video!
Quake 3? I'm almost certain it was back in Quake 1. There was a discussion about whether it was Carmack or Mike Abrash, and turns it could have been Gary Tarolli at 3dfx? My memory of that era has long faded.
that's jaw on the floor type stuff
I can't wait for the optimized robot uprising
8:57 ooo, reminds me of Romberg integration (more generally Richardson extrapolation), add together approximations at different step sizes to cancel out one error term in the taylor expansion. Takes me back to intro to scientific computing :)
7:32 nice detail on the map
Me (comp Sci grad but for enterprise software): "mhmm ahh yes I understand some of these words"
with all of your improvements, I bet you could make an N64 game engine for building anything. Not just Mario
Im using fixed-point so i kinda need the algorithmic versions, not the mantissa hack. Interested in researching these... In a few years, when i have time to spare this issue
I don't know where your journey takes you, but the amount of data you took upon you, is painfully large. You are like a character from literature, the giver. In the story a certain character carries the memory of the world as it was. At this point it's safe to bet you are in the top 5 most knowledgeable n64 programming/development person in the world.
He has the relative luxury of only concerning himself with one set of hardware (the N64) and one set of software (the relevant programming language(s)) for decades. Almost no (game) programmer out there enjoys this kind of laser focus. Instead it's 2-3 things at a time and every other year one thing is discarded and another thing added.
You know, for as terrible as most everything in the world is right now, the fact that we have people like Kaze who is relentlessly optimizing Mario 64 and making great romhacks is a welcome ray of sunshine. Never stop buddy!
You don't need to do 1/fastinvsqrt or x*fastinvsqrt to get fastsqrt, you can use the exact same method, just instead of constant-(i>>1) use constant+(i>>1) (and of course the constant is different). You can use this method to calculate any nth power, the general formula is constant+i*n (which for -½ simplifies to constant-(i>>1)).
oh shit that actually seems like a good idea
Which mario mods are been shown? Some look stunning! I wannah try them
this is a great example of how optimization is a very specific problem that always requiring profiling before you can say something is gonna be a "good optimization"
At 1:30 you seem to be suggesting that the best way to get sqrt(x) from 1/sqrt(x) is to take the reciprocal via a division, but you could also just multiply by x since x/sqrt(x) = sqrt(x). I don't know if this changes anything you're saying.
it does not
what's crazy to me is that stuff like this proves geniuses are out there. I struggle writing methods in java ffs, I didn't understand a thing going on except that Kaze has an immense IQ
Keep at it and you'll get better. I don't know how long you've been programming, but I'm sure that Kaze has been doing it for a long time.
I just fucking died laughing after saying "YOOOO" outloud & IMMEDIATLY got called out for it by the video.
1:30 I'm sure finv + div is more expensive than sqrt, but I am certain there is a way to make a finv-like function that only computes the square root without taking the reciprocal. That would be a fairer comparison in that part of the video.
I didn't understand a single thing in this video, but it was fun to watch!
Will you release a optimation patch for Super Mario 64? Awesome content as usual 😊
Not only is your explanation easy to understand, you also are a chad innovator. 🍻
I wonder if you’ll ever do optimization for the n64 bios… I know Nintendo didn’t give very many developers access to the bios but there are a few games which load a different bios into the n64 and allow even more optimized code to be run for whatever game was developed…
You mean the RSP Microcode, and that's a whole different problem. I don't know how doucumented the microcode is. Nintendo certainly didn't want developers messing with it, and just use the ones they provided.
rambus go vroomvroom
Can you explain what the accuracy loss is doing to the view matrix in that one clip? I don’t have enough information to spot the difference
Definitely at the end of the video a shocked Pikachu face for myself.
are any of these optimizations or complete mods available already on a cartridge?
And don't forget, if the only reason you're using sqrt to normalize your vectors is for distance comparisons, you don't even need it at all.
RAM BUS IS BACK. LET'S GOOOOOOOOOOOOO
Is there anyway to upgrade the ram's speed on a N64? I'm a bit curious just how much horsepower is locked away behind having 4 miners share one pickaxe.
The N64 uses a type of RAM called RDRAM. That's where you would need to start your search. There are faster versions of it that were made for PCs, but they were uncommon and the last ones were made around 2003. The PS2 also uses RDRAM, so that might be an easier source to find. After you find some RDRAM, you would need to find out how to make it work. The RDRAM is connected to the RCP, so you would need to find some way to speed up the RDRAM without affecting the RCP's timings.
Bro the inside of the factory looks soooooooo goood
Hmmmm. . . I didn't notice much documentation on the code you shared. Is there manual I can rtfm? 😘
Could another use case be to compute 1/x, with the same idea of multiplying two estimates of 1/sqrt(x)? I don't know if inaccurate division is ever helpful though.
bro is just casually improving wikipedia algos
Thank you for once again augmenting the collective knowledge of humanity.
The camera normalization makes it look like the camera guy is tipsy. Neat
Thank you for reminding everyone it also screws up the rendering temporarily! Most forget that
2:48 i've watched quite a vew of your videos but only now got ramBUS goea vroom vroom pun
Can anyone tell me which romhack is played at the beginning? Is it the upcoming Return to Yoshi's Island or something already public?
this is relevant to my interests.
Even though this is mostly specific to the N64 I'm going to save it to my game dev list anyway :) Maybe some day I'll find myself optimizing some code where this is useful and remember that it's in there
Am I the only one who doesn’t understand most of this stuff? Yet I’m always excited to see them. And when I see “vroom” I get happy too