Dictionary of Mathematical Eponymy: Volder’s algorithm

One of the questions that occasionally crops up in the hive of scum and villainy I hang out in search of problems to solve is, “how do calculators work out trigonometric values?”.

It’s not, typically, the way that the Mathematical Ninja would (find an angle nearby and adjust using heuristics), but it’s not all that far away. The method a calculator typically uses is known as CORDIC1 or - at least for the purposes of this dictionary, Volder’s algorithm.

What is Volder’s Algorithm?

The principle of Volder’s algorithm is to rotate a vector on the unit circle by progressively smaller angles in either direction until it reaches the angle you’re interested in.

So far, so obvious - that’s basically what the Ninja does.

The clever bit is picking angles - and the corresponding rotation matrix - so that the calculation is straightforward.

Your standard angular rotation matrix looks like this: $\mattwotwo{\cos(\Theta)}{-\sin(\Theta)}{\sin(\Theta)}{\cos(\Theta)}$ - but that rather begs the question. However, there’s a nice pair of identities that helps here:

  • $\sin(\theta) \equiv \frac{\tan(\theta)}{\sqrt{1 + \tan^2(\theta)}}$
  • $\cos(\theta) \equiv \frac{1}{\sqrt{1 + \tan^2(\theta)}}$

This turns the rotation matrix into $\frac{1}{\sqrt{1+\tan^2(\theta)}} \mattwotwo{1}{-\tan(\theta)}{\tan(\theta)}{1}$

And if we pick $\theta$ so that $\tan(\theta)$ is a (non-positive integer) power of 2, we can make use of the fact that computers can multiply by such numbers almost instantaneously using bit shifts. And in particular, if we start by moving by $\arctan\left( 2^0 \right)$ in the correct direction, then $\arctan\left( 2^{-1} \right)$, and so on, we can get as close as we like to the angle we want - and, probably the neatest thing - the factors in front of the rotation matrix, the $\frac{1}{\sqrt{1+\tan^2(\theta)}}$s, are the same set of values, no matter what angle we pick.

The only wrinkles, then, are:

  • keeping track of how far you’ve rotated so far (which is just a case of working out ahead of time what $\arctan\left(2^{-k}\right)$ is for as many values as you fancy using);
  • keeping track of the product of the constant factors in front of the matrix - which, again, you can work out ahead of time.

At the end of the series of (very quick to compute) rotations, the vector you wind up with is $\colvectwo{\cos(\theta)}{\sin(\theta)}$, or as close to it as you could possibly want.

Why is it important?

The motivation for Volder’s algorithm came from aircraft manufacturing: the B-58 bomber’s navigation computer relied on an analogue resolver, and needed to be replaced by an accurate electronic version. Seeing as this was the 1950s and computers were generally comparable in size to planes2, hardware efficiency and speed were of the essence - and a shift-and-add system like this hits both of the goals nicely.

Variations on it were soon implemented for other useful functions, such as square roots, logarithms and hyperbolic functions, and formed the basis for hand-held calculation devices for many years.

Who was Jack E. Volder?

Volder is another largely mysterious mathematician. He was born in Fort Worth, Texas in 1924 and graduated from Texas Technological College in 1949 before moving into aircraft equipment design, at first in Wisconsin and then back in Texas.

He died in Yorba Linda, California, in 2013.

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

  1. CO-ordinate Rotation DIgital Computer []
  2. and just as prone to crashing []

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter