How does the Cordic algorithm work to calculate Sine and Cosine?

Question

How does the Cordic algorithm work to calculate Sine and Cosine?

In: 18

Answer 1

First, let’s recall the dichotomic method (also named binary search). It seems unrelated, but this algorithm starts with a variant of it.

Let’s take a simple example for the dichotomic method: searching a word in a dictionary.

* The method states that first you should open the dictionary at 1/2, and then you compare your word to the current page, and make a jump of 1/4 “in the good direction”. Said otherwise If it is before alphabetically you now open at 1/4, otherwise at 3/4.

* You compare again and now make a jump of 1/8 in the good direction, so depending on the result you will open it at 1/8 or 3/8 in the former case, and 5/8 or 7/8 in the latter case.

* And you continue by making smaller and smaller jumps: 1/16, 1/32, etc

* Eventually, you’ll end up at the good page. And while this method is not always practical for a human, it’s the most efficient one for a computer.

So what’s the link between this method and computing sines and cosines? Well, that’s because the method approximate the angle in a similar way. It makes jumps of size arctan(1), then arctan(1/2), then arctan(1/4), then arctan(1/8), … up until it’s near enough from the intended angle.

(Those values for arctan(theta) are pre-computed and included in the algorithm. Usually, you only need to pre-compute like 20 maybe 30 of them to get a good enough algorithm.)

At each steps, it updates values of the sine and cosine of this approximated angle. This is done through mathematical formula that link “making a rotation of angle arctan(theta)” and “modifying the cosine and sine in a certain way”.

(Those mathematical formula are the reason why the jumps are things like arctan(1/8) and not just 1/8. Fortunately, this small change does not break the dichotomic method due to some nice properties of the arctan function.)

And since sin and cosin are continuous function will small derivatives, approximating the angle and giving the sin and cosin of this approximation will actually give a good approximation of the sin and cosin of the intended angle.