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 CORDIC ¹ 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: $\left(\begin{array}{cc}\cos (\theta )& -\sin (\theta )\\ \sin (\theta )& \cos (\theta )\end{array}\right)$ - 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 )}}\left(\begin{array}{cc}1& -\tan (\theta )\\ \tan (\theta )& 1\end{array}\right)$

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 $\left(\begin{array}{c}\cos (\theta )\\ \sin (\theta )\end{array}\right)$, 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 planes ², 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.

Footnotes:

1. CO-ordinate Rotation DIgital Computer

2. and just as prone to crashing