CORDIC: trigonometry with nothing but shifts and adds

Here is a claim that sounds impossible: you can compute sine, cosine, arctangent and vector magnitude, all the transcendental trigonometry, using only shifts, adds, and a tiny table of constants. No multiplier at all. On an FPGA, where a hardware multiplier (a DSP slice) is a limited and precious resource, that is close to magic. It is the same delight as a look-up table becoming a neuron: choose your primitives cleverly and the expensive operation simply disappears.

The trick is called CORDIC, and it is not new. Jack Volder invented it in 1959 for the navigation computer of the B-58 bomber, to replace spinning analog resolvers. Hewlett-Packard put it inside the HP-35 in 1972, the first scientific pocket calculator, so it could do trig with no room for a multiplier. Whenever a small machine has needed transcendental functions on a tight hardware budget, CORDIC has been the answer. On an FPGA it still is.

The one idea: a rotation is a multiply, until you pick clever angles

Rotate a point (x, y) by an angle theta:

x' = x*cos(theta) - y*sin(theta)
y' = y*cos(theta) + x*sin(theta)

Pull cos(theta) out of both lines:

x' = cos(theta) * (x - y*tan(theta))
y' = cos(theta) * (y + x*tan(theta))

The multiplies are hiding inside tan(theta). Now the move that makes it all collapse: only ever rotate by angles whose tangent is a power of two. Choose theta_i = atan(2^-i), so tan(theta_i) = 2^-i, and "multiply by the tangent" becomes "shift right by i". A shift on an FPGA is free, it is just wiring.

So instead of rotating by the target angle in one impossible step, you build it up out of these fixed rotations, adding or subtracting each one to steer toward where you want to be. The first swing overshoots, the next comes halfway back, and each is smaller than the last, so the vector zeroes in on the target angle.

The iteration

That homing-in is the whole algorithm. At each step, look at how much angle is left to go and rotate by the next atan(2^-i) in the right direction:

x[i+1] = x[i] - d*(y[i] >> i)
y[i+1] = y[i] + d*(x[i] >> i)
z[i+1] = z[i] - d*atan(2^-i)     // z tracks the angle still to rotate

d is just +1 or -1, the direction, picked from the sign of z[i] so the remaining angle is always driven toward zero. The atan(2^-i) values are constants living in a tiny ROM. That is the entire engine: two shifts, three adds, and one table lookup per step. There is no multiplier anywhere in it.

The gain (there is always a catch)

We factored cos(theta_i) out of every step but never actually multiplied it back in. Those forgotten cosines pile up into a single constant scale, the CORDIC gain:

K = product of cos(atan(2^-i)) over all i  ~=  0.6073

It converges to about 0.60725, so the output vector ends up longer than the input by 1/K ~= 1.6468. You deal with it for free: start the vector at x0 = K instead of 1, and the answer falls out unit-length. It is one fixed number you bake in once and forget.

Two modes, one engine

Steer the iterations two different ways and the very same hardware solves two different problems:

Rotation mode drives the angle z to zero. Feed in (K, 0, theta) and out come cos(theta) and sin(theta), both at the same time.
Vectoring mode drives y to zero instead. Now the accumulated angle is atan2(y, x) and the surviving x is the vector magnitude. Rectangular to polar, in the same gates.

And it stretches further than trig. Swap in a different set of shift angles and a hyperbolic mode computes exp, ln, sinh, cosh and square root; a linear mode does plain multiply and divide. CORDIC is less a single algorithm than a small math library folded into one repeating datapath.

Why FPGAs love it

On a CPU you would just call sinf() and move on. On an FPGA you have two honest choices for trig, and CORDIC is the better third one. A big lookup table is fast but eats block RAM and is only as fine as its address width. A polynomial approximation is accurate but spends your scarce DSP multipliers. CORDIC fits the fabric like it was made for it:

No multiplier. Shifts are wiring and adds are cheap, so your DSP slices stay free for the actual signal path.
Deterministic and pipelineable. Unroll the N iterations into N hardware stages and you get one result every clock at a fixed N-cycle latency, the spatial-computing sweet spot. Each stage is only a pair of adders, so the pipeline clocks fast.
Precision is a dial. You get roughly one bit of accuracy per iteration, so N iterations buys about N bits. Choose the width you need and stop, the same "precision as a design knob" idea. It is all fixed-point, so our Qm.n converter earns its keep here.

One caveat worth knowing: the rotations converge for angles up to about 99.7 degrees, comfortably past a right angle. For anything outside that, a coarse plus-or-minus 90 degree pre-rotation (which is just swapping x and y and negating, still free) folds any angle back into range first.

Fourteen adders, four correct decimals

Here is a complete 16-bit rotation-mode CORDIC (Q2.14 fixed-point, 14 iterations). Press Run: it computes the cosine and sine of 30 degrees, and in the waveform you can watch x, y and z step and converge over the iterations.

The result: cos(30) = 0.86615 against the true 0.86603, and sin(30) = 0.49982 against 0.5. About four correct decimal places, out of fourteen shift-and-add steps and a table of fourteen constants. Want more bits? Add more iterations. There are no multipliers to add.

The takeaway

CORDIC teaches a lesson that keeps paying off: the expensive operation is rarely fundamental. It is a consequence of the primitives you allow yourself. Restrict the rotations to angles whose tangent is a power of two and the multiplier evaporates, exactly as restricting weights to plus-or-minus one turns a neuron into an XNOR. An FPGA is a sea of shifts, adds and small tables, and it was shaped for precisely this kind of cleverness. Sine and cosine, built from nothing but wires that move bits sideways.