How can Computers Calculate Sine, Cosine, and More? | Introduction to the CORDIC Algorithm  

I figured I’d make this comment to address some common questions I’ve been seeing: EDIT: I made a mistake in saying that we don't need to calculate the angles a_n = tan^-1(2^-n). We do need the angles in order to keep track of the total angle we've rotated by, but we don't need to calculate tan(a_n) since we know it's 2^-n. Apologies for any confusion this may have caused. 1. Is this algorithm the main way to calculate these functions today? Today, this algorithm is rarely used. The main advantage of it is how few transistors it needs, at least compared to implementing a floating point unit to use a polynomial method. For this reason, the main use of CORDIC today is in circuits where hardware is limited, and not in more powerful modern computers. I think it's still a useful algorithm to learn because of how interesting the ideas behind it are, and how it gives you an insight into how computers function. 2. If CORDIC is used to calculate sin, cos, and arctan, how do we get the cos and arctan values we need for the rotation matrices in the first place? For the angles we use, which are tan^-1(2^-n), since we know the tangents of those angles are 2^-n, -we don’t need to actually know the angle on the computer- we don't actually have to compute tan. That’s due to the fact that the rotation matrix only has terms that are tan(a_n), which will always be some 2^-n. -We’re not actually using the values of the angles a_n when we do the computation.- We can calculate a_n = tan^-1(2^-n) using something like a Taylor series, which we need to keep track of the total rotation we've done by adding or subtracting each angle from the total depending on the direction of rotation. For the cos(a_n) constant, we can compute this using a method like a Taylor polynomial or some other approximation besides CORDIC. As @Demki noted, we could also use CORDIC to calculate the scalar of all of the cos product by starting with a vector on the x-axis with length 1, rotating it onto the y-axis, and then finding the final length of the vector L. If we multiply by 1/L, we’ll re-scale our vector to a length of 1 again meaning the cos scalar = 1/L 3. Why is the cos product K always the same? Wouldn’t it change each time we run the algorithm? The reason the cos scalar K remains constant is because the series of angles we rotate by, +/- a_n, remain constant in magnitude with only their signs changing. Cos(x) is an even function, meaning cos(-x) = cos(x). Therefore the sign of a_n doesn’t affect our cos(a_n) value. Since every cos(a_n) value is the same every time we run the algorithm, the constant K to scale the vector by will be the same each time. 4. Why not use something like a Taylor Series to approximate the values instead? Polynomial approximations like Taylor series are pretty simple in their computations, but they require a lot more multiplication operations. The main advantage of CORDIC is how easy it is to implement with very little in the way of transistors, at least compared to a floating point unit. 5. Why use the repeated addition algorithm for multiplication? Aren’t there faster ways to do it? The main reason for using that algorithm was because it was simple to showcase without having to first introduce binary. I know that there are much faster algorithms for computer multiplication, but the goal was to show something simple that provided motivation for the bit-shifting optimization while still giving a general overview of how everything works. I do regret not putting a note in the video that explained this, but hopefully people will read this and not be mislead.

I was expecting lookup tables and interpolation. Boy, how wrong am I...

I was expecting an infinite series expansion but this is so much more clever and optimized for computers

Amazing that you managed to put in an intuitive explanation of L’Hopital’s rule in the middle of it!

Awesome! I've been curious about CORDIC for a while, but I never had the motivation to trudge through technical papers about it.

Ive always wanted to figure out how CORDIC woked. I ended up using a basic Taylor series with 3-4 terms while using a repeated Chebyshev polynomial to make it way more accurate

I've been a casual math enjoyer for a long time (with only really doing a small bit of maths up to DE and Liner Alg.) and I have to say your intuitive description of L’Hopital’s rule was one of the best I've ever seen. Short and to the point and without alot of the messiness that you sometimes get when describing some facts in math. Thanks :)

Very nice presentation. The one thing that I found a bit cloudy was the K constant but after thinking it through I realized that K will always be equal to the product over the same angles, because cosine(-a)=cosine(a). This product looks like it should converge quite quickly so I’m assuming that we just use the constant (roughly 0.607) every time as within just 4 angle adjustments/rotations, K is within about 0.002 of this constant (K). We can safely assume that for almost every angle we are using to calculate the sin and cos of that it will take 4 or more rotations, so this constant is justified to be used for every calculation, and doesn’t need to be recalculated for each use of the algorithm. Thought I would explain my thought process just in case others were a bit confused.

I was looking for resources on implementing my own trigonometry functions in C just for practice and this is perfect!

oh man, this was my idea for SoME3! guess I gotta find a new one :P awesome to see this cool concept well explained though. Hope you keep making videos, you def know what you're talking about and the visualizations are great too.

