Hardware

The algorithm was used in the navigational system of the Apollo program's Lunar Roving Vehicle to compute bearing and range, or distance from the Lunar module.^[51][52] CORDIC was used to implement the Intel 8087 math coprocessor in 1980, avoiding the need to implement hardware multiplication.^[53]

CORDIC is generally faster than other approaches when a hardware multiplier is not available (e.g., a microcontroller), or when the number of gates required to implement the functions it supports should be minimized (e.g., in an FPGA or ASIC). In fact, CORDIC is a standard drop-in IP in FPGA development applications such as Vivado for Xilinx, while a power series implementation is not due to the specificity of such an IP, i.e. CORDIC can compute many different functions (general purpose) while a hardware multiplier configured to execute power series implementations can only compute the function it was designed for.

On the other hand, when a hardware multiplier is available (e.g., in a DSP microprocessor), table-lookup methods and power series are generally faster than CORDIC. In recent years, the CORDIC algorithm has been used extensively for various biomedical applications, especially in FPGA implementations.

The STM32G4 series and certain STM32H7 series of MCUs implement a CORDIC module to accelerate computations in various mixed signal applications such as graphics for human-machine interface and field oriented control of motors. While not as fast as a power series approximation, CORDIC is indeed faster than interpolating table based implementations such as the ones provided by the ARM CMSIS and C standard libraries.^[54] Though the results may be slightly less accurate as the CORDIC modules provided only achieve 20 bits of precision in the result. For example, most of the performance difference compared to the ARM implementation is due to the overhead of the interpolation algorithm, which achieves full floating point precision (24 bits) and can likely achieve relative error to that precision.^[55] Another benefit is that the CORDIC module is a coprocessor and can be run in parallel with other CPU tasks.

The issue with using Taylor series is that while they do provide small absolute error, they do not exhibit well behaved relative error.^[56] Other means of polynomial approximation, such as minimax optimization, may be used to control both kinds of error.

Software

Many older systems with integer-only CPUs have implemented CORDIC to varying extents as part of their IEEE floating-point libraries. As most modern general-purpose CPUs have floating-point registers with common operations such as add, subtract, multiply, divide, sine, cosine, square root, log₁₀, natural log, the need to implement CORDIC in them with software is nearly non-existent. Only microcontroller or special safety and time-constrained software applications would need to consider using CORDIC.

Rotation mode

CORDIC can be used to calculate a number of different functions. This explanation shows how to use CORDIC in rotation mode to calculate the sine and cosine of an angle, assuming that the desired angle is given in radians and represented in a fixed-point format. To determine the sine or cosine for an angle ${\displaystyle \beta }$, the y or x coordinate of a point on the unit circle corresponding to the desired angle must be found. Using CORDIC, one would start with the vector ${\displaystyle v_{0}}$:

${\displaystyle v_{0}={\begin{bmatrix}1\\0\end{bmatrix}}.}$

An illustration of the CORDIC algorithm in progress

In the first iteration, this vector is rotated 45° counterclockwise to get the vector ${\displaystyle v_{1}}$. Successive iterations rotate the vector in one or the other direction by size-decreasing steps, until the desired angle has been achieved. Each step angle is ${\displaystyle \gamma _{i}=\arctan {(2^{-i})}}$ for ${\displaystyle i=0,1,2,\dots }$.

More formally, every iteration calculates a rotation, which is performed by multiplying the vector ${\displaystyle v_{i}}$ with the rotation matrix ${\displaystyle R_{i}}$:

${\displaystyle v_{i+1}=R_{i}v_{i}.}$

The rotation matrix is given by

${\displaystyle R_{i}={\begin{bmatrix}\cos(\gamma _{i})&-\sin(\gamma _{i})\\\sin(\gamma _{i})&\cos(\gamma _{i})\end{bmatrix}}.}$

Using the following two trigonometric identities:

