How does the Cordic algorithm work to calculate Sine and Cosine?
In: 18
I’m going to explain a very similar algorithm first called Fast Exponentiation (FE), both Cordic and FE are very similar, in fact they both fall under the same category of algorithms we call “shift and add” algorithms, but CORDIC has a lot of red herrings compared to FE so we’re gonna go over this real quick to get an intuition. Still gonna be slightly complicated but hopefully this is at a level high school me could understand.
Suppose you had to figure out what 7^(43) was? How would you go about doing it, well without a calculator at least.
I mean you could multiply 7s together 43 times but that would be a waste, and gets pretty unreasonable pretty quick if you have to multiply even bigger numbers like 7^746373.
Well if you stared at the problem for long enough you would probably be able to mess with the rules of algebra to figure out a shortcut. And that shortcut is the exponent exponent addition rule, that a^x * a^y = a^(x + y) .
Instead of multiplying 7s together, we can multiply higher powers of 7s together that we already know in the process of going up to those higher powers and skip a lot of steps involved here. to get 7^4 we could multiply 7 * 7 * 7 * 7 or we could do this in two steps, multiply 7 * 7 to get 49 then multiply 49 * 49 to get 7^4 = 2401
And now it even takes us just one step to get 7^8 = 7^4 * 7^4 = 2401 * 2401 = 5764801. We can similarly find 7^16 , 7^32 and beyond.
To find 7^43 all we have to do is break this down into a product of powers of 7 that are multiplies of two, (in other words we have to find the binary decomposition of 43, not gonna get too deep into that, you can search this sub for that topic) and that would be 7^43 = 7^32 * 7^8 * 7^2 * 7^1
It takes us 5 multiplications to get all the powers of 7 we need for this, then 4 multiplications to “sum” them all together into 7^43, compared to multiplying 7 43 times this is really good, and it gets even better with bigger exponents. Computers have the added benefit of already storing all their numbers as binary decompositions (we store our numbers as say “4 tens and 3 1s,” computers store this as “one 32, one 8, one 2, one 1”), so we can just shift through the list of an exponents binary decompositions and add them up. Hence why we call these shift and add algorithms.
CORDIC works almost the same! In linear algebra we have a thing called a rotation matrix, each rotation matrix “rotates” vectors by whatever number of degrees the rotation matrix is designed to rotate, the actual values in the matrix are based off sine and cosine for that angle. Linear algebra allows us to “multiply” two matrices together which combines their effects, if we multiply two rotation matricies we get a third rotation matrix whose rotation angle is the sum of the last two. By adding a rotation matrix to itself we get the double rotation of that matrix!
If you want to avoid using linear algebra, you can actually just use the trig double angle and angle addition formulas for the same result (the formulas are actually derived from the rotation matrix’s properties), if you know sine and cosine for some angle, you can calculate the sine and cosine for double that same angle.
This gives us the add in the shift and add, except we have one big question, where do we start?
CORDIC computer programs are usually “bootstrapped” with a very small angle’s rotation matrix, usually a very small power of two, something like the angle 1/256 degrees or something, this is our minimum resolution for the angle. We take the binary decomposition of the angle we want to find, out all the powers of two that are in the angle, then we start doubling and “summing” to the biggest angle in the binary decomposition. And at the end we get the rotation matrix, from which we just extract sine and cosine.
And there you go, you your trig functions.
Latest Answers