The Folded Polynomial - N64 Optimization
Vložit
- čas přidán 13. 06. 2024
- It seems so obvious in hindsight, but somehow only one person thought of this...
Patreon: / kazestuff
Discord: / discord
Streams: / @kazeclips
🐦 / kazeemanuar
MERCH: kazemerch.myspreadshop.com/all
0:00 Intro
0:56 Chapter 1: Refresher
2:49 Chapter 2: Numerics
3:20 Chapter 3: The Square Root...
4:42 Chapter 4: The Folded Polynomial
(I quickly scrubbed the video several times and there was no chapter 5, I think he just saw the length between chapters 4 and 6 and assumed it was there)
10:29 Chapter 6: Other Ideas
12:23 Conclusion - Hry
Getting a lot of comments about making the code branchless - so let me explain why that's a bad idea:
A branch takes a single cycle on N64 and we have no branch prediction.
Doing bit manipulations on floats requires us to move the float from a float register to a general purpose register first, so that will always be a penalty of 2 cycles.
This means that just doing the conditions is WAY faster than doing bit manipulation on floats.
Lets compare a branchless version to a branchfull version:
if (shifter & 0x8000) {
cosx = -cosx;
}
Compiles to:
andi t0, a0, $8000
beq t0, r0, DontInvert
neg.s f0, f0
Dontinvert:
(3 cycles)
cosx = cosx ^ ((shifter&0x8000)
Dude I only vaguely understand half that math but I can tell you know your stuff. You literally put more effort and thought into fixing a 20 year old game then most triple A devs put into making theirs. Keep up the good work.
Kaze, my -2 braincells are gonna EXPLODE 💀💀
Instead of going branchless, try using only one branch with a switch statement jump table to distinguish the 8 cases up front. That should remove all of the bit tests and swaps and conditional branches at the cost of inlining the polynomial calculation 8 times. Code size would increase but not by much.
What song did you use for the background music in chapter 3? So familiar but I just can't remember the name
It's cool to see that branch delay slot get some work, another reminder why you can't always optimize the N64 like a modern processor
All math books should have the Mario font.
Super Maths 64
tht's wht i'm saying
Conversely, imagine a version of Mario 64 that uses LaTeX
Would make it more bearable
with subway surfers in the corner
"We run the computations first and THEN figure out which one we computed"
You know you're pushing against the limits of what's possible when your code starts implementing quantum mechanics
Finally... Quantum computing...
my brains hurts
If only they marketed the system as the Nintendo Quantum
They don't call it the Reality Coprocessor for nothing.
How did you escape your designated Gamemaker corner?
kaze on his way to save literally 0.000096 microseconds on a console thats 27 years old
Just you wait until you hear about Super Mario Bros. speedrunners
the benefit wasn’t even fps this time, the sine function is what makes the 3D math of the N64 and 3 dimensional games in general tick basically so physics, rendering and animation all benefit from improvements in accuracy
It's .096µs. The “.000096” is in seconds
@@jash21222n64 but it runs on an intel i12 12th gen
@@jess648So does that mean that he can do better animation or physics or something like that?
I really appreciate how open minded you are and how you give credit where credit is due and don't try to make people with "worse" ideas look bad. Keep up the good work!
I try my best to invite any type of discussion! I guess a confident demeanor in people is often associated with unwilling to change ones mind, which is an unfortunate vibe to give off. I wish more people would just come in and try to tell me where I'm wrong just so we can discuss and learn.
@@KazeN64You have every right to be confident based on your results. If someone else proposes a measurably better solution, of course it's time to upgrade, otherwise the right to be confident is gone :) Love that mindset, exactly mine too.
It's a good idea to not completely dismiss the "worse" ideas because sometimes these things are a two steps forward, on step back situation, and maybe that worse idea will become useful later with a little modification or refinement or in a different context.
@@KazeN64 The best way to create something great is to start out by trying something stupid and correcting why it went wrong.
Which is why it's important to have people willing to suggest , try and discuss anything that might seem worth giving a chance. It seems you understand that. ^ ^
Lol, extremely passive aggressive comment. Get over yourself with that toxic "all solutions are beautiful" mentality. Take some responsibility when you're in the wrong. No one is owed anything just because they tried (less hard than others at that).
Imagine being this math genius, code genius, retro gamer, nintendo enthusiast and also being buff. WTF with this dude, he is a demigod.
rumour is, that every time he find a new optimization, he does one push-up
@@MrBlakBunny
Dear god…
He is buff?
@@kurikuraconkuritasYep.
@@kurikuraconkuritas he's posted a lot of photographic evidence
In short:
- not actually faster
- _way_ more accurate
I'd say that's a decent trade-off.
Summarizing this video is a crime to this video
@@FloydMaxwell but it saves so many cycles
This stuff reminds me of when I was learning x86 programming and attempted to use my new-found powers to beat libc's sin/cos. After hand-writing an asm implementation of a 7th order taylor polynomial it was...2x slower and less accurate than libc's version. These videos might help in the future when I get into DS programming.
Isn't there an ASM instruction for that anyways?
@@kintustisx87 does indeed have sin and cos as instructions. I'm sure they were great back in 1995.
@@henke37 They are actually surprisingly bad. For unknown reasons, Intel only used a 66 bit approximation of Pi, so near multiples of Pi they are only correct to 1 significant figure instead of the 16 that they are supposed to reach.
@@oscarsmith3942 In real use cases that won't matter since the error inherent in rounding the near-pi value will be much larger than the error of fsin and fcos instructions
Kaze when he accidentally creates a movement of optimizing old games to the point they cannot lag:
Speaking it into existence!
Infinite frames per second
He might be the first person to finally remove frames from games entirely.
We now measure performance in "speed of light", as frames don't exist, and lag is only something the human brain can suffer from now....
The game is just a function of t
@@novarender_That's called a TAS
Kaze is slowly recreating the shipoftheseus problem in SM64 😂
Now that you say it...
At some point he could just swap out Mario and it’s not even the same game anymore
If we change all the parts, but it ends up sailing 15 nanoseconds faster, is it the same ship?
i get what you're saying. but the mechanics and genre of gameplay ain't changing at all.
@@AROAH he already did that, he replaced that mario with a brand new optimized mario
Oh, I remember! I'm so glad to hear a programmer that still cares about performance. Too often I've had coworkers do something in a disgustingly inefficient way because they just don't even think about it. I'll rewrite a query, or a function, or just flatten some nested loops, and suddenly it's 3 to 100 orders of magnitude faster (usually when someone is 1,000x slower they start reaching out for help, but that's about it)
I feel that! I have had coworkers complain to me that I do not need to optimize the code, but I just go ahead anyways since it usually does not take much longer. They end up liking the faster, optimized code much better (usually running real time instead of 1 frame a second LOL)
@@krystostheoverlord1261 there are dangers on both sides, but it largely boils down to personality types.
If you are a perfectionist that wants everything to run perfectly, then there is some use in pushing yourself to go faster and be less perfect (especially early on or during a proof of concept).
...but I think most people fall into the other category of people that want to write it once with whatever pops into their head first and then never revisit it as long as it technically provides accurate information.
Those people need to be pushed into taking a little more time to not just do the first thing but at least weigh a couple options. More importantly, they need to go back, actually test the speed, and do a round 2 specifically intended for optimizing, simplifying, commenting, and making the code more elegant (yes, I'm lumping all those sins together, but I realize some people can just have 1 or 2 of those problems)
I think you mean 3-100x slower? 100 orders of magnitude would be 1 followed by 100 zeros.
@@adamsoft7831 I do not mean 100 times slower. I mean 1000x slower to an incalculably slow but probably exaggerated 100 orders of magnitude (since we never knew how long it would take since it was essentially stuck, I gave it a fake artificial top number for emphasis).
They usually start asking for help around 1,000x slower, which was why I listed that, but there are literally processes that they tried to run, estimated it would take a few days, and then 3 months later the process still hadn't even hit 1% success.
I'm talking about *really* big data (many many petabytes).
Whereas if you cleverly divide and conquer, suddenly we can do the whole thing in less than 24 hours (I know, still slow, but we are talking about many Petabytes across about 300k servers)
My point was that many things were literally 100 times slower (2 orders of magnitude) and no one would care or ask for help. They would just deal with the fact that this tool only got run once or twice a year. There was a data sync tool that was running monthly, because it took a week or 2 to run. After I fixed it, it ran hourly (every now and then it would go over the hour mark, so it'd skip 1 cron sync. It was just a simple flock, but it hardly ever got triggered. Usually only after a batch update that touched a ton of datapoints all at once).
I'm not claiming I'm a genius either. The biggest problem is that a dev would literally try to run a script off their personal machine that would then loop through every server and try to do something.
Just by writing the script so it could run on the server itself and rsyncing it everywhere, that gives me a 300,000x boost because each server can do its own thing simultaneously (yes, I mean THAT dumb of mistakes)
Optimizing trig functions is great, but the fastest trig function is the one you never call. Have you taken the time to step back and see how many places where you can avoid entering degree/polar space, and instead simply stay in linear (vector/matrix/quaternion) space?
yeah, im planning to translate the whole game to quaternion animations for example. animation sin/cos calls are the bulk of this right now. unfortunately the entire engine and every behavior runs on euler angles so i dont want to refactor the actor rotation into quats if i can prevent it.
@@KazeN64(joke) you've already rewritten the entire source once, why not twice?
imagine if Nintendo discovered your rom hack in 1996, how shocked the devs would be
romhack takedown origin story
Forget dmca, they'd send a hitman his way
Prob would pay him money for the code or try to hire him, and also have him work on new consoles other than games
Yeah, it would prove backward time travel to be possible!
Maybe the original original Mario 64 ran at like 2 frames per second and ruined Nintendo's reputation and they went bankrupt. Then Kaze decades later and improved Mario 64 into what it is today and Nintendo's time travellers got ahold of it, took it back to 1996, published it and saved Nintendo. Now Kaze is basing his improvements off that version of Mario 64, the version he unknowingly wrote himself in a parallel reality, and any day now Nintendo's time travelling spies will bring it back to 1996 and Mario 64 will blow everyone's minds and Nintendo will bankrupt Sony because no one wants a Sony crapstation after they see Kaze's v2 Mario 64.
You have no idea how excited I am to play the original SM64 when you remake it with all the improvements. I have held off playing it for years all for this moment. I cannot wait!
I thought he said he wasn't releasing these fixes applied to the original game, just using it to make his sequel
@@danielpope6498nah, he said at one point that sometime in the future he is gonna backport the upgrades and patch's into the vanilla game with no custom levels, but that's probs still gonna be like 6 months after "Return to Yoshi's Island" is out, and there's no ETA on the hack
@@danielpope6498 not if we pressure him enough.
@@Tabu11211 Not trying to offend or anything but, most of us have witnessed what could happen if we "pressure" someone (or a company) to release or publish an app or game just cause we are impatient (looking at you Cyberpunk 2077, NoManSky... )
We all hate a buggy mess. With that said, I rather be the kind of viewer / customer to actually encourage developers and studios to take their time to make the app, game or whatever they are trying to develop so we the consumers get what we paid for.
Pressure will only fuel the crunch culture in Programming jobs (or any other field where this exists...) So no. I rather wait few more months.. HELL a YEAR, as long as final product is stable and efficient enough for us to enjoy.
Just my humble two cents.
Take care
@@bretayerstormreal shiz bruh
Schoolkid: "Nobody needs this math stuff in real life!"
Kaze: Entertainment is math, enjoy!
In an age where a modern basketball video game has over 100 gb of data you give me haven knowing people out there are developing formulas for specific hardware in order to save possibly a few milliseconds just for the sake of optimization. You're work is both amazing and humbling.
I wonder how much of that is optimisation for loading times in an era where read speeds often outstrip decompression speeds.
I want this rom hack so badly. The levels look so huge, and clean! You have ziplines! And workplace accidents!
I'm enjoying imagining an alternate universe in which commercial n64 games were this efficient
This. I'm trying to imagine Turok 2 could have actually worked now.
Do you plan to release a version of your optimised engine at some point, which can run the original Super Mario 64 ROM? It would make for a very interesting comparison.
of course, this mod will be open source after release.
Out of curiosity... when will this mod release? It's absolutely phenomenal.
@@Apostolinen it'll release when it's done ;)
I think you could use a double angle identity of cos here: cos(2x) = 2cos(x)^2 - 1. Compute cos in the interval [0, pi/4] via quadratic polynomial, then use the identity to expand to the interval [0, pi/2]. From there you get all values of cos via the usual symmetries. This might get rid of the square root, but I don't understand the details of the implementation.
That would be more efficient if you only need the cos. You'd still need the sqrt to get the sin though.
This folding technique is common in lots of numerical approximation. For example search for the golang error function (erf) implementation where only a short interval of the function is approximated and then things outside of that interval are shifted via erf() identities into the well-approximated region. I still think you can get better performance by avoiding sqrt() by using a different polynomial approximation for the second 8th of the curve. Once you have two 8ths you have a quarter of the curve and from there you can get the rest.
@@sonic-templeos When you divide a curve up into N pieces and then find a best-fit polynomial for each Nth you need the endpoints to match up with each other perfectly or you get noticeable discontinuities. As such, the end points aren't option, they must be fixed in the interpolation. Since I found a best-fit quadratic (defined uniquely by 3 points) that only leaves one free point to choose. I chose that point such that the average error (the difference in area between my polynomial and sine) was zero. I just used binary search to find the 3rd point that had this property.
Having followed this for years I am never ever EVER dissappointed when you upload. One of the only ongoing projects that just ROCK!
Even though I didn't understand the technical bits, I respect you immensly for you dedication to such old and limited hardware. Hopefully someone will recognize this hard work and give you the credit you deserve, whatever that may be.
It is no different than any other sport. Think about it, you set a limit and then try to better your skill by seeing how hard you can push it. Un target shooting you try to get as close as possible to the center of the target, in F1 racing you try to decrease your lap time, here you try to max your FPS. Using an N64 game is just a fun way to set the rules for the "competition" that he has a nostalgic connection too and forces him to think outside the box.
I will be playing the hell out of this ROMhack. I hope that is the kind of appreciation he is looking for (and a really good job, if he doesn't already have his dream job).
60% of this stuff goes over my head but I can't stop watching it super interesting and entertaining
Alright, you’re definitely going to be dipping deeper into advanced and/or theoretical mathematics going forwards with this project. Folded 4th order polynomials to approximate the sine and cosine graphs. You, and the community members who assisted, are mad geniuses.
The folded polynomial is genius!
I hope you can maintain a parallel release of original M64 patch that includes all your performance mods, this way the community will constantly referring to your channel if they want the most current on their M64 and the best performant build. The side effect is that it encourages more people to your channel and discover your incredible works, as well as knowing your new content
Yeah but then he’ll get struck by dmca
@@ruie.34nah he wouldnt, but its nice Kaze has a community so eager to defend him i guess 😅
@@kvdrrMany of his mods have been struck down.😢
My first thought was a piece-wise polynomial, possibly done with spline interpolation, but the folded polynomial is a cool idea.
How do you figure all this stuff out lmao. I am a full stack web dev but when I see stuff like this I’m just like I’m a fraud 😂
learn C, join the system side
you'll be angry at electron just like us!
i dont even know what electron is... :D
Lmaoo. I did learn some C in college and I actually loved it and was one of the few to do well 😂 and a little bit of assembly. It is def no easy task lmao. I’m tryna make a fullstack browser game actually. Got the prototype phase done of getting everything I need in place. But I just know imma run into optimization issues later. I always love watching videos like this to see how the pros do it 😭
Web devs sticking together 😤. In the same boat and feel just as fraudulent watching these optimization videos. One of these days I'll learn C or something
...
@@NoNameAtAll2 OP should learn HolyC instead, like a divine intellect individual would do.
I'd love to see you collaborate with James Lambert who's building Portal 64 to see what kind of performance gains he could potentially see with your optimizations.
Can't imagine they don't already watch each other's content
I have LITERALLY no IDEIA what are you talking about, but i love those videos lmao.
I think my fave way to avoid doing sqrt is the famous Quake 3 fast inverse square root function, which uses the mantissa of the float itself through a dubious cast and some bitwise black magic so you can calculate normals faster.
"// imaginary part in the cosine to give the reader mental damage"
It's a critical hit!
Not quite the quaternion video I was hoping for (you mentioned adding quaternions in the comments of your prior video), but I i will always accept more math optimization content on this channel. And yes, I was not joking when I i said I i was hoping for _quaternions._ Quaternions are actually pretty simple when not obfuscated or divorced from their connection to the composition of reflections.
Cordic is specifically designed for machines with no or slow multiplication, so it doesn't actually require them (that python code isn't really a good example), but when you do have fast multiplies, it's not really worth it.
i absolutely love your videos. not only was mario n64 my childhood game, your videos have the perfect amount of nerdiness and math in them to be interesting while your jokes are hilarious. Keep it up!
That was super cool. I liked watching how everything was broken down to extrapolate positions based on just a few calculations. It was amazing, and very interesting to watch!
I would love to see your version being played by SpeedRunners so they cab comment the diffences in the feeling of the game.
I'm sure they will, his mod also looks amazing
Kaze played the original game somewhat recently, and noted about how the physics and mechanics changes made him more rusty in the OG, since his romhack has many quality of life improvements and mechanics
i understood approximately 10% of the words in this video but congratulations to you and silas on the toenail
It brings me immense joy seeing you pull more and more optimizations for this console as if out of thin air. Thankyou for documenting and sharing your discoveries with us as well, unbelievably fascinating!
Kaze, your channel and insane romhacking ability was a big inspiration for me picking up Decomp romhacking myself and making my first Pokemon romhack. Just like your videos I barely understand what's going on and I'm enjoying every second of it. Thanks for being awesome.
Love your conclusion about assumptions.
Half-jokingly, I'm wondering when you will start optimizing the microcode itself as we're far into GPU-limited territory now. :)
Sauraen is currently working on a new microcode called "f3dex3". I'm thinking of getting into microcode programming and expanding on his work when he's more or less done. He's already found some optimizations that are implementing in this mod!
@@KazeN64oh yes micro code 😊 I hope you document your journey into it, there isn't much accessible resources, it might help democratizing it 🎉
Just went over to their CZcams and there's some cool stuff there. Where could I find more information about Sauraen's efforts in this direction?
he doesn't post too much publically i think. he usually talks in the fast64 discord.
@@KazeN64 Waiting for the day you tell us, new f3dex3 microcode just dropped!
The level of optimization here is just too satisfying to hear about. If only such maximal utilization of resources wasn't such a time intensive practice.
Yeah, you've hit the nail on the head here. Programmer time is expensive and limited. You can't employ double the programmers to double the output due to coordination taking up more and more time as team size increases, so a hyper optimised game either needs more development time or exponentially more money.
@@KenionatusThat's also why console graphics got better as generations went on: a more experienced programmer could use his time more efficiently.
i;m new to programming and i was shocked that interpolating between 2 values is slower than calculating all that stuff. I would have just assumed that interpolation was faster and never even investigated. Nice job
I'm consistently blown away at your programming skills. Keep up the great work!
This is wild, not only is it more accurate but it’s also fast enough that the console doesn’t even know there’s a difference. Pushing the 64 like this makes me wonder what kind of games we could have if AAA devs still put games out on older systems.
I hope the community has access to all of these clever optimizations one day
You took the most parabola-like part of the sine that's still fully periodizable and used it to cover the entire thing. That's great.
This was an interesting watch. I love these types of optimizations, pushing the limits.
My favorite optimization has to be the fast inverted square root since its so simple and so fast, obvious in hindsight but not very if you don’t already know it.
All the cache talk reminded me the issues we had with PC to PS2 ports, having DMAs constantly stalling on instruction and data cache fills. In the end there wasn’t a lot we could easily do. Fun times.
crazy that we have something this insane for an ancient game and then modern game optimization existing in the same timeline
I wouldn't say modern since pretty much every game released today has awful optimization and rely on dlss and require 32gb ram and an rtx 4090
@@SmashyPlays that's... what I meant... I'm comparing them...
@@ThompYT oh my bad I can't read lmfao, sorry about that
@@SmashyPlays what are u sorry about, you're fine 👊
@@ThompYT thanks you're a g 👌
You think I would just ignore Mario doing the soyjak face in the thumbnail? You think I would just let that go? You're a fool.
Another technique I once tried on a different platform uses the identity sin(x+y) = sin x cos y + cos x sin y, cos(x+y) = cos x cos y - sin x sin y. I split the angle into two parts containing the high and low bits of the angle and used lookup tables. But the polynomial expansion turned out to be faster in the end.
I love this kind of passion projects. Keep it up!
Quaternions 😢
quaternions will be the final animation format used here, no worry! but yeah at the moment it's still euler angles
Fingers crossed for a video. I will however ask if your planned use of quaternions still uses the 360° fixed point angle format, since the individual components are no longer just raw angles, but floats are also twice as large.
@@KazeN64that would be insanely cool!
Nintendo, hire this man once he manages to optimize this game so much it runs in reverse and works as a time machine.
you explain the basic trigonometry concepts that drives sine functions very well
"For you that was 1995. But for me, that is *today*" 😂
Random question: Who composed and programmed the music in the Return to Yoshis Island demo and Peachs Fury? The music is amazing in these games! Thank you for your incredible work!
Kaze giving a whole new definition to speed running here
I love your videos, man. Keep up the great content!
This was a great video. It was like the best parts of Michael Abrash's Programming black book, but about Mario 64. Thank you for putting this together.
as someone who loves low level code, hearing that a square root is optimal is bizarre and awesome
bro is a genius, and he’s using it on mario hacks 💀💀
Bro ✅
Skull emoji at the end ✅
@@escape209lmao
@@escape209 bro 💀💀💀 i don’t think i did that bro 💀💀💀 but the hacking skills are crazy 🔥🔥🔥🔥
After your last video on this topic, I was convinced that the accuracy could still be improved considerably. So I am glad you found a way to get it without sacrificing performance, even if none of my suggestions were what got you there.
A cycle is a cycle, you can't say it's only a half.
when anyone asks if math is useful, I'll just redirect them to your videos
I guess the only thing to do now is Fast Approximate Square Root.
For real though, that folded polynomial is crazy. The math nerd in me was more than impressed at the ingenuity.
any square root approximation will be a lot slower than the hardware one i think. the famous inverse square root algorithm is in the ballpark for 3 - 20x slower (depending on use case)
@KazeN64 is that the quake 3 fast inverse square root trick?
@@KazeN64 Well, that's unfortunate, but hey, at least you got a few cycles saved with the current implementation.
@@MDaveUK if you've heard of it, it's the famous one :P
You are doing a LOT of heavy lifting in the N64 space. I don't know how many people are still making homebrew for this old a console, but I imagine you could get most projects to run around twice as fast, which is massive.
Looking forward to the finished project and to Mario64 2.0 running at 60 fps on native hardware :)
Lookin great Kaze. Doing amazing work for the community.
Kaze has dreams of finding out ways to optimize Super Mario 64 further. We need this man to optimize Starfield and it's 20 year old engine lol
Bro, imagine someone as talented as Kaze trying to improve Bethesda's graphics engine, maybe he'll encounter as many bugs as possible on the first day xD
no its not 20 year old engine people say this when they dont know what they are talking about. and anyone who has reverse engineered creation will call you an idiot creation doesnt have anything left of gamebryo except for two functions and that is its scenegraph and its node system. literaly not one single other thing from gamebryo exists in creation. gamebryo is not a game engine it is an engine framework and creation was a engine made for bethesdas games
creation 2 is a near complete rewrite adding completely new systems to the engine thwt are impossible in fallout 4s version of creation hence why its called creation 2
the engine isnt actually that unoptimized its just extremely cpu bound as all versions of creation are because you cant run most of its background functions on the cpu
when people have performance issues its because the single core performance of their cpu isnt as good as it could be and theyre trying to push the game to max everything.
ns then yell about things they do not understand.
and as much as gamers think they know what the fuck they are talking about they really really do not know what the fuck they are talking about. do gamers somehow know more about how games work then an entire company who has very selective hiring practices and id softworks developers who i might add are fucking wizards wouldnt know how their own engine works?
@@GlitchLamb hell I think maybe within the first 5 minutes of looking at their code lol
@@jh302 nice book didn't read. Let me know when they can actually have proper vehicles in their games without their garbage game engine breaking after being held together by unoptimized and bad code for years.
@@jimmyv3170It wasn't even that long
These optimizations are getting ridiculous at this point, great stuff Kaze! The folded polynomial approach is brilliant and elegant, nice job to the guy who came up with it
I can't wait to start seeing speedruns of one of your fixed sm64 versions, and listening to the speedrunner's comments on the run.
wild how much you guys can come up with. god bless the information superhighway baby
Someone needs to show this to Todd Howard so he knows what optimisation is.
He's too busy putting his energy into convincing people the ridiculous CPU tax is fine
I'll "fold" your "polynomials" for 64 bucks.
Made timestamps for the video. @KazeN64, can you please implement these when you got a minute?
0:00 Intro
0:56 Chapter 1: Refresher
2:49 Chapter 2: Numerics
3:20 Chapter 3: The Square Root...
4:42 Chapter 4: The Folded Polynomial
(I quickly scrubbed the video several times and there was no chapter 5, I think Kaze just saw the length between chapters 4 and 6 and assumed it was there)
10:29 Chapter 6: Other Ideas
12:23 Conclusion
done! ty!
I almost caught myself asking why, but no, this is cool as hell. While the heft of our operating system-scale browsers (at least relative to OSes [checks notes] 20 years ago? Holy crap.) may give the impression that memory and compute are cheap and plentiful for the moment, we're running into for-now limits on just how much more memory we can pack into a space, how densely we can pack storage on a drive of any type we currently use, and just plain how many transistors we can fit on a given die using today's tech. People enjoying the sandboxes of constrained computing that old consoles offer will probably provide some much-needed optimization hints for the giant and heavy programs of tomorrow.
But most of all, I know we all pursue our own niches for personal enjoyment and it makes me happy to see someone making strides in their chosen area.
That's an awesome idea for approximating, sad that it's basically the same speed-wise, and n64 specific...
its a lot more accurate so i think it's still a huge bonus! i bet theres other architectures that benefit from this approach too
@@KazeN64 yeah, I guess more older hardware would probably benefit from this! I just don't think there's a lot of hardware where you both use sin/cos/tan a lot, yet those operations are not super-optimized in hardware.
Accuracy is great though! How close is this to being the perfect 1ULP function?
I was on a discord where they had discussed porting Mario 64 to the GBA, the same discord where tomb raider GBA was presented, I wonder how much it's compatible with that console, they had bomb OMB battlefield rendered with texture. The fill rate is even more of a bottle neck 😂
@@lior_haddad Only use case I could think of is GPU stuff, where that style of sin/cos would be integrated into the hardware, I've no idea if it would be better than what they use though
nintendo 64
Nintendo ultra 64
i wish all games had dedicated optimizers like you and your community!
You really should look again into CORDIC, there are implementations of this algorithm only using addition/subtraction, specifically for FPGAs. I used it a couple of years ago to calculate a sine for a 40MHz ADC input for phase shift detection (dual phase lock in) and only needed ~30 clock cycles for a 64 Bit input signal.
i'll need to see some code before i can give it a consideration
The N64 definitely is the system of all time
Possible optimization: This is going to sound ridiculous but in many programing languages, multiplying by 0.5 can be faster than dividing by 2. I know this is the case in C# but I don't know about C or C++.
I don’t remember for sure but I think he might’ve said he’s already doing that in the previous video
On a bit level, they're just adding and subtracting 1 from the exponent, though if the instructions always take the same number of cycles, then dividing by 2 would slow down to accommodate non powers of 2 that get passed in, which are much slower than a single multiply, but can be more accurate. Multiplying or dividing by a power of two on the other hand is always perfectly accurate as long as your floats aren't subnormal.
That said, this doesn't actually seem relevant as the given code doesn't include a single division, nor multiplication by a half.
GCC compiles a division by 2 into a multiplication by 0.5 - but i don't divide anywhere in this anyway so i don't know where you got that idea.
Yeah, your right. Also, I meant it as a general optimization and not one for calculating sin functions.@@KazeN64
7:06 For some reason this reminds me of the Zelda NES fast travel glitch❤
I think variants of this might be a bit faster on any hardware that has a dedicated floating-point square root function but not a dedicated trig function (or, at least, no fast one)
I do not understand 😁👍
This is fantastic for use in resource constrained flight controllers
I wish you could make videos like this every day
MARIO IS A MENACE IN THIS GAME Mario making that goomba and get squished by the plank he was sitting on?? and Mario breaking the glass the Koopas were carrying??? Hilarious
this video combines all of my favorite things: cool math, computer systems and programming, retro games, and SUPER silly cat gifs
Since this code operates primarily on 16-bit shorts (if I'm reading it correctly), do you know if an extension of this could still be valuable for general floating point values?
Great video, thank you!
However, I don't understand why we can't use the second hand-picked polynomial instead of using sqrtf to find other parts of the graph?
video for each function LETS GOOOOOOOO
As someone starting Algebra II I'm starting to get this better
I didn't understand much of this but found it really inspiring and interesting XD
your outro is brilliant. I wish i could subscribe again :D
SilasLock had the oppenheimer song playing while he thought of that optimization
MMM recently I found out about chebyshev polynomial in the computation of cosine distance field. I haven't investigate yet, my use case is a bit different, I'm trying to find an algorithm with no loop to raytrace an helix. Fun how both look alike.
Hi Kaze!
Very cool!
I wish developers still cared about performance like this
I haven't looked through the source, but computing sine and cosine at the same time made me thing of the mpfr library, specifically mpfr_sin_cos(). Obviously an arbitrary precision library won't be using that same approximation, but I wouldn't be surprised if it was calculating it in a similar way.