${\displaystyle {\begin{aligned}\cos(\gamma _{i})&={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})}}},\\\sin(\gamma _{i})&={\frac {\tan(\gamma _{i})}{\sqrt {1+\tan ^{2}(\gamma _{i})}}},\end{aligned}}}$

the rotation matrix becomes

${\displaystyle R_{i}={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})}}}{\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}.}$

The expression for the rotated vector ${\displaystyle v_{i+1}=R_{i}v_{i}}$ then becomes

${\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}={\frac {1}{\sqrt {1+\tan ^{2}(\gamma _{i})}}}{\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}},}$

where ${\displaystyle x_{i}}$ and ${\displaystyle y_{i}}$ are the components of ${\displaystyle v_{i}}$. Restricting the angles ${\displaystyle \gamma _{i}}$ such that ${\displaystyle \tan(\gamma _{i})=\pm 2^{-i}}$, the multiplication with the tangent can be replaced by a division by a power of two, which is efficiently done in digital computer hardware using a bit shift. The expression then becomes

${\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}=K_{i}{\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix}}{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}},}$

where

${\displaystyle K_{i}={\frac {1}{\sqrt {1+2^{-2i}}}},}$

and ${\displaystyle \sigma _{i}}$ is used to determine the direction of the rotation: if the angle ${\displaystyle \gamma _{i}}$ is positive, then ${\displaystyle \sigma _{i}}$ is +1, otherwise it is −1.

All ${\displaystyle K_{i}}$ factors can be ignored in the iterative process and then applied all at once afterwards with a scaling factor ${\displaystyle K(n)}$

${\displaystyle K(n)=\prod _{i=0}^{n-1}K_{i}=\prod _{i=0}^{n-1}{\frac {1}{\sqrt {1+2^{-2i}}}},}$

which is calculated in advance and stored in a table or as a single constant, if the number of iterations is fixed. This correction could also be made in advance, by scaling ${\displaystyle v_{0}}$ and hence saving a multiplication. Additionally, it can be noted that^[43]

${\displaystyle K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694}$

to allow further reduction of the algorithm's complexity. Some applications may avoid correcting for ${\displaystyle K}$ altogether, resulting in a processing gain ${\displaystyle A}$:^[57]

${\displaystyle A={\frac {1}{K}}=\lim _{n\to \infty }\prod _{i=0}^{n-1}{\sqrt {1+2^{-2i}}}\approx 1.64676025812107.}$

After a sufficient number of iterations, the vector's angle will be close to the wanted angle ${\displaystyle \beta }$. For most ordinary purposes, 40 iterations (n = 40) are sufficient to obtain the correct result to the 10th decimal place.

The only task left is to determine whether the rotation should be clockwise or counterclockwise at each iteration (choosing the value of ${\displaystyle \sigma }$). This is done by keeping track of how much the angle was rotated at each iteration and subtracting that from the wanted angle; then in order to get closer to the wanted angle ${\displaystyle \beta }$, if ${\displaystyle \beta _{n+1}}$ is positive, the rotation is clockwise, otherwise it is negative and the rotation is counterclockwise:

${\displaystyle \beta _{0}=\beta }$

${\displaystyle \beta _{i+1}=\beta _{i}-\sigma _{i}\gamma _{i},\quad \gamma _{i}=\arctan(2^{-i}).}$

The values of ${\displaystyle \gamma _{n}}$ must also be precomputed and stored. But for small angles, ${\displaystyle \arctan(\gamma _{n})=\gamma _{n}}$ in fixed-point representation, reducing table size.

As can be seen in the illustration above, the sine of the angle ${\displaystyle \beta }$ is the y coordinate of the final vector ${\displaystyle v_{n},}$ while the x coordinate is the cosine value.

Vectoring mode

The rotation-mode algorithm described above can rotate any vector (not only a unit vector aligned along the x axis) by an angle between −90° and +90°. Decisions on the direction of the rotation depend on ${\displaystyle \beta _{i}}$ being positive or negative.