I love channels that explain complicated thing with small steps and examples that are understandable

Beautiful presentation! I especially liked how you built a visual intuition for the sine and cosine angle addition formulas and for L'Hôpital's rule rather than just presenting them as established facts (hell, you didn't even mention their traditional names--and there was no need!).

I'm really impressed. I'm currently implementing a cordic calculation in an FPGA. Both HLS and HDL implementations for two separate projects, but i have to admit this was a great refresher. Please keep it up. You're doing gods work.

I think you've just given me the insight I needed to figure out how the equations were derived in the first place. Taking the simple ratios of a unit circle and making them more complicated by stepping makes so much sense I don't know why I didn't think of it before, but hopefully I'll build up a better understanding of math because of this.

Thank you for this video. I remember seeing a knowledgeable person on Reddit mention some techniques for trigonometric function computations, which included the CORDIC algorithm as well as pade approximants, I had not seen an explainer on cordic aimed at non-experts yet

Was always curious about this! Excellent explanation and visualization!

Thanks for making this. I've been trying to understand CORIC for quite some time now.

When I first started watching this video, I didn't expect that I would also learn some interesting pieces of knowledge re: Limits and series convergence. Thanks for the video.

Glad to be here before this channel blows up. Such amazing visuals and intuitions are a scarce thing

you just dropped an intuitive proof of l'hôpital's rule and an explanation of cordic together, loved the video

Kudos. This is one of my favorites of this SoMe so far.

Really cool entry P.S. love the effort in the 8 bit computer you made. I have seen ben's series on it

i've never seen this proof for the trig identity before, that's cool

very impressive video. Every college level concepts are explained in simple words and graph. Incredible work sir.

Now this is what I would like to actually like!

You surprised me when you whipped out that breadboard computer. I actually made one following Ben's tutorial too! Although I have bugs to squah...

fantastic video. i was really surprised to see you don’t have that many subscribers! you’ll be pleased to know you gained my subscription, and hopefully more people will find your channel soon. ❤ keep it up

I really liked this. The solution that I arrived at (and a solution that I’ve used for other transcendental functions) is to use a Taylor series expansion with just enough terms to be within the precision of the LSB of the data type that I’m calculating with.

Such a beautiful presentation! I've always been curious about this

Thanks for this! I've been meaning to understand CORDIC for a while but there's just too much fluff/ computer science background that I couldn't be bothered to read into. This cuts right through all the fluff (especially the (1/2)^n series at the beginning of the video) and helps me understand it!

what a channel, please do a series on directed search algorithms.

This is cool stuff. Highly advanced for rocket engineers.

Your computer is not multiplying, it is repeated adding. That's why it is slow. Using a Shift-Add or similar algorithm, it should be much faster. At a minimum, adding "16" seven times would be twice as fast as adding "7" sixteen times.

Back when I was first learning to program (using C++), I was so enthusiastic that I wanted to make my own command-line calculator. At first I made it using just basic arithmetic operations. And then later on I added trig functions (along with the other typical math functions). But at the time I didn't know the standard library already provided built-in sine/cosine/tangent functions, so I ended up writing my own rudimentary ones using Taylor's series approximations 😅

I've been trying to find this. Thanks!

This is awesome and so are you!!! Excellent graphics and clear explanation!

Pretty good video and lots of good feedback in the comments. A few expanded explanations (now covered in the comments but would be better in the video itself) and slowing down the pacing a tad would be greatly beneficial. Great job!

Even if the terms of a series are gradually getting smaller when n is getting bigger, the series can diverge. For example, the harmonic series (1/n) diverges even though the sequence 1/n converges to 0. In fact, if a series converges, then the corresponding sequence converges to 0. But, if a sequence converges to 0, the corresponding series can either converge or diverge.

Wonderful video!! please keep going!

What an amazing channel Hope that you grow to exponential heights. You help in visualization so well❤

Thank you for the information.

Thank you for this video. It is over 10 years I wanted to know this.

My calculus teacher last year taught us about Taylor series expansions, and he based the explanation off wondering how calculators get trig values, implying they use Taylor series. I spoke with him later in private to explain that there exists this algorithm and calculators really don’t use series, which he was surprised about

excellent video, glad I discover your channel. Hope to see more videos in the same style.

i found my own method for calculating cos(x) 1.choose accuracy n 2. divide the input number by 2^n-1 3.square the number and subtract 2from that 4. repeat 3 n times 5.divide the answer by two this works due to the double angle formula and chebesev polinomials

Thank you for this lesson. I learned something beyond my capability. You forgot to mention the software you use to make those circles and triangles.

I was disappointed that this did not receive a mention in the final announcement. I hope you continue to make videos though.

I'm not sure if I just missed it, but if to calculate inverse tangent you need to use this method and you need inverse tangent to use this method, how are the inverse tangents of 2^-n calculated?

In the old days, i calculated the Arctan in assembler using a the CORDIC. There is a mathematical proof of the CORDIC somewhere.

There’s a #SOME3 ??? i’m so excited?!!

A quicker way to prove convergence of the inverse tangent series: Note that tan^-1(x) < x for x > 0, therefore the sum of tan^-1(2^-n) is less than the sum of 2^-n, which is finite.

Excellent video.

12:08 Each term in the harmonic series is smaller than the one before, but it doesn't converge

This is a really nice video. I am excited about the content on this channel because it corresponds well to the content on my new channel. Your video is very professional and easy to understand - a feat considering the content. One quibble: the part about convergence misses a really important point - you need to cover all possible values. It turns out that the atan(.5^n) basis works, but not because the rate of converge is 0.5. For example, tan (pi/4*(.5^n)) would have the same asymptotic rate of convergence but leaves the range of computable values a Swiss cheese of holes. The property you need is sum of all remaining basis numbers must equal or exceed the last included basis number.

Everybody's gansta untill bro causally pulls up a home-made cpu to calculate the algorithm

Very awesome video! Education and funny!

This is insane. Love it!!

You deserve more subscribers

"How CAN computers compute (trig functions)" vs. "How DO computers ...". The hard real-time systems I worked on used Taylor Series approximation. 3 or 4 terms are adequte to achieve required accuracy (usually LSB).

I'd be curious if there are any hardware-based optimizations for this. For example, with multiplication, you don't have to add one number over and over again. You can instead AND the two values together several times simultaneously, each time at a different offset, which gives you 'partial products' in O(1) time. Then, you can have a series of 'reduction stages', where the partial products with the same place value are added together. Each reduction stage runs in O(1) as well, but you do need O(log(n)) reduction stages, and they do need to run in series. Finally, after the reduction stages, you're left with two numbers that you simply add together to get the final value. Because 1, generating the partial products is O(1); 2, you only need O(log(n)) reduction stages; and 3, the final adder can be implemented as a carry-lookahead adder (or other fast adder), which also runs in roughly O(log(n)), it's said that this brings multiplication's time complexity down to O(log(n)). As for how many gates it takes, that depends on how you build your reduction stages. If you use the Wallace method, you'll end up with fewer bits to add at the very end (making even a ripple-carry adder viable). However, you'll have a significantly higher number of total gates than if you use the Dadda method, which instead has more bits at the end to add up. A compromise is the 'Reduced Complexity Wallace' (or RCW) method. It's worth noting, however, that this doesn't mean that O(log(n)) computations are performed with this method, just that so many are done in parallel that the duration of time it takes to perform these computations is O(log(n)). However, using multidimensional wizardry, Joris van der Hoeven and David Harvey finally (announced in 2019, published in 2021) devised an algorithm for binary multiplication using only O(n log(n)) binary operations. This leads me to suspect they may not be human, but instead advanced transdimensional aliens who perceive time and space non-linearly. This would explain why their method isn't feasible with current manufacturing techniques, and would require a substrate with more than 3 spatial dimensions.

I wish you made this video a year ago, when I searched for them my first year of high school geometry At the start, you joked about being told that the answer was "wizard magic" but that is genuinely what I was told in school. Why does youtube have a better curriculum than the education system for math anyways oh, this is for SoME3. So I guess the answer to my question is 3B1B.

lets go SoME3!!!!

00:24 Very good!

Nice and informative video. However, this is not how modern computers compute trig functions. Multipliers (even floating point) are cheap and abundant. Few layers of small lookup tables combined with complex multiplication will give you a lot of angle resolution and precission. Or a small LUT + Chebyshev polinomial.

These graphics are beautiful. Were they made in Manim?

Very well done, thanks !

🥲 Very cool video. You explain well. Best wishes man.

Incredible video!

This video is AWESOME

Warning: unless you've had a Calculus II class (infinite series, product sums, l'Hopital's Rule, etc.), this will be over your head. Otherwise, this is a good video.

Very good Video really. But out of the eye of a newbie to Math and Computersince i would like to know why we need to do it this way. So why is this such a big problem for Computers in the first place ;) .

