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.

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

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

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

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

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

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

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

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.

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

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.

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

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!).

Wonderful video!! please keep going!

This is insane. Love it!!

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

I've been trying to find this. Thanks!

Very well done, thanks !

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.

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

Very awesome video! Education and funny!

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

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

Now this is what I would like to actually like!

Thank you for the information.

Incredible video!

Nice video! Awesome song choice.

Excellent video.

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

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

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.

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...

This video is AWESOME

Impressive!

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!

Great video

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

You deserve more subscribers

This is cool stuff. Highly advanced for rocket engineers.

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!

lets go SoME3!!!!

2:50 would it increase accuracy to split it into four quadrants each centered on an axis? (like +45 to -45, not 0 to 90) or would it simply make 90 degrees representable and nothing else?

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.

awesome video! always wondered how these things worked

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.

Good video 👍

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

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

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

is it the algorythm used by the math C library on cpus that do not have hadware acceleration of theses functions ? sin and cos are still pretty slow on small cpu like on 8bit arduinos. BTW It seems to me that modern cpu (after intel "Core" microarchitecture on PC) have an assembly instruction that do both sin and cos at the same time and also really fast. I think it's using hard-wired lookup tables and maybe linear interpolation. In fact i do not really know how they do it so fast and I would be interested if you could explain it the same way you did for CORDIC.

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?

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.

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.

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

Thanks.

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

Nice Vid

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.

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

00:24 Very good!

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

New sub here! Very interesting video.

Thats amazing work ❤

These graphics are beautiful. Were they made in Manim?

animations are great

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.

So magic

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.

Grate video

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?

"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).

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

How do you compute the atan(1/2^n) ?

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

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.

how do you keep track of what theta is in order to compare it to the target angle? i understand how you track the x and y coordinates, but not the angle.

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

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

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?

Awesome, what do you use for the animation?

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!

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.

But do any calculators use the taylor series expansion? I mean, before CORDIC, were taylor series used?

Do we precalculate the tan values like this ? tan(45) = 1 tan(26.565) = 1/2 tan(14.036) = 1/4 tan(7.1250) = 1/8 tan(3.5763) = 1/16 tan(1.7899) = 1/32 tan(0.8951) = 1/64 tan(0.4476) = 1/128 tan(0.2238) = 1/256 tan(0.1119) = 1/512

CORDIC rotations first used in HP35 calculator?

This video is really really really mind-blowing

I am currently studying trigonometry and matrix, and both topics suddenly appear on my feed.

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

If K is constant, start at (K,0) and remove one multiplication.

WOW!

I have a question how do u know when to rotate a vector backwards or forward, (substract and add the angle) EDIT: actually this sounds kinda dumb, since u can check if the currentAngle is bigger or smaller then the desiredAngle and add/substract the next iteration of the angle