best trig approximations in x86 asm | SCHIZONE EP-31

hey guys welcome back to the skit Zone my name is completely irrelevant to the topic which is alternate trig function algorithms or approximations uh particularly for S and cosine besides the tailor series expansion that we implemented back in the beginning of this series um I want to talk about the performance the memory footprint as well as the accuracy of each algorithm and some comparisons between them I have a bunch of algorithms here today so you'll be kind of interested in them um both on the low end and the high end as far as accuracy and runtime and everything the whole Gambit is here so it's pretty cool stuff um I have a lot of high level takeaways um even Beyond just the actual algorithms themselves so I think you'll enjoy this as much as I did over the past two weeks going through this I really love this kind of stuff personally uh okay first some misconceptions one is that there's an idea that Hardware is always faster than software I would say yeah in general that's the case but not always there's some overhead related to I'm speaking here about the floating Point Unit there is a hardware instruction f sign and F cosine as well as other instructions as well for the x87 math Co processor um that's for Boomers really old stuff but um there's some overhead regarding how do you get floing Point values on the FPU and then back off and if you're going to constantly be switching back and forth FPU and like SS2 instructions like we have in this series there's going to be some overhead there that you wouldn't already have if you were to stay on the FPU entirely either way what I'm saying is that there's sometimes a case where software is just better than Hardware as far as performance is concerned and also the hardware instructions are extremely accurate they have to provide enough accuracy for all the bits that you put in and so question is do you always need that much accuracy not so much so number two integer arithmetic is always faster than floating point I would say in general yes and if you can come with an algorithm the same algorithm in you know integer and floating Point probably the integer algorithm is going to be faster but you know there are sometimes shortcuts you can take with Floy point and um also there's an expense related to converting ins to floats with the convert instructions and stuff like that so it's not always the case I'll leave it at that number three the idea that you always need high accuracy functions in reality you really don't unless you're designing like you know or planning caliber missile trajectories to hit Ukrainian power stations or something you don't really need 16 digits of accuracy on your sign and cosign I don't think um lot of the time you know 3 four five is more than enough and even for our applications we don't go more than like six or seven digits of accuracy for all our three 3D rendering so you don't need as much as you think you need most of the time uh number four a specific approach will be best for all applications obviously that's you know obviously false you know you have to tailor your approach for the application as I said before if you don't need the accuracy maybe pick a worse algorithm if you don't have the memory space to to spare maybe pick a smaller algorithm the choice is yours right number five slow algorithm will make your code do slow I want to show you that even the fastest of the fast algorithms are not that much faster than the slow ones um you'll see here in a few minutes that's the case it's not going to be a huge impact on on your performance know that there's always more important things than your math implementations you know uh right into the screen right into a file is always very slow and most of the time in my experience that's what limits your speed not so much um your sign approximation of course obviously if you can avoid slow functions avoid them but it's not going to make or break your runtime in fact most of the time your CPU is sitting idle you know you really you can spare a couple Nan seconds here and there for a slower algorithm if it's easier to implement um second to last simple algorithms are always easiest to implement you'll see that's not the case sometimes the more complex algorithm are easier to implement and I'll show you perhaps why that is and lastly um there's nothing to be gained by comparing apples to oranges in this video we're going to be comparing apples to oranges to plums to pears and I want to show you that even though we're doing that you can still Garner some high level understanding and takeaways from this okay so right into it now here are the two easiest s and cosine approximations um the first is the small angle appro oximation you may have heard that before a lot of Engineers use this to simplify their equations so s of X is basically X same with tangent of X and cosine of x is basically one for small values of X or you can take a look at 1us X2 over 2 that's also perhaps better way to approximate cosine either way this is very fast as you would expect in fact you don't even have to do anything you can literally inline and play replace S of X for X in your other algorithm so if you have some other algorithm that uses sign and cosine we'll just replace that with these approximations here so really there's going to be no overhead as far as memory footprint you're just replacing sine of x with X and this is very very fast as you would expect but it's only valid around x equals 0 or perhaps higher um values as well like for example uh you know you can you know sign and cosine they're periodic so you maybe you can remap higher values back towards zero as well but either way it's only valid over a very small small range also what about return zero this is perhaps a a dumb approximation of sonic sign but uh it is right infrequently and periodically this is more of a control than anything else to compare our other algorithms against but even this is valid every 2 pi right so you can perhaps use this if you know that you're going to pass in an N Pi into your sin of x cosine of x functions okay how about some a little bit more challenging approximations here well one might be a lookup table this is one that's very simple and the idea is basically you pregenerate and store however many s of X values in order and maybe the first one is for S of zero the next one is for s of some small X let's call it like you know delta T then you have S of 2 delta T and so on 3 four 5 delta T Etc and uh basically by passing in an input number you can say hey I passed in 7 delta T well you check the table what is the seventh or eighth element down that table and then pull it out and return so it can be very very fast and also it can be tailored to your application um so if you need a big table you can have a big table if you can get away with a small table you can use a small table but obviously the bigger the table the higher your accuracy and honestly the um the scaling is pretty good I'm not sure what caching even means but as far as I could tell when you scale up this table it doesn't really cost you anything as far as runtime it just makes your program more accurate obviously if you have a immense table it's going to have some expense as far as that entire table cannot be located entirely in your cash and so there's going to be a problem with that but either way uh it's going to be pretty close as far as performance um then you have these two Hardware instructions I mentioned before f sign and F cosine they're on the math C processor that you have on your computer right now if you're watching this series probably um it's decently fast they are extremely accurate I think they have like the maximum accuracy you can get however there is a significant overhead when you have to load in the contents of an xmm register onto the FPU because you have to actually go through a memory address to do that and so you're basically have to go from an register into memory onto the FPU do the instruction and then undo the last three instructions so it is a little bit of expensive operation to get this set up especially if you're not using the FPU for all your math but it has a very small footprint and it just works and you can just call this whenever you want and it's honestly a great bang for your buck then you have this bascara whatever his name is uh approximation from like a thousand years ago he basically has these two um estimates here for S and cosine you can see them here they're very fast they're good enough like almost all the time and they're valed over only a very small range so you have to remap into that range but uh I either way these polinomial or whatever you call these types of things are extremely good as far as accuracy for how much space they take up in memory so very efficient approximations this guy is an ultimate Boomer he's from like you know prehistoric times but he's a really smart guy so great approximations there now we have some approximations for math enjoyers so Tor series we already covered that in the beginning of this project however it is just a sum of these terms and the terms scale and they keep shrinking by the factorial here on the bottom and so you get more and more accuracy the more terms that you have that you're adding up um and so you have a configurable accuracy you can change how many ends you want to add up 5 10 20 and you can relate very easily the number of terms to the accuracy because because the 10th term is going to be you know this and if that number is less than your tolerance you can stop so it's very easy to decide when to stop your approximation and then for the uh idea of how efficient it is you have a pretty good bank for your book as far as memory footprint and performance I'll show you the results in a minute um so wait for that but it has a very good speed for decent accuracy and and uh the problem though is it's only valid over small range as many of these algorithms are and so you have to constantly think about remapping so if you pass in sine of3 this might handle your problem directly but then what about s of 10 trillion and three well you have to constantly subtract off some number of two pies to get back into the range where this is actually valid so it's easy to implement documation is everywhere and we've used this for everything so far in this series and will probably continue to do so in the future chubby series is one that is better however there's almost no good documentation on this out there unless you're really good at math you can figure it out yourself I do have this one paper I'll pull it up here um this paper is by this uh Sean Felder fella um basically he's tabulated these approximations this table basically of uh coefficients a and uh what you do is you basically compute this terer multiply it by a and add them up and for a different amount of terms you have more and more accuracy and he computes it all the way down for 10^ the -4th in accuracy however I has it both for cosine and for S and for other ones as well um I'll link this in the description um however I do think there's a typo somewhere in these tables because I'm not getting the perfect accuracy that he's he's bragging about but either way um we can evaluate this ourself and compute our own coefficients but from what I can see here the accuracy is is lacking but that's just a problem of I think a typo in this table so with that out of the way um back to chbby Chev as far as pros and cons again it has configurable accuracy so the more terms you have the more accurate you're going to be and this you'll see is probably the best bang for your buck this is like the the optimal sele C of your coefficients for a given accuracy it's kind of the whole idea behind Chev as far as I'm aware and so it's very fast with very good accuracy and you'll see that result in a second um but again it's only valuable a very small range and so you have to remap back into that range and uh as I said before there's not much papers or you know pseudo code out there to look at you have to do this by yourself you're kind of on your own for this okay and lastly the one that getss shilled all the time I'm not sure why is this Boomer Cordic approximation thing um and we have two ways to do this one with floats and one with integers and the idea is simple you can look up videos and stuff on this or look at the Wikipedia I do have it open actually um the Wikipedia algorithm here actually implements I think it's in Python the folding Point method um so not exactly the intended use case but I do have a pretty good integer paper I'll put that in the description as well this guy Michael Bron has a pretty awesome 16 bit implementation but we'll do we'll do much more than that in this video but uh the idea is basically either with inser floats you basically start with the right half of this circle and then you constantly it's not really bisecting but you keep breaking apart this sector of the circle into smaller and smaller pieces correcting with an arc tangent until you Converge on your given angle and uh by adding different well subsequently smaller and smaller and smaller arctangent values you can Converge on both your s and cosine actually at the same time so there's like a double uh throughput there as well but the idea behind this is it's it's a boomer algorithm because it has for integers there's no Hardware multiplies there's only add subtract and shift I can show you this guy's paper if if you're curious the algorithm a lot of boiler plate stuff but um where is the algorithm basically write here here's the iteration of the CTIC algorithm so you access the table you add to your running angle sum essentially and then you just add and bit shifts by different amounts so there's no multiplies it's a very efficient integer approach for this problem um but there is a so I should say you can get extremely high accuracy like like insanely high accuracy with this even though it's integer only you may think that integers are you know for rounding and stuff you must lose Precision on that you actually have a probably the highest accuracy of any of these methods with the exception potentially of the FPU because you actually have 80 bits of accuracy on that not 64 but either way extreme accuracy really decent speed but a particularly large footprint especially if you want to handle different amounts of Tolerance at at runtime if you want to say hey I want 10 terms this time but 30 Terms this time you'll have some overhead there to handle both those cases and for floating point it's much the same you have inherently worse accuracy because you have this um accumulated floating Point error um so it's worse than the integer version it is seemingly faster though so you may think well this bit shifts must be super fast yeah they're fast but when you have to constantly um access memory to pull things out of these tables and remember you're passing in a floating Point number in the first place and so that has to be converted and there has to be adjustments for the you know your domain are we sign of 3 million Pi again or are we near zero and so there is some overhead that you have to do it either way for both and um a lot of the time all those convert instructions and memory accesses may not be as fast as grabbing something from from memory as a floating point or keeping it in a register as a floating point so yeah there's some pros and cons to each of these two now for the actual results sorry to keep you waiting um so what I have here is basically and this is the example today I have one for sign and cosine both here's the sign one we've we're averaging basically um well we're generating like half a million random numbers and evaluating the sign and or cosine of them and in the first row you can see the first five of these half a million signs and the exact answer for the sign of that number so s of 6.34 is zero and these random numbers are always between I think -1 and 10 so they're beyond the range where any of these algorithms is going to be valid but um you know like most of these algorithms are only valid between like 0 and pi/ 2 or negative pi to Pi Etc so this is outside that range obviously um and so you are looking at the time and the performance and the memory footprint and accuracy of of this entire setup of taking the input X mapping it back to the range that we can use our approximation over and then the function itself executing so like I said before these are the first five of the half a million signs here's the exact sign I think we're using the FPU to evaluate this exact quantity here and then I have each algorithm and then for each algorithm I have just for these first five signs first five X's 1 2 3 4 five the corresponding function evaluation for this approximation in this case return zero always return zero which is the whole point of it but for other ones you can see here for tayor series for example this is very close to the exact answer for sign of 6.34 so a little bit hard to read this table but that's the idea and then I have the error plotted here so for a given approximation what is the error from the exact answer and then I have a a time in fractions of a second for how long it took to execute half a million of these signs through each individual algorithm and then I have uh divided that that out basically per each sign how many CPU cycles that was more or less and there's some variation in this so don't take too much confidence in these numbers but the overall trend is there okay so the first thing and then also I have on the right hand side the bite counts of each algorithm rounded to a multiples of 64 because I've aligned these all to 64 byte boundary for again just an Apples to Apples comparison of the performance okay so retting zero as you would expect is extremely fast seven cycles per each sign so very very efficient um just to basically replace the x value with zero of course not a very accurate algorithm you can see the error is quite large in this case it's Error of one basically error of one so um not too good that's actually really bad um but the memory footprint is zero so that's kind of the gold standard here as far memory size now the small angle approximation now this is only valid around xal 0 and none of these particular X's that I'm showing is near zero and so all the errors are quite large you can see here this is a terrible error error of seven in this case very very bad but again Cycles is six actually it's even faster than return zero because I can literally inline replace the X with the new X right sign of x = x I can just return from this function directly there's nothing to be loaded into registers at all so even faster than return zero and again zero bytes now into the more you know accurate algorithms I would say or more useful I would say um first is the tailor series and so for this I've picked some tolerance it's probably around one E9 or something I would say just based off this error I'm seeing here and you can see now we are very close to the exact answer we're within E9 for all of these and it takes us 221 cycles for each sign and we're using this type of uh algorithm for everything in the skit Zone Series so far and so clearly it's not slow but you'll say hey it is way slower than small angle approximation sure it is but you're getting way more accuracy for the time and the memory print is 384 bytes so larger but nowhere near as large as you would expect a lot of these other libraries to implement this type of stuff um very very small function even though it's much bigger than these two simpler functions okay so that's kind of our first real function not really sure how that compares here's a look at some other functions so lookup table now this one I've only implemented I think it's 100 for this particular case um items in that lookup table so you're inherently going to be remember sign goes from negative 1 to one and so if you divide that two you know y value Delta into 100 spaces that's what 02 and so you're looking like yeah we're probably going to be within uh like 02 for for most of these and you can see just by having that table in there even just having 100 elements you're already up to 704 bytes so almost double the tayor series implementation that we've used so far in the series and you have worse accuracy so all the haters out there that say Hey Taylor series sucks it's this dumb cringe math thing it is that is true it is cringe math thing but as far as accuracy as far as footprint and as far as speed well I guess speed is faster but is it worth it if you're going to be so far off now I will say if you're going if you can sacrifice the bites if I can go from 100 to 10,000 then all of a sudden my accuracy reduces by a factor of what 100 right and so then we're in the realm of maybe not matching this tor series but being closer and this cycle count is not going to increase by much if at all so you have to weigh that is it worth the extra bites the extra blow in my binary or not so yeah good question then we have bcar now here's an interesting one right so for bascara you'll see that the cyle count is actually less and remember this one was that that thousand year old approximation here and you'll see that it was faster than the lookup table and it had comparable if not better accuracy than the lookup table for that many elements in it and the bite count of the binary is small smaller so almost the hands down well I would say definitely hands down better for this lookup table size now if you were to increase lookup table you know 10 fold 100 fold thousandfold maybe it would be better as far as accuracy but honestly you don't need more than E3 accuracy for most applications in sign and cosign you may think that you do but think about it some more cuz you really don't most of the time uh so yeah that's pascar a very good algorithm and next is the hardware instruction so this is that FPU f sign or F cosine instruction and here you can see this accuracy is um is perfect because we're using this as the definition of exact so yeah zero error um but look at the time it takes to do this so just looking at this from tiller series it is slow so using the FPU is slower than the teror series expansion with this many terms in it of course better accuracy but do you need that extra accuracy is the question is E9 not good enough for you I don't know check figure it out yourself I don't know maybe it is but the size of this binary is very small it fits in one 64 byte block as far as lining is concerned so yeah pretty cool stuff there I would say if you don't care about again in this series we made the decision that we're going to only stick with SS2 instructions um for everything so we're not going to use this but if you don't have that requirement that constraint I should say yeah go ahead use this this is great it just works plug and play and uh it's not that slow and gives you I would say extremely accurate accurate results now here is the the best one in my opinion is this chubby Chev expansion thing and just look at this in less this is a polinomial random thingy it's just some some you know math stuff again but look it's faster than the hardware instruction it is essentially as accurate right e -16 for this many terms that I'm putting in here and the file size is large but not that large and a lot of the the file size here has to do with I want to support multiple um tolerances and so if I go back to this table here you know I want to support up to 40 you know e negative 40 of accuracy in reality we're not going that deep but I've still wasted some bites on storing these values in the table so yeah there's that um but I would say this one is the best one as far as bang for your book regarding um file size performance and accuracy now into the two CTIC approximations floating point and integers you'll see here that they are are they exactly the same look at look at these the arrows are the same the signs are the same of everything that is s of X so they match exactly for these amount of terms that I've picked in the approximation so this is as close as you can get to an Apples to Apples comparison of these two algorithms now for the floating point one you'll see that it's slightly slower than the integer one which is to be expected because it it is slower to use floats most of the time than ins um there is an implied denominator for the integer evaluation that's we convert back out of at the end and that's why it's so much faster we don't have to keep tracking this and I will say the um I guess the accuracy is up to a limit you can increase this accuracy for the integer version like almost to the I mean to the same degree that you you can get the hardware instruction you can get this error to be zero if you up the number of terms you can't do that for the float you're always accumulating some amount of floating Point error and you'll never quite get to zero error relative to this but you'll be able to get that with integers alone so for that reason alone if you want a truly exact answer and you can't use for whatever reason the hardware instructions then use this Cordic integer approximation and so here's that you know misconception that integers are going to be less accurate not the case if you have a very large implied denominator you can get like every single bit of accuracy there's no waste of bits on exponents or anything like that or signs if you can use the bits efficiently you can get way more accuracy out of a fixed point or integer approximation than you can for a Flo just my takeaway top level here and then also look at the size so we are bigger a bit than the other algorithms in the in here perhaps the exception of lookup table for more terms but uh again a lot of these Bites come from the fact where I want to support multiple tolerances if I want to have 10 terms 20 terms 40 terms the tables in these files and I'll show you those in a minute are large enough to support multiple tolerances multiple you know accuracies in the function call at runtime time do you need that no you could pull all that out and get these bik counts way way down if you wanted to but again even still these bike counts are not massive and um there's no reason to do that in my opinion okay so with that out of the way that's the kind of top level comparison and you can see um one take away here is that there's not a huge variation you may think oh yeah that algorithm is so slow tayor series is so slow well first off it's not it was actually one of the fastest ones but even still look at the variation here as far as you know I I'll call the them the reasonable algorithms so let's take a look at the ones that are of decent accuracy so I'm going to ignore small angle ignore return zero tillor series is one lookup table is I'll say not so much here but maybe we'll grab it bascara Hardware instruction chubby Chev and the cordex if you look at all these the fastest one of all these was bascara at 50 Cycles the slowest one was Cordic float at 700 Cycles so you're looking at little over a factor of 10 in variation but what are you getting you're getting six more digits of accuracy in the result if you ignore the ones like lookup table and bascara and you stick with the ones that are like ea9 or better what's the fastest one chbby Chev 178 the worst one is cord float 700 so even still you're looking at a a factor of four variation between the very best and the very worst algorithms so not a huge factor factor of four is not massive at all factor of 400 is massive factor of four not massive so yeah that's the take way I wanted to show with this that even the slowest algorithm on this list is not going to really slow down your program unless that's the entirety of your program okay so what are some caveats for this well first the footprint for some algorithms as I mentioned is inflated by having large tables of this pre-computed data both lookup tables as well as just data for the algorithms themselves and um that gets even worse when you want to support multiple tolerances like hey I want to support 10 terms 20 terms 30 Terms I have to have more and more data in those tables to permit more and more or uh basically tolerances at runtime so number two the accuracy is all compared relative to the FPU instruction so that could be wrong the FPU could be wrong about all this and this entire table could be bogus so I don't know I guess I could check that but I I believe that it's correct personally uh number three implementations here are decent but they could definitely be improved I didn't spend much time know optimizing each algorithm all I did was Implement them and then align them a little bit and debug them so I didn't spend time optimizing each one and so even that factor of four at the end of the day um between chubby Chev and float that might not be a factor of four if I were to spend or you were to spend an hour or two optimizing these algorithms further okay and then I should say that there's a certain amount of variation in execution between each run right this takes maybe like 5 Seconds to run half a million of each sign through each algorithm and I've just screenshotted one result here of course you can take the code run it yourself and get similar numbers on your machine um and there's going to be some variation so hey maybe it's a factor of four now but it might be a factor of three on average I don't know could be and then uh lastly the I should I can show you the code but we're only timing as best as I can the algorithms themselves so basically we're calling a rapper function for each algorithm and that calls the function itself so there basically two calls and two returns and then the function itself so um it's pretty if I would say apples to apples in that regard and we're using um rdtsc the instruction to basically read the number of cycles that have been you know elapsed on the on the hardware as along with the Cy call for time that's elapsed and so both of those are basically the same thing but we're using that to evaluate the performance and we've pulled all the random numbers and their generation out of the loop just to make sure we have an Apples to Apples comparison because the uh random function well the the random instruction well the instruction that gives you a random number basically makes you wait until the number is ready and so uh you you can't keep calling that over and over and over again and time the result so that's pulled out out of the loop and that's why if you look the um memory footprint of the entire binary is large because I've allocated literally space for half a million random numbers in the binary directly so yeah there's that not very good but whatever okay so all the code is available in this um I spelled skits on wrong jeez I can't even we'll fix that live dude that would have been bad so yeah it's all in this Li math expression trig directory chubby Chev the cordex stuff FPU lookup table all that's in here sign and cosine and I have two different benchmarking functions programs that you can run um to see on your machine the the stuff so I'm GNA run this right now uh here together so I'll open up just the sign one so you can see how this is set up uh and basically it's pretty straightforward so we're including all the different sign approximations as well as functions to Generate random numbers as well as time the number of seconds and clock cycles that have elapsed and print the results out and so basically uh it prints out some formatting stuff it Loops through the different function slips through all of the random numbers evaluates the sign of those numbers prints them out prints the time out and then formats the result and I mentioned before this is a cool way to do this I have a function table that includes both the string of the function name so return zero is a I guess 17 or something 15 bytes long with zero at the end followed by a pointer to the function itself and so I can kind of store an arbitrary number of functions in this table and then automatically Loop through these so if you wanted to add an approximation for a sign go ahead add a sign function 10 add its name above that and then change this number here to a nine and the whole thing would uh would keep running that's great and then uh at the bottom here I have basically each sign function implemented as this is like the wrapper function so here is return zero you can see it just exor out xmm0 and returns here is the small angle approximation for sign it just returns right you pass in X I pass back out X so this is the fastest algorithm obviously then for Kill series you can see here we passed in the tolerance in this case it's E8 or 9 whatever this happens to be uh then it calls the ex the actual sign function directly and then returns and so I have lookup table bascara FPU Chev CTIC flow and CTIC int here as well so if I run this wait a few moments and it will dump all the data to the screen and here you can see the table that we saw before with some uh variation obviously in the ccle count and obviously the numbers have changed so yeah point out right here look at this number for X 02 well small angle approximation look at that 02 so that came out pretty close to the exact answer right e -6 even though it's an absolutely asinine you know zero instruction approximation hey it was pretty accurate for this particular input so there's that I also want to show you um the algorithms themselves just to give you an idea of how they're implemented because I think it's kind of interesting um lid math expression trig let's do that I hate that we have arct tangent another arc tangent cosine is tillor series we did that one way back in the beginning of the series here is the bascara approximation here you can see it literally just uh remaps our input so if you pass in you know X is 500 it remaps that back between 0 and Pi / 2 that's the first thing it does gets an idea for the the sign of this so it has to negate the answer if it's the wrong sign but that's fine it tracks that in a flag and then it just basically implements the scar approximation you can see here a very simple fling point the registers here being used and then Returns the answer so very straightforward some hardcoded values in memory here for the comparison of the the range I guess the the input X needs to be remapped between 0 and Pi / 2 and then also we have like pi^ squ half pi 4 those things are required for the actual algorithm itself you can see here here's the algorithm cosine is pi^ 2us 4 so we have to have those stored as floating Point numbers of course you could convert four as an INT into a float but that is very slow so we don't do that that's bascara here is the chubby Chev for floating Point numbers um and it does the same thing it remaps our input to a certain range in this case z to pi over two then it starts con you know evaluating those T terms if I open up the Boomer Shan Felder paper um it basically implements this expansion this uh this sum for a given number of inputs and that you passed in in RDI as number of inputs you want to evaluate so if I want terms I to pass in RDI equals 10 Etc and uh it goes how you think it would work however you can see here here is the CH coefficients and you'll note that I only have some number of these but uh either way it's it's not up to 40 40 40 digits of accuracy it it stops way before that because you can't have that much accuracy realistically and um and maintain the number of of digits here so you you can't have the exponent and the accuracy both together I think in in all this but uh either way we have it all here just in case and that's how that works now here is the Cordic approximation this is the floating Point Cordic and uh this one basically implements the Cordic algorithm but doesn't use bit shifts instead it uses Hardware multiplies instead and it's not all that much slower than the integer version um so I would say it's pretty decent but you see here that I have a lot of data here for what's called the K factor I can show you that in a moment as well as Arc tangents as well as this is basically powers of two here as well and so this is all trying to basically do I have it open still I do this is basically imple this is the wrong one um you need an an arct tangent table here to constantly uh correct your approximation for the the angle and so you have a table for that you have a table in this case for this this divide equals 2 this could be a bit shift but I've stored that as a uh in this case floating Point numbers I've stored that as a bunch of powers of two negative powers of two in a table and then you have this knen this knen is a function well a scaler that scales your output because without this you kind of you either gain or lose length of your approximation uh Ray or line segment whatever that is and so you have to have a a correction factor and uh that's computed basically as a function of number of terms because of that you want to be able to support multiple inputs you know tolerance of 10 terms 20 terms Etc and so this has to be implemented in my case I did a lookup table for that that's uh this table here but uh you could Implement that logic that they have here in Python just the same but it would be more expensive I think at runtime whenever you can pull out at compile time or even before compile time I think is a good investment of your time and memory because uh ultimately this is not a huge memory footprint for this and it's way faster than solving those C values at run time uh okay there's that look look table here's lookup table so interesting stuff here basically um I decided to only use four floats because as you saw before the accuracy of this table is well of this algorithm is kind of limited and you don't get to the point where you actually need the full 8 byte floats for this even 4 by floats is enough to get your you know 0.101 accuracy that we were seeing and so I have these values here this is basically sign of every number between I guess 0 and pi/ 2 um so for x0 all the way to Pi / 2 in increments of that range divided by 100 I'm guessing and then we take the answer and we uh map it to every other possible spot on the number line so you know sign is very periodic in fact the very first pi/ two of that plot can be flipped negated copied translated around to make the entire plot over you know x negative Infinity to Infinity so that's how that works and then also you can see here this scaler this is what computes the entire like which address in memory should we grab and so basically whatever you pass in gets skilled by this and that determines how many bytes into the table we're looking so that's how that works um here is the integer CTIC implementation um this one is a little bit more sophisticated took the longest to debug but was also the most accurate and extremely fast algorithm that we talked about today um only beaten out uh by Chubby shev and but uh potentially even more accurate than CH Chev if you need it and um it enables you to pass in obviously both the x value as well as the number of iterations you want to execute in this case supports from 1 to 60 um the example that I'm going to link in the description this 16bit implementation only handles up to 14 I believe for number of iterations obviously this is for older Hardware uh yeah number of bits here is is 14 but uh either way you pass that in and there's a bunch of data down here to support that and so here is the you can look it up how this works a table of the initial X values a table of the AR tangents and you can see just how much accuracy you have so this correlates the Delta y to Delta X essentially for each iteration of your quic approximation and you can see originally it's very very large and this is this is divided by 2 to the 60th or something as far as so basically when you use this um integer approximation you're passing in basically a number an integer that corresponds to your angle from zero all the way to 2 pi and so I guess we're using 62 bits for that entire range and so 60 bits for just the top quadrant the first quadrant of that range and so basically this these numbers correlate to how many so if we divided that entire circle into 2 the 62 sectors this is how many sectors in the first correction second correction third correction Etc all the way down and the very last correction you can see here is two and so we're down into the the weeds of the the limit of our accuracy is basically down to 1 over 2 602 so it's extremely accurate algorithm if you run it all the way to the end to this many terms which we don't most of the time you don't need to but you potentially could so that's how that works um here is the FPU instruction so here's kind of the overhead I was talking about before about you know why uh why is it so slow to use this Hardware instruction shouldn't it be fast well here's why so we're using these xmm registers for everything in this project that's how all our math is done normally you don't couple XM registers with the FPU FPU is something that you do separately the SC processor is separate entirely you don't use them interchangeably but you can here's how you would do that basically you would take your x value dump it somewhere in memory then load a quad word from memory that memory address onto the you know stack of the co-processor call the instruction to evaluate the cosine that replaces on the stack x with cosine of x and you pop it off back into memory and then move it from memory back in the register and then return and so a lot of this is overhead that you wouldn't need to use if your entire you know code base was done on the FPU or whatever you call this the x87 C processor you wouldn't need these two instructions or these two instructions or this instruction or the call originally this could literally just be done in line on the cord processor and it would be way faster however to do Apple's Apple's comparison here um I I wrap this you can see here to make it work it would be faster though if you didn't have this overhead and so that should be remembered because hey this instruction only works on the old Boomer you know instruction maybe you should use the old Boomer instructions for all your math hey I don't know maybe your algorithm can be converted over to the co-processor instead up to you anyway that's the gist I just wanted to go through and take these like top level takeaways for you guys um and you can see just the the main tick I want to give you is it's not a huge difference you can spend you know days and days debuging this but is it really worth you know two days of your time to try and get chubby Chev to work when you could have just implemented uh you know Taylor series and it would have been a little bit slower if that or is it worth wasting time on Cordic to get that much accuracy and whatever else just to avoid Hardware multiplies well maybe not maybe bcar is enough for you maybe you only need E3 accuracy Maybe you should try that hey is do we have enough memory for a lookup table maybe we do do we not maybe we don't we we have to use the hardware instruction hey how about this what if our application only deals with very small angles maybe we can just use this one that one's pretty good if you ask me for small angles so yeah think about your application not a huge difference as far as performance and uh even file size is not a huge difference there either these are all very small by today standards as far as binaries go and um ultimately performance accuracy this is a a trade-off you have to make on your own choice and I would say my opinion if I had to pick one of these I'd probably pick chbby Chev knowing what I know now um but up to you chbby Chev bascara killer series all very good algorithms to do this we're going to stick I think with Hiller serus as a matter of principle but if you want to use the these other ones feel free with that I'll end the video thanks for watching I hope you enjoyed I'll see you in the next one