Hey Bobater, great job! I was wondering if any of this might help explain the super cool phenomenon of tan 89, tan 89.9, tan 89.99, etc. Why they keep going up by factors of 10 has always been something I've been curious about.

I think my main question at the end is how you determine if the current angle is more or less than the desired one. Do you have pre-computed arctan values for each power of two to add or subtract from the running total angle? P.S. While it wouldn't make any difference in the code since eliminating the identical expressions is an obvious optimization, the not-quite-rotation matrix used is pretty clearly a complex number on the Re(z) = 1 line. I just find it kind of funny when sine and cosine systems of equations show up and people immediately put them into a matrix rather than using the much shorter but equivalent complex number representation. It's also pretty easy to remember the angle-sum formula if Euler's formula is already provided just by using the standard power rule of a^(x+y) = (a^x)(a^y).

13:10 technically this statement is incorrect and the harmonic series is a popular counter example. Awesome video though!

Very interesting. Is that how scientific calculators do this kind of calculations? Like the venerable TI-30?

7:30, well multiplication speed is relative. In x86 floating point multiplication takes the same number of cycles as addition.

Nice Vid

Nice video! Awesome song choice.

This video is really really really mind-blowing

in practice, if you alredy have microcomputer capable of simple operations then you should use polynomial approximation of sin/cos up to 5th power for sine(3 terms) and 4th for cosine(constant + 2 terms). it is pretty fast and uses only couple multiplications and additions.

