CORDIC Algorithm

cordic

Unlike a common belief, most calculators do not use Taylor series to compute trigonometric functions, but the much more efficient CORDIC algorithm, namely COordinate Rotation DIgital Computer. It was developed by Volder in 1959 although the ideas can already be found in the work of Briggs in the XVIIth century.

How to efficiently approximate \tan \theta \textrm{ for } \theta \in [ 0 ; \frac{\pi}{2}[ ?

ROTATION SEQUENCE

Let (X,Y) be a point on the trigonometric circle such that \tan \theta = \frac{Y}{X}. Let (X_0 , Y_0) = ( 1 , 0 ) be an initial point on the same circle. The idea consists of applying a sequence of rotations of angles \theta_i to approximate (X , Y). The sequence of angles must be decreasing such that \theta_{i+1} \leq \theta_{i} and we will see below that their values can be precomputed.

\displaystyle (X,Y) \simeq R_{n} \cdot R_{n-1} \cdots R_{0} \cdot (X_0,Y_0)

Recursively :

\displaystyle \left( \begin{array}{c} X_{i+1} \\ Y_{i+1} \end{array} \right) = \left( \begin{array}{cc} \cos \theta_i & - sin\theta_i \\ \sin \theta_i & \cos \theta_i \end{array} \right) \left( \begin{array}{c} X_{i} \\ Y_{i} \end{array}\right)

\displaystyle \left\{ \begin{array}{c} X_{i+1} = X_{i} \cos \theta_{i} - Y_{i} \sin \theta_{i} \\ Y_{i+1} = X_{i} \sin \theta_{i} + Y_{i} \cos \theta_{i} \end{array} \right.

We can factorize by \cos \theta_i

\displaystyle \left\{ \begin{array}{c} X_{i+1} = \cos \theta_{i} ( X_{i} - Y_{i} \tan \theta_{i} ) \\ Y_{i+1} = \cos \theta_{i} ( X_{i} \tan \theta_{i} + Y_{i} ) \end{array} \right.

FACTORIZATION

In order to optimize the calculations, we inject \cos \theta_{i} into the product of rotations and redefine the problem as follows

\displaystyle (X,Y) \simeq \cos \theta_{n} \cdot \cos \theta_{n-1} \cdots \cos \theta_{0} \cdot R_{n} \cdot R_{n-1} \cdots R_{0} \cdot (X_0,Y_0)

\displaystyle \left\{ \begin{array}{c} X_{i+1} = X_{i} - Y_{i} \tan \theta_{i} \\ Y_{i+1} = X_{i} \tan \theta_{i} + Y_{i} \end{array} \right.

It is worth to notice that the product of cosines disappears in the ratio Y/X, so it can be ignored in the algorithm.

CHOOSING ANGLES

Now, the smart idea consists of choosing

\displaystyle \tan \theta_{i} = 10^{- k_i} \textrm{ with } k_i \in \mathbb{N}

In this way, we have very simple formulas

\displaystyle \left\{ \begin{array}{c} X_{i+1} = X_{i} - Y_{i} 10^{- k_i} \\ Y_{i+1} = X_{i} 10^{- k_i} + Y_{i} \end{array} \right.

All these operations are easy and fast to compute. It suffices to precompute \arctan 10^{- k} in memory. The choice of 10^{- k} can actually be  replaced by 2^{- k} to optimize the binary representation on computers.

ALGORITHM

precompute \alpha_{k} = \arctan 10^{- k}

k \leftarrow 0

while \theta \geq \epsilon

while \theta < \alpha_{k}

k \leftarrow k + 1

end

\theta \leftarrow \theta - \alpha_{k}

X' \leftarrow X

X \leftarrow X - Y \cdot 10^{- k}

Y \leftarrow Y + X' \cdot 10^{- k}

end

return Y / X

Advertisements

3 thoughts on “CORDIC Algorithm

  1. David says:

    I love your blog. I found it when my physics class asked me to do something similar to the problem of Dido, and every entry has been quite interesting.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s