The vectoring-mode of operation requires a slight modification of the algorithm. It starts with a vector whose x coordinate is positive whereas the y coordinate is arbitrary. Successive rotations have the goal of rotating the vector to the x axis (and therefore reducing the y coordinate to zero). At each step, the value of y determines the direction of the rotation. The final value of ${\displaystyle \beta _{i}}$ contains the total angle of rotation. The final value of x will be the magnitude of the original vector scaled by K. So, an obvious use of the vectoring mode is the transformation from rectangular to polar coordinates.

Software Example (Python)

from math import atan2, sqrt, sin, cos, radians

ITERS = 16
theta_table = [atan2(1, 2**i) for i in range(ITERS)]

def compute_K(n):
    """
    Compute K(n) for n = ITERS. This could also be
    stored as an explicit constant if ITERS above is fixed.
    """
    k = 1.0
    for i in range(n):
        k *= 1 / sqrt(1 + 2 ** (-2 * i))
    return k

def CORDIC(alpha, n):
    K_n = compute_K(n)
    theta = 0.0
    x = 1.0
    y = 0.0
    P2i = 1  # This will be 2**(-i) in the loop below
    for arc_tangent in theta_table:
        sigma = +1 if theta < alpha else -1
        theta += sigma * arc_tangent
        x, y = x - sigma * y * P2i, sigma * P2i * x + y
        P2i /= 2
    return x * K_n, y * K_n

if __name__ == "__main__":
    # Print a table of computed sines and cosines, from -90° to +90°, in steps of 15°,
    # comparing against the available math routines.
    print("  x       sin(x)     diff. sine     cos(x)    diff. cosine ")
    for x in range(-90, 91, 15):
        cos_x, sin_x = CORDIC(radians(x), ITERS)
        print(
            f"{x:+05.1f}°  {sin_x:+.8f} ({sin_x-sin(radians(x)):+.8f}) {cos_x:+.8f} ({cos_x-cos(radians(x)):+.8f})"
        )

$ python cordic.py
  x       sin(x)     diff. sine     cos(x)    diff. cosine
-90.0°  -1.00000000 (+0.00000000) -0.00001759 (-0.00001759)
-75.0°  -0.96592181 (+0.00000402) +0.25883404 (+0.00001499)
-60.0°  -0.86601812 (+0.00000729) +0.50001262 (+0.00001262)
-45.0°  -0.70711776 (-0.00001098) +0.70709580 (-0.00001098)
-30.0°  -0.50001262 (-0.00001262) +0.86601812 (-0.00000729)
-15.0°  -0.25883404 (-0.00001499) +0.96592181 (-0.00000402)
+00.0°  +0.00001759 (+0.00001759) +1.00000000 (-0.00000000)
+15.0°  +0.25883404 (+0.00001499) +0.96592181 (-0.00000402)
+30.0°  +0.50001262 (+0.00001262) +0.86601812 (-0.00000729)
+45.0°  +0.70709580 (-0.00001098) +0.70711776 (+0.00001098)
+60.0°  +0.86601812 (-0.00000729) +0.50001262 (+0.00001262)
+75.0°  +0.96592181 (-0.00000402) +0.25883404 (+0.00001499)
+90.0°  +1.00000000 (-0.00000000) -0.00001759 (-0.00001759)

Hardware example

The number of logic gates for the implementation of a CORDIC is roughly comparable to the number required for a multiplier as both require combinations of shifts and additions. The choice for a multiplier-based or CORDIC-based implementation will depend on the context. The multiplication of two complex numbers represented by their real and imaginary components (rectangular coordinates), for example, requires 4 multiplications, but could be realized by a single CORDIC operating on complex numbers represented by their polar coordinates, especially if the magnitude of the numbers is not relevant (multiplying a complex vector with a vector on the unit circle actually amounts to a rotation). CORDICs are often used in circuits for telecommunications such as digital down converters.