Be careful. It is of the most basic math level to know that a sum of a converging to 0 series does not always converge. Sum(1/x) does not converge.

You missed one last trick to eliminate that last multiplication that you did to correct for cosine term from all the iterations. You set the initial vector length to that number (0.6.....) rather than unity. As the iterations proceed, the vector length grows, ultimately reaching unity as the last iteration is done. Actually, only a finite number of iterations is done (this number must be fixed in order for the cosine correction term to be fixed) & the cosine correction is calculated for that number. You also do not mention memory requirements. You need working registers to store the present vector X & Y terms. Also required in ROM is the cosine correction value & a table of one angle for each iteration number. So ROM must contain N + 1 values, one for cosine & n for the iterations angles. This can get large. For example, for 16 iteration routine, you need storage for 17 constants, each of length to support precision of the calculation. You can save one iteration by reducing the angle range to one octet & folding the input angle into that. This also permits eliminating negative numbers from the calculation in the constants.

Thanks, really very nice, I love manim. One more clarification needed: I would expect K to depend on the number of iterations, not be constant. Do you store in memory a vector of the first, say, 10 K-Values?

Super interesting, I always wondered how CORDIC worked. Question, though, at 12:19, I'm not sure that the ratio of a[n+1]/a[n] is really sufficient to prove convergence, since the latter terms of the harmonic series (1/2 + 1/3 + 1/4 + ...) satisfies that test but still doesn't converge. Maybe I'm missing something though. Anyways, great video!

Good video 👍

So magic

Quick question. I was wondering if computers could use the complex plane to rotate points(by multiplying complex numbers), instead of using a rotation matrix. Is there a reason this isn't used?

While the CORDIC algorithm is undeniably neat, it is not the most efficient way to implement trigonometric functions on modern processors. Instead repeated fused-multiply-add instructions are used to evaluate polynomials that approximate the given function to very high accuracy. If you're using radians, the biggest challenge for sine and cosine, both with and without CORDIC, is the argument reduction, aka modulo π.

12:40 so that's why L'Hôspital's rule works!

I left this video pretty confused, and the example at the end left me mystified. The point of this whole thing, is that every matrix shown 15:00 to 16:00 is actually a matrix of just 1's 2' and other powers of 2. So this allows the bit shifting talked about earlier to come into play. I'm still not sure exactly what is getting bit shifted, or what is adding to what, but I'm closer.

12:32 To actually explain the ratio test, you need to appeal to the geometric series. 13:30 While I appreciate the attempt at motivating L' Hospital's Rule, you don't explain why both of the functions need to be zero at the limit point. Plus, dy/dy doesn't really make sense in your context. It's probably best just to quote the theorem.

sin(x) = x for small x. Done 😅

Ahhhh this video was so confusing! 1. At 7:18, you say that because we have the rotation matrix, "we have a way to rotate vectors and get their x and y coordinates after we rotate them" (correct) "...that gives us our sine and cosine" BUT the rotation matrix requires that we calculate sine and cosine! I don't understand why we're any better off at this point. 2. Was the motivation behind why we're adding successively smaller angles to an initial 45° ever explained? I don't see what doing that is giving us and I feel like it's probably a crucial part of this algorithm. Is it that you precalculate the terms of the summation AND their sines and cosines? Then you can just store those in a list and easily plug them into the rotation matrix? I appreciate the video but feel that this key point could have been explained a little more in depth.

Great video

Awesome, what do you use for the animation?

can you make one explaining how a logarithm is calculated? ive always wanted to know

How do you handle the accumulation of errors at each step? And how do you compute sin(z) where z is complex?

Grate video

I didn't understand how should we get tan(x) values? Have we a precalculated table of tan(45), tan(22.5) ... ?

It would have been easier to use Taylor series expansion for trig functions