Mechanism · a hard thing done with only shift, add, and a sign

The Sine That Never Multiplied

A pocket calculator finds the sine of an angle without ever multiplying two numbers together. It walks a single vector through a fixed ladder of ever-halving angles — arctan 1, arctan ½, arctan ¼ — and at each rung it does only three things a chip finds trivial: shift some bits, add, and choose a sign. That is CORDIC. Watch it work, watch why its magic constant never changes, then flip one parameter and turn the same machine into a circle, a straight line, or a hyperbola.

In 1959 Jack Volder needed to compute trigonometry aboard a B-58 bomber, in real time, with 1950s hardware that had no multiplier worth the name — just shifters and adders. His answer, the COordinate Rotation DIgital Computer, is still how a great deal of silicon computes sines today. The idea is almost impudent: to rotate a vector by some target angle θ, don't rotate it by θ. Rotate it by arctan 1 = 45°. Overshot? Rotate back by arctan ½ ≈ 26.57°. Still not there? Forward by arctan ¼ ≈ 14.04°. Each rung is half-ish the last, so the running total zeroes in on θ like a scale balancing — a binary search across the arc.

The reason those particular angles were chosen — the arctangents of 2⁻ⁱ — is the whole trick. Rotating by an angle whose tangent is exactly 2⁻ⁱ means the rotation's arithmetic collapses into a bit-shift. A true rotation multiplies by a 2×2 matrix full of sines and cosines. CORDIC's rotation multiplies by 2⁻ⁱ — which, in binary, is just "move the point i places right." No multiplier required.

§1 · The ladder

A fixed table of angles, computed once

Every CORDIC machine carries one small read-only table: the arctangents of the negative powers of two. Here are the first rungs (recomputed live, below), beside the length each rung stretches the vector — hold onto that second column, it is the secret of the whole method.

Add every rung and you get the farthest angle a bare CORDIC can reach: Σ arctan 2⁻ⁱ = 1.743 rad ≈ 99.88°. Ask for more than that and you must first fold the angle into a quadrant (the calculator does; our instrument stays inside the honest range). Now let it run.

§2 · The instrument

Watch one vector zig-zag onto the circle

Set a target angle. The vector starts pointing along the x-axis, at a peculiar length K = 0.6073… we will explain in a moment. Then it takes N pseudo-rotations, each time turning toward θ if it is short of it, away if it has overshot — the + and − choices below. After enough steps the tip lands, to full precision, on the unit circle at exactly (cos θ, sin θ). No sine was ever looked up; it fell out of the rotations.

That is the entire algorithm. Three integer operations per step — a shift, an add or subtract, and reading one sign bit — repeated a couple of dozen times. Nothing that deserves to be called a multiply. But two things should nag: why does the vector start at that strange length K, and why does K never depend on the angle you asked for? That constant is doing something, and it is the hinge the whole method turns on.

§3 · The payload

Why the gain K never changes

Here is the sleight of hand. A true rotation by angle α keeps the vector's length exactly the same. CORDIC's step does not. When it "rotates" by using tan α = 2⁻ⁱ, it quietly skips the cos α that a real rotation carries — so each step is a rotation and a stretch. This is why it is called a pseudo-rotation. The step is:

Ask how much longer the vector got. Square the new length and expand — this is the one calculation that matters on this whole page:

Look at what the sign d does and does not touch. It appears only in the two red cross-terms — and those are equal and opposite, so they cancel for d = +1 and for d = −1 alike (all that matters is d² = 1). What survives, the stretch factor √(1+2⁻²ⁱ), is set by the shift magnitude i alone. The sign steers the angle; it has no vote on the length.

So over N steps the vector's length is multiplied by the same product no matter what angle you steered toward — a fixed number. Its reciprocal is K. Start the vector at length K and the accumulated stretch lands it back at length exactly 1, on the unit circle, where its coordinates are the cosine and sine. Below: pick a rung i and a vector, and see the same stretch land the + step and the − step on the identical dashed circle — different directions, one radius.

And here is K assembling itself. The running product of the stretch factors converges to the total gain A = 1/K; its reciprocal settles onto the constant every CORDIC chip stores. Tied to the same iteration count N as the instrument above:

§4 · The honest floor

One bit per step — until it isn't

The folklore says CORDIC gains "about one bit of accuracy per iteration," and the sloped part of the curve below shows exactly that: each rung roughly halves the error. But the folklore stops too soon. The angle table and the running arithmetic are themselves only stored to finite precision, so past a certain point new iterations stop buying anything — the error flattens, and in double precision it even bounces around a floor near 10⁻⁹. More steps is not more truth forever. Drag N and watch the marker walk down the slope and then wander along the floor.

This flattening is not a flaw to hide — it is the honest shape of every iterative method, and naming it is the difference between a demo and the truth. A hardware designer reads this curve backwards: to guarantee b good bits, run about b iterations and store the table to a couple of guard bits beyond that. The cost is linear in the number of result bits — which, in a moment, is exactly why CORDIC lost the general-purpose CPU.

§5 · The flagship

One machine, three geometries

Everything so far was Volder's 1959 circular CORDIC. Twelve years later, John Walther at Hewlett-Packard noticed that the identical shift-add-sign iteration — change nothing but one sign in the update and swap the little angle table — computes an entire library of functions, not just sine. He added a single parameter m:

The quantity the iteration secretly conserves is x² + m·y². Set m = +1 and that is a circle — sine, cosine, arctangent. Set m = 0 and the conserved shape degenerates to a straight line — and the machine multiplies and divides. Set m = −1 and it is a hyperbola — giving exp, ln, √, and the hyperbolic functions. Same rotations. Same silicon. Flip m and watch the point walk a different curve.

The hyperbolic mode hides one genuine wrinkle, and the instrument honours it rather than fudging it: not every rung converges on the first pass. Iterations 4, 13, 40, 121, … (each 3k+1 after the last) must be repeated, or exp and ln silently drift. You can see the doubled rows in the trace table above when m = −1. That is the sort of detail a one-paragraph "CORDIC rotates a vector" tutorial never mentions — and the reason the verifier for this page tests convergence with and without the repeats.

This unification is the answer to the sophisticated dismissal — "CORDIC is a museum piece; real processors just evaluate polynomials." The depth of CORDIC was never the sine. It was that one tiny state machine, by swapping a table and a sign, spans trigonometry, exponentials, logarithms, multiplication, division and square roots. Which is why it never left the places where multipliers are expensive or absent: FPGAs and ASICs, DSP blocks, and dedicated units like the CORDIC coprocessor STMicroelectronics still ships inside its STM32 chips.

§6 · The relative

The other way to make a transcendental cheap

There is a rival trick, and setting the two side by side sharpens what CORDIC is. In 1962 — three years after Volder — John Mitchell showed you can multiply and divide by faking a logarithm: because a binary number's position already is roughly its log₂, you can approximate the log by counting and shifting bits, add instead of multiply, then shift back. The most famous descendant of that idea is the fast inverse square root from Quake III: reinterpret a float's raw bits as an integer and you have log₂ for free, already sitting in the exponent field.

Both families make transcendentals cheap, and both, at bottom, exploit the logarithm — but by opposite mechanisms. The bit-log trick is a single, one-shot reinterpretation: read the bits differently and the log is just there, no loop, at the cost of a fixed few percent of error. CORDIC is iterative accumulation: it never reinterprets anything; it grinds out one more correct bit per rung by tabulated rotation, as accurate as you are patient. One reads a logarithm the hardware already wrote down; the other builds an answer up from rotations. Kin in spirit, opposite in method — which is why they win in different places.