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.

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 was looking for resources on implementing my own trigonometry functions in C just for practice and this is perfect!

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

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.

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.

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

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

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

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

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

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.

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

Wonderful video!! please keep going!

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 awesome video! Education and funny!

This is insane. Love it!!

Thank you for the information.

Very well done, thanks !

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

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

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

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.

Nice video! Awesome song choice.

Excellent video.

Incredible video!

Now this is what I would like to actually like!

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

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

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

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.

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!

This video is AWESOME

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!

Impressive!

This is cool stuff. Highly advanced for rocket engineers.

Great video

You deserve more subscribers

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

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?

Good video 👍

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

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.

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

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.

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

awesome video! always wondered how these things worked

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

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

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

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?

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.

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.

Thanks.

lets go SoME3!!!!

Thats amazing work ❤

Nice Vid

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

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?

So magic

animations are great

New sub here! Very interesting video.

This video is really really really mind-blowing

Grate video

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.

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?

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.

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

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

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.

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

These graphics are beautiful. Were they made in Manim?

WOW!

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

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

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!

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

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

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

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

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.

ty )

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.

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

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

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

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