# CORDIC Algorithm

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$