Using Computers to Compute: Calculating Sine and Cosine Using CORDIC

I will talk briefly about the following topics:

• What are sine and cosine?
• How do humans do math?
• How do simple computers do math?
• What is CORDIC?
• How does CORDIC work?
  • Including graphic examples

• It's fun
• Tau Day (6/28). Last month's meeting was a social, so this talk is late
• History of computing
• Math! Who doesn't like learning how to do math calculations?
  • Or at least having a computer spare us the work?

• If you haven't read Michael Hartl's Tau Manifesto, you should.
• tauday.com
• Makes understanding trigonometry much easier

• What are they?
• Trigonometry. Supposedly about Triangles.
• It's really about circles.

Unit Circle:

Circle of radius 1, centered at the origin, (0,0)

Theta (θ):

Angle pointing to point on a circle

Sine:

Vertical coordinate of point

Cosine:

Horizontal coordinate of point

• Fundamental math
• Used in very many engineering calculations
• Astronomy, Surveying, Navigation, Mechanics, Radio Engineering, Signal Processing
• Converting from rectangular to polar coordinates
• I won't even try to list all the uses

• Table books (printed spreadsheet)
• Slide rule (fancy lookup table)
• Pencil, paper
• Maybe even a protractor (for minimum accuracy)
• Did you spot the error in the previous slide?
  • \(sin \theta\) should have been 0.97029. Oops, I copied the wrong table value.

• By hand, with Taylor series like this: \[sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \frac{x^9}{9!} - \dots \] \[cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \frac{x^8}{8!} - \dots \]
  • That's a lot of multiplications!
    • Even after clever optimizations
    • We'll get back to that in a minute

• If you are stuck working with pencil and paper, this book has you covered.

• Okay, so we have calculators.
• But how do they work?

• Digital circuits exist to quickly calculate basic arithmetic operations
• Addition, subtraction, bitshift, etc.
• Bitshift is multiplication and division by powers of two only
• Arithmetic Logic Unit (ALU)

• Simple computers have no multiplication or division operators
• Why? Multiplication takes multiple steps (more time) and more transistors
• Division takes even more

• 4-bit ALU schematic, simplified
• Look at this thing
• You don't want to make this even more complicated by building a multiplier too, do you?

• Traditional methods of calculating sine and cosine require slow and expensive multiply circuits
• Can we calculate sine and cosine without multiply circuits?

• COordinate Rotation DIgital Computer
• Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, September 1959.

• Special purpose computer to demonstrate algorithm
• 96.5773 kHz clock frequency
• Built in 1960
• Led to CORDIC II built for the Air Force and B-58 bomber
• Replaced analog computers

• Uses only:
  • Addition
  • Subtraction
  • Bitshift
  • A small table look up
• No multiplications!
• Can be built with the simple ALU circuits

• Trigonometric identities:
  • Collections of mathematical facts collected over thousands of years
• Not obviously useful at first look, until you see one used well
• This is an example
• "Necessity is the mother of invention." –Jack Volder

• I'm sorry, but I didn't have time to create images for the following slides.
• We will all have to use our imaginations, or study this part later.
• There are animated examples at the end.

• Suppose you already know the coordinates of one point on the circle with angle \(\alpha\)
  • \(sin(\alpha)\) and \(cos(\alpha)\)
• What about another point a small angle away?
  • \(sin(\alpha+\theta)\) and \(cos(\alpha+\theta)\)

\[ sin(\alpha+\theta) = cos(\alpha) cos(\theta) - sin(\alpha) sin(\theta) \] \[ cos(\alpha+\theta) = sin(\alpha) cos(\theta) + cos(\alpha) sin(\theta) \]

• These equations rotate a known point around the circle

Coordinate Rotation:

\[ sin(\alpha+\theta) = cos(\alpha) cos(\theta) - sin(\alpha) sin(\theta) \] \[ cos(\alpha+\theta) = sin(\alpha) cos(\theta) + cos(\alpha) sin(\theta) \]

Or:

\[ x_{next} = x_{in} cos(\theta) - y_{in} sin(\theta) \] \[ y_{next} = y_{in} cos(\theta) + x_{in} sin(\theta) \]

In code:

x_next = x_in * cos(theta) - y_in * sin(theta)
y_next = y_in * cos(theta) + x_in * sin(theta)

• Graphics programmers might recognize this as an image rotation matrix

\[ P_{next} = \begin{bmatrix} x_{next} \\ y_{next} \end{bmatrix} = A P_{in}^T = \begin{bmatrix} cos \theta & -sin \theta \\ sin \theta & cos \theta \end{bmatrix} \begin{bmatrix} x_{in} \\ y_{in} \end{bmatrix}\]

Math trick: divide both sides of the equation by \(cos(\theta)\).

\[ \frac{x_{next}}{cos(\theta)} = x_{in} - y_{in} tan(\theta) \] \[ \frac{y_{next}}{cos(\theta)} = y_{in} + x_{in} tan(\theta) \]

In code:

x_next = x_in - y_in * tan(theta)
y_next = y_in + x_in * tan(theta)

x_next and y_next grow each time we do this (since \(cos(x)<1\)), but we can fix that later.

• So now we can easily add a fixed angle to any sine/cosine result and get a new point
  • If we know the arctangent of that angle
• We can move to any angle/point by repeatedly adding a small angle (say, one degree) to a starting point, until we have the angle we want
• Or, we can be smart about our increments: start big, and get smaller as we zero in on the answer

• Idea: start with a quarter rotation, then an eighth, a sixteenth, etc.
• Binary search!
• Need to be able to rotate both forward and backwards (we can)
• So, when our angle sum is higher than our target angle, rotate clockwise.

• Choose the angle of our successive jumps so that \(tan(\theta)\) is always a power of two

\[ \frac{x_{next}}{cos(\theta)} = x_{in} - y_{in} 2^{-i} \] \[ \frac{y_{next}}{cos(\theta)} = y_{in} + x_{in} 2^{-i} \]

In code:

x_next = x_in - (y_in >> i)
y_next = y_in + (x_in >> i)

• Our point's distance from the origin grows each iteration
• Start with a point inside the unit circle (K, 0)
• It will end up on the unit circle at the end
• I won't show the math for calculating K, but it isn't complicated

• The following examples show the CORDIC algorithm seeking the correct result
• In eight steps it gains eight bits of precision towards the correct answer (0.4% max error)
• Created with Dr. Geo geometry software
  • Uses Smalltalk language for scripting geometric figures

• Want to know more?