1959

CORDIC

Volder wrote this at Convair in the late fifties, to replace the analogue navigation computer in the B-58. The digital machine that would take its place had no multiplier, so the method could not use one. What is left is a table of sixteen arctangents, a shift, an add and a subtract, and a vector that walks to the answer by overshooting it and then correcting, sixteen times.

A sine, from shifts and adds and a table of sixteen angles

1 The table of arctangents, which is all the memory there is

Every entry is the arctangent of one over a power of two. That is the point: rotating by one of these angles needs a shift rather than a multiply, and nothing else is stored.

2 One rotation, by a shift and an add

Pick an angle. Each step shifts x and y right by the step number, then adds or subtracts, and takes the matching table entry off the angle that is left.

angle

3 The sequence, each step overshooting and the next correcting

The whole run. The angle left over is what decides the next direction, and it changes sign repeatedly: every rotation overshoots and the next one corrects. Numbers are in units of 1/65,536, because the arithmetic is integer throughout.

4 The gain, which every rotation multiplies in and the end divides out

A shift-and-add rotation is not quite a rotation: it stretches the vector a little each time. The stretch is the same for a given number of steps whatever the angle, so it can be dealt with once.

That is why the vector starts short rather than at one. The gain is divided out before the loop instead of after it, and the loop itself never divides.

These ran in this browser at load. The last one reads the rotation's own source and counts what is in it.

Each claim, whether it held, and the values behind it
claim	held	measured
the only table is arctangent of one over two to the i	yes	16 entries, largest 0.785398
sine and cosine stay inside the error the scale allows	yes	largest of 3201 sampled angles is 1.80e-4 at 0.85 degrees, against a bound of 2.75e-4
the rotations overshoot and are corrected, rather than creeping up	yes	11 direction changes in 16 steps
the angle left over shrinks to about the smallest table entry	yes	residual 0.00e+0, smallest step 3.05e-5
the gain depends only on how many steps, not on the angle	yes	K = 1.6467602579
there is no multiplication in the rotation, only shifts and adds	yes	2 shifts, 0 multiplications
the furthest it can reach is the sum of its own table, and the page stays inside it	yes	reaches 99.88 degrees; the control offers 80

What is real here, and what is not

The arithmetic really is integer, and that took a rewrite

x, y and the angle are integers scaled by 65,536, the shifts are right-shifts and the direction is a branch. The first version of this page held them as ordinary numbers and wrote the rotation as x minus d times y times two to the minus i, which is three multiplications wearing a shift's clothes. The page claims the algorithm needs no multiplier, so the page must not use one, and the check at the foot of the last panel reads the rotation and counts.

Sixteen steps, and how far the answer can be out

x, y and the angle are integers scaled by 65,536, so the arithmetic is exact and the error is quantisation. Each step shifts x and y right and loses up to one unit of that scale, and what is left of the angle when the table runs out is at most the smallest angle in it, so the error cannot exceed sixteen units plus that remainder. The table at the foot of the page checks that bound and prints the largest error it found among the angles it tried. That number is a sample and is labelled as one: it read 9.3e-5 when the sweep stepped a degree at a time, 1.35e-4 at half a degree and 1.80e-4 at a twentieth, which measured how hard the check was looking rather than how accurate the machine is. The rotation only sees the angle as an integer, so there are 183,013 of them across the range this page offers and the tests try every one. The worst is 1.90408e-4, at 4.8146 degrees, which no sweep here ever landed on.

Rotation mode only, and one quadrant of it

This is CORDIC in rotation mode: given an angle, produce sine and cosine. Vectoring mode, which goes the other way, is not here, nor are the hyperbolic and linear variants that give logarithms, exponentials and multiplication itself. The convergence range is limited to the sum of the table's own angles, which this page computes rather than quotes: about 99.9 degrees. The control offers 80, comfortably inside it.

No sound

Nothing here has a duration to hear.

Sources

Logical Art builds interactive explanations of difficult machines.

The machines:

1935-1991 RangekeeperThe answer is on both sides of the equation, so it had to be a machine.
1964-1990s AbendThe loop you did not write, and the day it cost to get it wrong.
1971-1995 Line ModeYou could telnet to port 80 and be the browser, and then you could not.
1975 Front PanelA working 1975 Altair 8800 you program by flipping switches.
1980s 300 BaudA real dial-up modem and the BBS on the other end of it.
1994 WinsockThe two seconds after the modem stopped screeching, before anything worked.
2020s LLM LabTrain a tiny language model and watch every number as it learns.

Smaller pieces, on the studio itself: Morse, Baudot, Flip-Flop, Punch Cards, Interlace, Bitwise, The Adder, Stored Program, Two's Complement, Trigger, Bit, Nibble, Byte, Transistor, Score Reel, Hamming, Huffman, Core Memory, Hash Table, The Interrupt, CORDIC, CRC, Page Fault, ASCII, CPU Cache, Race, Fifteen Planes, B-tree, Backoff, Checkout, Diffie-Hellman, Zero Address, Fringes, LZ77, Signature, Z-Characters, Merkle Proof, Branch Prediction, Write-Ahead Log, Interleave, Eight Sprites, DNS, Floating Point, Slow Start, Longest Chain, JPEG, UTF-8, Masking, PageRank, Merge Collapse, Merkle DAG, Count Distinct.

A Logical Art machine by RoamingPigs, Inc. Built by Cisco Caceres in Las Vegas, NV.