Notation
Symbol Meaning \(x_i, y_i\) the coordinates after step \(i\); scalars are in ordinary italics \(\hat\alpha_i\) the angle estimate held by the accumulator after step \(i\), starting from \(\hat\alpha_0=0\) \(\alpha\) the true angle of the input vector, \(\alpha=\arctan(y_0/x_0)\), in radians
CORDIC (COordinate Rotation DIgital Computer) is an iterative method that recovers the angle and amplitude of a vector based on shifts and additions. Without loss of generality, we define
\[\arctan\frac{y_0}{x_0} \in \left[0,\ \frac{\pi}{2} \right), \qquad x_0>0, \qquad y_0\ge0\]The idea behind CORDIC is to rotate the vector onto the real axis with a sequence of fixed angles:
\[\theta_i=\arctan(2^{-i}), \qquad i=0,1,2,\dots\]Note that the tangent of \(\theta_i\) is \(2^{-i}\), so shifting can be used instead of multiplication.
2. The iteration
2.1 The recurrence
Rotating the vector by \(\theta_i\), we obtain
\[\begin{bmatrix} x_{i+1} \\ y_{i+1} \end{bmatrix} = \begin{bmatrix} \cos\theta_i & -\sin\theta_i \\ \sin\theta_i & \cos\theta_i \end{bmatrix} \begin{bmatrix} x_i \\ y_i \end{bmatrix} = \cos\theta_i \begin{bmatrix} x_i - \sigma_i 2^{-i} y_i \\ \sigma_i 2^{-i} x_i + y_i \end{bmatrix}\]where
\[\sigma_i = \begin{cases} -1, & y_i\ge0 \\ +1, & y_i<0 \end{cases}\]selects the direction.
The iteration process of the angle is
\[\begin{cases} x_{i+1} = x_i - \sigma_i 2^{-i} y_i \\ y_{i+1} = y_i + \sigma_i 2^{-i} x_i \\ \hat\alpha_{i+1} = \hat\alpha_i - \sigma_i \theta_i \end{cases}\]where \(\hat\alpha_{0} = 0\).
The factor for one step is
\[\cos\theta_i = \frac{1}{\sqrt{1+\tan^2\theta_i}} = \frac{1}{\sqrt{1+2^{-2i}}}\]The factor \(\cos\theta_i\) is discarded at every step. Hence, the gain after \(n\) steps is
\[K_n = \prod_{i=0}^{n-1}\frac{1}{\cos\theta_i}\]After \(n\) steps the nominal vector is therefore the input rotated through the accumulated angle and scaled by that gain:
\[\begin{bmatrix} x_n \\ y_n \end{bmatrix} = K_n \begin{bmatrix} \cos\Phi & -\sin\Phi \\ \sin\Phi & \cos\Phi \end{bmatrix} \begin{bmatrix} x_0 \\ y_0 \end{bmatrix}, \qquad \Phi=\sum_{i=0}^{n-1}\sigma_i\theta_i\]where \(\Phi\) is the total angle actually turned. The limit of the gain is
\[K_\infty = \prod_{i\ge0}\sqrt{1+2^{-2i}} = 1.6467602581\ldots\]