\magnification=\magstep1
\input pictex
\setbox1=\vbox{
\beginpicture
\setcoordinatesystem units < 1.40586in, 1.40586in>
\put {\phantom{.}} at -0.37277 -0.07533
\put {\phantom{.}} at -0.37277  1.71595
\put {\phantom{.}} at  1.1211 -0.07533
\put {\phantom{.}} at  1.1211  1.71595
\setlinear
\putrule from  0.00000  0.00000 to  1.00000  0.00000
\putrule from  1.00000  1.00000 to  1.00000  0.00000
\plot  0.00000  0.00000  1.00000  1.00000 /
\plot  0.50000  1.50000  1.00000  1.00000 /
\plot  0.00000  0.00000  0.50000  1.50000 /
\plot  0.12500  1.62500  0.50000  1.50000 /
\plot  0.00000  0.00000  0.12500  1.62500 /
\plot -0.07813  1.64063  0.12500  1.62500 /
\plot  0.00000  0.00000 -0.07813  1.64063 /
\plot -0.18066  1.63574 -0.07813  1.64063 /
\plot  0.00000  0.00000 -0.18066  1.63574 /
\put {$A$} at  -0.05  0.00000
\put {$B$} at  1.05000  0.00
\put {$C$} at  1.05000  1.04
\put {$D$} at  0.55000  1.55
\put {$E$} at  0.12500  1.68
\put {$F$} at -0.07813  1.69
\put {$G$} at -0.19066  1.69
\endpicture}
\parindent=0pt
\headline{\bf\hfil Elementary Functions and Calculators\hfil}
The mathematical content of these pages is not original.
Despite being accessible in journal articles for several years,
however, it seems not to be well
known.  Teachers of trigonometry and calculus thus may be surprised to learn
what really happens when they ask their calculators to find square roots,
cosines, and logarithms.  It is hoped that this paper will help dispel a
myth --- that the calculus of infinite power series is at work --- and that it
will instead rekindle interest in the mathematics that lies at the heart of
the versatile CORDIC algorithm --- namely, trigonometric addition
formulas and
hyperbolic functions.  It will also be seen that improvements are
needed. Refining this algorithm is a topic of current research.
\vskip .25in
\bf A Trigonometric Fan \rm
\vskip .15in
Imagine a fan built from a sequence of right triangles.  The longest leg of
each triangular section is hinged to the hypotenuse of the preceding section.
The angles that meet at the vertex of the fan are all acute, and decrease
steadily toward zero.  The sizes of the first five angles are
approximately $45.00^\circ$,
$26.57^\circ$, $14.04^\circ$, $7.13^\circ$, and $3.58^\circ$.
The diagram shows these sections.  Notice that
each angle is about half as large as its predecessor.  This is a consequence
of the precise construction of these angles.
What is actually being halved at
each stage is the \it tangent ratio\rm:  $BC = BA$, $CD = {1\over2}CA$,
$DE = {1\over4}DA$,
$EF = {1\over8}EA$, $FG = {1\over16}FA$, and so on.
The resulting infinite sequence of angles is geometric
in a limiting sense.
\vskip .1in
\hangindent -2.1in
\hangafter -20
The examples that follow employ only the
first two dozen terms of this sequence.
In principle every term is useful,
however, for the accuracy of CORDIC is
set by the size of the last angle in the
fan.  The scope of the algorithm is, as
you might have guessed, limited to those
angles covered by the fan, which include
all the acute ones.  The first four
angles alone bring the total to more than
90 degrees.  No matter how many of these
sections are included, the total never
quite reaches 100 degrees, by the way.
\vskip -1.6in
\hskip 3.2in
\box1
\vskip -0.8in
\hangindent -2.1in
\hangafter -5
To apply this fan to the computation of
trigonometric values, the initial segment
$\overline{AB}$ is placed on the positive $x$-axis, with
$A$ at the origin.  The terminal segment
(which would be $\overline{AG}$ if the fan consisted
of only five sections, as in the diagram)
points into the first or second quadrant,
depending on how the hinges are folded.
To say that the scope of the fan includes the first quadrant means that the
terminal segment can be made to point in any first-quadrant direction, to
within a small tolerance.
This is accomplished by folding the fan along its
hinges.  In the diagram on the next page, you see
the result of folding the third section
over the second (along hinge $\overline{AD}$), and then
the fourth and fifth sections over
the third (along hinge $\overline{AE}$).
\vfil
\eject
\setbox2=\vbox{
\beginpicture
\setcoordinatesystem units < 1.50214in, 1.50214in>
\put {\phantom{.}} at -0.23229 -0.07408
\put {\phantom{.}} at -0.23229  1.60240
\put {\phantom{.}} at  1.123229 -0.07408
\put {\phantom{.}} at  1.123229  1.60240
\setlinear
\putrule from  0.00000  0.00000 to  1.00000  0.00000
\putrule from  1.00000  1.00000 to  1.00000  0.00000
\plot  0.00000  0.00000  1.00000  1.00000 /
\plot  0.50000  1.50000  1.00000  1.00000 /
\plot  0.00000  0.00000  0.50000  1.50000 /
\plot  0.87500  1.37500  0.50000  1.50000 /
\plot  0.70313  1.48438  0.87500  1.37500 /
\plot  0.61035  1.52832  0.70313  1.48438 /
\plot  0.77778  1.22222  0.87500  1.37500 /
\plot  0.68182  1.43939  0.70313  1.48438 /
\plot  0.58741  1.47086  0.61035  1.52832 /
\setdots<3pt>
\plot  0.00000  0.00000  0.58741  1.47086 /
\plot  0.00000  0.00000  0.68182  1.43939 /
\plot  0.00000  0.00000  0.77778  1.22222 /
\put {$A$} at  -0.0500  0.00000
\put {$B$} at  1.05000  0.00000
\put {$C$} at  1.05000  1.04000
\put {$D$} at  0.48000  1.55000
\put {$E$} at  0.92500  1.42500
\put {$F$} at  0.75313  1.53438
\put {$G$} at  0.62035  1.5732
\endpicture}
\hangindent -2.1in
\hangafter -20
If the goal had been to create a $70^\circ$ angle with the fan, these would
have been the first five stages.  Because
the first two angles have a sum of more
than $70^\circ$, the third angle is subtracted
by folding it back over the second.  This
makes the subtotal $57.53^\circ$, so the fourth
and fifth angles must be added to bring
the subtotal to $68.23^\circ$.
\vskip .1in
\hangindent -2.1in
\hangafter -20
It is plausible that this process can be
continued until the terminal segment
makes an angle with $\overline{AB}$ that is as close
to $70^\circ$ as desired.  In fact, it can be
shown that the terminal angle differs
from the target angle by no more than the
last angle in the fan (as long as the
target angle lies within the scope of the
fan).  This is a property of the special
angles used to build the fan.
\vskip -2.15in
\hskip 3.25in
\box2
\vskip -0.25in
\hangindent -2.1in
\hangafter -2
From now on, all examples are based on a 24-section fan.  This guarantees
that each angle in the first quadrant will be approximated by the folding
process to within $0.00000683^\circ$ (the size of the 24th angle, whose
tangent is  $2^{-23}$).  The table below shows step-by-step how
the special angles are
combined so that the terminal segment of the fan is always
folded toward $70^\circ$.
\vskip .1in
$$\vbox{\settabs 5\columns
\+\phantom{MM}Angle&\quad Subtotal&\phantom{MM}Angle&\quad Subtotal&\cr
\smallskip
\+45.00000000(+)   &45.00000000    &0.01398823(+)   &70.00614325&\cr
\+26.56505118(+)   &71.56505118    &0.00699411($-$)   &69.99914914&\cr
\+14.03624347($-$)   &57.52880771    &0.00349706(+)   &70.00264619&\cr
\+\phantom{0}7.12501635(+)   &64.65382406    &0.00174853($-$)   &70.00089767&\cr
\+\phantom{0}3.57633437(+)   &68.23015843    &0.00087426($-$)   &70.00002340&\cr
\+\phantom{0}1.78991061(+)   &70.02006904    &0.00043713($-$)   &69.99958627&\cr
\+\phantom{0}0.89517371($-$)   &69.12489533    &0.00021857(+)   &69.99980484&\cr
\+\phantom{0}0.44761417(+)   &69.57250950    &0.00010928(+)   &69.99991412&\cr
\+\phantom{0}0.22381050(+)   &69.79632000    &0.00005464(+)   &69.99996876&\cr
\+\phantom{0}0.11190568(+)   &69.90822568    &0.00002732(+)   &69.99999608&\cr
\+\phantom{0}0.05595289(+)   &69.96417857    &0.00001366(+)   &70.00000974&\cr
\+\phantom{0}0.02797645(+)   &69.99215502    &0.00000683($-$)   &70.00000291&\cr
}
$$
\vskip .1in
Next to each of the 24 special angles is shown an
indication (+ or $-$) of how
the angle contributes to the folding process, as well as the subtotal that
results. Notice that every subtotal differs from $70^\circ$ by less than the size of
its special angle, by the way.
The covering property of the fan can be described another way:  There are 23
hinges, each of which can be folded in one of two ways.  This means that there
are $2^{23}= 8388608$ ways of folding the fan, hence 8388608 positions for the
terminal segment.  These 8388608 terminal segments are scattered throughout
the first quadrant and part of the second, uniformly enough that any radial
segment makes an angle less than $0.00000683^\circ$ with one of them.
\vfil
\eject
A key property of the special angles is that each one of them is exceeded by
the sum of those that follow it in the list.  This means that every section of
the fan can be covered by the (smaller) sections that follow it (except
possibly for a gap that is no larger than the smallest angle).
\vskip .2in
\bf A familiar property of powers of 2 \rm
\vskip .15in
Take any group of consecutive terms from the infinite series
$$
\cdots+16+8+4+2+1+{1\over2}+{1\over4}+{1\over8}+{1\over16}+\cdots
$$
and calculate its sum.  The result equals the difference between
the last term and the term that precedes the first term.
For instance, $8+4+2+1+{1\over2}+{1\over4} = 16-{1\over4}$.
In other words, any term
in the series is equal to the sum of any block of terms that follows it, the
last term in the block counting twice.  (If infinite series are allowed, then
any term equals the sum of \it all \rm the terms that follow it.)
\vskip .2in
With the help of the Mean-Value Theorem from Calculus, this familiar result
can be used to show that the special angles (whose tangents are powers of 2)
used to build the fan have the necessary covering and accuracy properties.
From now on, let $A_n$ denote the acute angle whose tangent is $2^{-n}$.
\vskip .2in
{
\parindent=0.3in\narrower\smallskip\noindent
For any nonnegative integers $m$ and $n$, with $m < n$,
$A_m$ is at most equal to
$A_{m+1} + A_{m+2} + \cdots + A_n + A_n$.
\smallskip
}
\vskip .1in
{
\parindent=0.3in\narrower\smallskip\noindent
Let $T$ be a target value, with $0 < T < A_0 + A_1 +\cdots + A_n$.  Define a
sequence as follows:  $T_0 = 0$ and, for $0\le m$, let
$T_{m+1} = T_m + A_m$ if
$T_m < T$ and $T_{m+1} = T_m - A_m$ if $T\le T_m$.  Then
$|T_{n+1} - T| \le A_n$.
\smallskip
}
\vskip .2in
See [2] for proofs of these results, which formalize the angle-approximation
scheme described above.  Each $T_m$ is the subtotal after
special angle $A_{m-1}$ has
been included.
\vskip .2in

\bf Trigonometric calculations \rm
\vskip .15in
The time has come to actually calculate something. Let us find the sine
and cosine of a
70-degree angle.  The primary computational tools are the well known
trigonometric addition formulas
$$
\eqalign{
                  &\cos(u \pm v) = \cos(u)\cos(v) \mp \sin(u)\sin(v)\cr
                  &\sin(u \pm v) = \sin(u)\cos(v) \pm \cos(u)\sin(v)\cr
}
$$
\vfil
\eject
Because $70^\circ$ is approximated by
$T_{24} = A_0+A_1-A_2+A_3+A_4+A_5-A_6+\cdots+A_{21}+A_{22}-A_{23}$,
it is inviting to build up the desired answers in stages.  First find
$$
\eqalign{
     \cos(A_0) &= 0.70710678\cr
     \sin(A_0) &= 0.70710678\cr
     \cos(A_1) &= 0.89442719\cr
     \sin(A_1) &= 0.44721360\cr
     &\vdots\cr
     \cos(A_{23}) &= 1.00000000\cr
     \sin(A_{23}) &= 0.00000012.\cr
}
$$
Incidentally, these values can be found by Pythagorean methods (the tangents
of these angles are known, remember), and it is only necessary to calculate
them once, for the same angles will be applied to every target angle.
\vskip .15in
Next use the addition formulas to calculate
$$
\eqalign{
&\cos(T_1) = \cos(T_0+A_0) = \cos(A_0) = 0.70710678\cr
&\sin(T_1) = \sin(T_0+A_0) = \sin(A_0) = 0.70710678,\cr
&\vphantom{M}\cr
&\cos(T_2) = \cos(T_1+A_1) = \cos(T_1)\cos(A_1) - \sin(T_1)\sin(A_1) = 0.31622777\cr
&\sin(T_2) = \sin(T_1+A_1) = \sin(T_1)\cos(A_1) + \cos(T_1)\sin(A_1) = 0.94868330,\cr
}
$$
then use the subtraction formulas to calculate
$$
\eqalign{
&\cos(T_3) = \cos(T_2-A_2) = \cos(T_2)\cos(A_2) + \sin(T_2)\sin(A_2) = 0.53687549\cr
&\sin(T_3) = \sin(T_2-A_2) = \sin(T_2)\cos(A_2) - \cos(T_2)\sin(A_2) = 0.84366149,\cr
}
$$
and so on.  This naive, recursive approach will yield the desired sine and
cosine values, \it but at great cost\rm.
Every round requires four multiplications
and two additions, so the whole task requires 92 multiplications and 46
additions.  This is time-consuming, even for a state-of-the-art electronic
device.  There is a better way --- one that requires \it no \rm multiplications!
\vskip .2in
\bf No multiplications?\rm
\vskip .1in
The clever trick is to rewrite the addition formulas as follows:
$$
\eqalign{
\cos(u \pm v) &= \cos(v)\left[\cos(u) \mp \tan(v)\sin(u)\right]\cr
\sin(u \pm v) &= \cos(v)\left[\sin(u) \pm \tan(v)\cos(u)\right]\cr
}
$$
\vfil
\eject
The recursive calculations now take the form
$$
\eqalign{
\cos(T_1) &= \cos(A_0),\cr
\sin(T_1) &= \cos(A_0),\cr
&\vphantom{M}\cr
\cos(T_2) &= \cos(A_1)\left[\cos(T_1) - {1\over2}\sin(T_1)\right] = \cos(A_1)\cos(A_0)\left[1\over2\right],\cr
\sin(T_2) &= \cos(A_1)\left[\sin(T_1) + {1\over2}\cos(T_1)\right] = \cos(A_1)\cos(A_0)\left[3\over2\right],\cr
&\vphantom{M}\cr
\cos(T_3) &= \cos(A_2)\left[\cos(T_2) + {1\over4}\sin(T_2)\right] = \cos(A_2)\cos(A_1)\cos(A_0)\left[7\over8\right],\cr
\sin(T_3) &= \cos(A_2)\left[\sin(T_2) - {1\over4}\cos(T_2)\right] = \cos(A_2)\cos(A_1)\cos(A_0)\left[11\over8\right],\cr
}
$$
and so on.  The powers of $1\over2$ are the tangent values
of the special angles.
Because the cosines have been factored out, the powers of
$1\over2$ occur where the
sine values once were.  It is easy to look ahead to the desired answers,
$$
\eqalign{
\cos(T_{24}) &= \cos(A_{23})\cos(A_{22})\cdots\cos(A_1)\cos(A_0)[C_{24}],\cr
\sin(T_{24}) &= \cos(A_{23})\cos(A_{22})\cdots\cos(A_1)\cos(A_0)[S_{24}],\cr
}
$$
where $C_{24}$ and $S_{24}$ are \it dyadic rationals\rm,
calculated recursively as follows:
$$
\eqalign{
&C_0 = 1 \hbox{\quad and\quad} S_0 = 0\cr
&C_{m+1} = C_m - 2^{-m}D_mS_m \cr
&S_{m+1} = S_m + 2^{-m}D_mC_m \cr
}
$$
Each $D_m$ is either 1 or $-1$, depending on whether
special angle $A_m$ appears with
a positive or negative sign in the approximation of the target angle.  The
variable names $C_m$ and $S_m$ are meant to suggest
cosine and sine, respectively,
even though their values are \it not \rm $\cos(T_m)$ and $\sin(T_m)$.
\vskip .15in
It should now be clear why the tangent function was chosen to set up the fan.
It is perhaps also clear that choosing to work with powers of two is about
to pay a dividend.
\vskip .2in
\bf Multiplying and dividing by 2 is easy for computers\rm
\vskip .1in
Because numbers are usually represented in base-10 notation, it is an easy
matter to divide a number like 0.70710678 by 10 --- just shift the point one
space to the left.  The same principle applies to numbers expressed in base-2
notation, as is usually internally the case in electronic calculators.  It is
thus easy to divide $\cos(A_0) = 0.101101010000010011110011001\dots$
by two=10 (but
not by ten=1010).
\vfil
\eject
In other words, the recursion above involves only addition, subtraction, and
point-shifting --- \it no multiplication or division \rm --- when
done in binary scale.
\vskip .15in
This leaves only the final product
$\cos(A_{23})\cos(A_{22})\cdots\cos(A_1)\cos(A_0)$ to worry
about.  It is eliminated next.
\vskip .2in
\bf The fan revisited\rm
\vskip .15in
One obvious and important feature of the fan is that the lengths of its hinges
do not change, no matter how it is folded.  These lengths are related in a
simple way: First $AC = \sec(A_0)AB$, then $AD = \sec(A_1)AC = \sec(A_1)\sec(A_0)AB$,
and so on --- each
one being larger than its predecessor.
In particular, the length of the terminal
segment of the 24-section fan is
$\sec(A_{23})\sec(A_{22})\cdots\sec(A_1)\sec(A_0)AB$.
This is
useful information, because looking for cosine and sine values is equivalent
to looking for $x$- and $y$-coordinates of points on the
unit circle.  In order
that the terminal segment of the fan be of unit length, it is necessary that
$AB=\cos(A_{23})\cos(A_{22})\cdots\cos(A_1)\cos(A_0)$.
From now on, this
\it constant\rm, which is about 0.607252935, will be denoted by $P$.
Whenever the 24-section fan is used to approximate angles,
the value of $P$ is essential, for it
is used to seed the recursion.  This is how multiplication is avoided
entirely.
\vskip .1in
In other words, if the recursion is redefined
$$
\eqalign{
&C_0 = P\hbox{\quad and\quad} S_0 = 0\cr
&C_{m+1} = C_m - 2^{-m}D_mS_m\cr
&S_{m+1} = S_m + 2^{-m}D_mC_m,\cr
}
$$
then $C_{24}$ and $S_{24}$ will be $\cos(T_{24})$ and $\sin(T_{24})$,
respectively.  Making the
length of fan segment $\overline{AB}$ exactly $P$ thus
eliminates all the multiplications from the process.
\vskip .2in
It remains only to define the numbers $D_m$ carefully. These
coefficients are determined by the target angle.
For the final version of the algorithm, it is convenient to modify
the angle-approximation recursion slightly.
Instead of starting with $T_0 = 0$ and building toward the
target value $T$, it is
customary to start the process with the target value and reduce this value
to zero.  In other words, instead of checking to see whether $T_m$ is
less than $T$, we check to see whether $Z_m = T-T_m$ is
greater than zero. This does not affect the calculations; it simply
means that the process is guided by the sign of $Z_m$.
Here is the final version of the algorithm:
$$
\eqalign{
&Z_0 = T\hbox{\ ,\ } C_0 = P\hbox{\ ,\ } S_0 = 0\cr
&Z_{m+1} = Z_m - D_mA_m\cr
&C_{m+1} = C_m - 2^{-m}D_mS_m\cr
&S_{m+1} = S_m + 2^{-m}D_mC_m,\cr
}
$$
where $D_m = \pm1$ is chosen to have the same sign as $Z_m$.
We say that $Z_m$ is \it driven toward zero\rm.
In the process, $C_m$ and $S_m$ are driven toward $\cos(T)$ and
$\sin(T)$, respectively.
\vfil
\eject
This is known as the CORDIC algorithm, which stands for
\it COordinate Rotation DIgital Computer\rm.
The method was published in 1959 by J. Volder.
See [2] for more
details of its historical and mathematical evolution.
It is still used today,
because of its speed and efficiency.  To calculate sine and cosine values for
any of the 8388608 angles that can be exactly represented by the 24-section
fan, it is only necessary to have twenty-five permanently stored constants
($A_0$, $A_1$, \dots, $A_{23}$, and $P$),
which are combined using only addition, subtraction, and point-shifting.
These 8388608 sine and cosine values are used in place of the correct
values for all other (nearby) angles.
\vskip .3in
The table below shows all the details of the (simultaneous)
calculation of $\cos(70^\circ)$ and $\sin(70^\circ)$.
Each row of the table shows the values of
$Z$, $C$, $S$, and $D$ at the end of a computation cycle.
Each row of the table is
produced by looking back at the previous row.
Once the sign of $D$ is set (by
the sign of the old value of $Z$), all else follows.
Except for $A$, each row of
the table replaces the previous row in the calculator memory.
\vskip .15in
$$\vbox{
\settabs
\+24&0000070.00000000&MMM0.60725294&MMM0.00000000&MMM1&MMM45.00000000&\cr
\+\hfill $m$&\phantom{000000000}$Z_m$&\phantom{000000000}$C_m$&\phantom{000000000}$S_m$&\hfill $D_m$&\phantom{000000000}$A_m$&\cr
\smallskip
\+\hfill 0&\hfill 70.00000000&\hfill 0.60725294&\hfill 0.00000000&\hfill 1&\hfill45.00000000&\cr
\+\hfill 1&\hfill 25.00000000&\hfill 0.60725294&\hfill 0.60725294&\hfill 1&\hfill 26.56505118&\cr
\+\hfill 2&\hfill $-1.56505118$&\hfill 0.30362647&\hfill 0.91087940&\hfill $-1$&\hfill 14.03624347&\cr
\+\hfill 3&\hfill 12.47119229&\hfill 0.53134632&\hfill 0.83497279&\hfill 1&\hfill 7.12501635&\cr
\+\hfill 4&\hfill 5.34617594&\hfill 0.42697472&\hfill 0.90139108&\hfill 1&\hfill 3.57633437&\cr
\+\hfill 5&\hfill 1.76984157&\hfill 0.37063778&\hfill 0.92807700&\hfill 1&\hfill 1.78991061&\cr
\+\hfill 6&\hfill $-0.02006904$&\hfill 0.34163537&\hfill 0.93965943&\hfill $-1$&\hfill 0.89517371&\cr
\+\hfill 7&\hfill 0.87510467&\hfill 0.35631755&\hfill 0.93432137&\hfill 1&\hfill 0.44761417&\cr
\+\hfill 8&\hfill 0.42749050&\hfill 0.34901816&\hfill 0.93710510&\hfill 1&\hfill 0.22381050&\cr
\+\hfill 9&\hfill 0.20368000&\hfill 0.34535760&\hfill 0.93846846&\hfill 1&\hfill 0.11190568&\cr
\+\hfill 10&\hfill 0.09177432&\hfill 0.34352465&\hfill 0.93914298&\hfill 1&\hfill 0.05595289&\cr
\+\hfill 11&\hfill 0.03582143&\hfill 0.34260752&\hfill 0.93947846&\hfill 1&\hfill 0.02797645&\cr
\+\hfill 12&\hfill 0.00784498&\hfill 0.34214879&\hfill 0.93964575&\hfill 1&\hfill 0.01398823&\cr
\+\hfill 13&\hfill $-0.00614325$&\hfill 0.34191938&\hfill 0.93972928&\hfill $-1$&\hfill 0.00699411&\cr
\+\hfill 14&\hfill 0.00085086&\hfill 0.34203410&\hfill 0.93968754&\hfill 1&\hfill 0.00349706&\cr
\+\hfill 15&\hfill $-0.00264619$&\hfill 0.34197674&\hfill 0.93970842&\hfill $-1$&\hfill 0.00174853&\cr
\+\hfill 16&\hfill $-0.00089767$&\hfill 0.34200542&\hfill 0.93969798&\hfill $-1$&\hfill 0.00087426&\cr
\+\hfill 17&\hfill $-0.00002340$&\hfill 0.34201976&\hfill 0.93969276&\hfill $-1$&\hfill 0.00043713&\cr
\+\hfill 18&\hfill 0.00041373&\hfill 0.34202693&\hfill 0.93969015&\hfill 1&\hfill 0.00021857&\cr
\+\hfill 19&\hfill 0.00019516&\hfill 0.34202334&\hfill 0.93969146&\hfill 1&\hfill 0.00010928&\cr
\+\hfill 20&\hfill 0.00008588&\hfill 0.34202155&\hfill 0.93969211&\hfill 1&\hfill 0.00005464&\cr
\+\hfill 21&\hfill 0.00003124&\hfill 0.34202066&\hfill 0.93969243&\hfill 1&\hfill 0.00002732&\cr
\+\hfill 22&\hfill 0.00000392&\hfill 0.34202021&\hfill 0.93969260&\hfill 1&\hfill 0.00001366&\cr
\+\hfill 23&\hfill $-0.00000974$&\hfill 0.34201998&\hfill 0.93969268&\hfill $-1$&\hfill 0.00000683&\cr
\+\hfill 24&\hfill $-0.00000291$&\hfill 0.34202010&\hfill 0.93969264&\cr
}
$$
\vfil
\eject
It is sometimes suggested that the
computational process could be improved by
taking the sizes of $A_m$ and $Z_m$ into account.  For example,
in the 70-degree
computation, it would seem advantageous to leave out
special angles $A_2$, $A_3$,
and $A_4$, for they are all much larger than the remainder $Z_2$.
Even if one disregards the logical complications
that such decision-making would introduce
into the algorithm, the answer is clear:  This would mean removing sections
from the fan, thereby making it impossible to predict the length of the
terminal segment in advance.  It is an essential feature of the CORDIC method
of building with special angles
that \it every special angle is used in every application\rm.
All intermediate stages of the simultaneous
computation of $\cos(70^\circ)$ and
$\sin(70^\circ)$ are shown in the preceding table
(in base-10 notation, of course).
The 24 cycles of this
algorithm are sufficient to guarantee better than
6-place accuracy.  This is
because the angle-approximation process creates an
error of at most $0.00000683^\circ$,
and because the sine and cosine functions themselves shrink this
error further (to at most 0.00000012, as can be proved with calculus).
\vskip .2in
\bf CORDIC has a reverse gear, too\rm
\vskip .15in
Now that you have thoroughly examined the sine
and cosine buttons on your calculator, turn your
attention to some of the others.  Because tangents are just
ratios of sines to cosines, it is clear that the tangent button needs no
further attention.  The time has come to see what happens when CORDIC is run
backwards.  In other words, it is time to take up the inverse trigonometric
functions.
\vskip .15in
As it turns out, the simplest one to understand is the inverse tangent.  You
might think that this is because the contruction of the fan features tangent
ratios; actually, it is because tangent ratios provide the simplest way to
describe an angle.  As an example, consider the problem of finding the acute
angle whose tangent is 2.  This will illustrate
the angle-finding capability of CORDIC.
\vskip .2in
You are now in the position of knowing the terminal ray of
the fan, but of not
knowing the combination of special angles that produced it.
The obvious solution is to apply the angle-approximation
algorithm again and keep an eye on
the target angle.  The difficulty is deciding how to deal with
variable $Z$; how
to seed it or how to know when it is close to its target
value.  The trick is
to turn the fan over and place the
initial $\overline{AB}$ on the terminal line.
This in effect provides initial values for $S$ and $C$.
The folding process is
now directed toward the positive $x$-axis.  Variable $Z$ will
approach the desired
angle, provided that it is initialized to be zero.
\vskip .15in
Which variable --- $C$ or $S$ --- should control the process?
In other words, should $C$ be
driven toward 1 or $S$ be driven toward 0?
The correct choice is to
drive $S$ toward 0.  The reason is that it is not necessary to worry about
the size of the fan for this problem.  The seed values for
$C$ and $S$ should be of no concern
individually --- they need only be chosen so that $S/C = 2$.
Thus, because $C$ and $S$ need not represent
actual cosine and sine values, it would be incorrect to drive $C$ toward 1.
\vfil
\eject
All the intermediate stages of the computation of $\arctan(2)$
are shown below.
Notice that the initial values
$C_0 = 0.25$ and $S_0 = 0.5$ define the angle.
$$\vbox{
\settabs
\+24&0000070.00000000&MMM0.60725294&MMM0.00000000&MMM1&MMM45.00000000&\cr
\+\hfill $m$&\phantom{000000000}$Z_m$&\phantom{000000000}$C_m$&\phantom{000000000}$S_m$&\hfill $D_m$&\phantom{000000000}$A_m$&\cr
\smallskip
\+\hfill 0&\hfill 0.00000000&\hfill 0.25000000&\hfill 0.50000000&\hfill   $-1$&\hfill 45.00000000&\cr
\+\hfill 1&\hfill 45.00000000&\hfill 0.75000000&\hfill 0.25000000&\hfill   $-1$&\hfill 26.56505118&\cr
\+\hfill 2&\hfill 71.56505118&\hfill 0.87500000&\hfill $-0.12500000$&\hfill    1&\hfill 14.03624347&\cr
\+\hfill 3&\hfill 57.52880771&\hfill 0.90625000&\hfill 0.09375000&\hfill   $-1$&\hfill 7.12501635&\cr
\+\hfill 4&\hfill 64.65382406&\hfill 0.91796875&\hfill $-0.01953125$&\hfill    1&\hfill 3.57633437&\cr
\+\hfill 5&\hfill 61.07748968&\hfill 0.91918945&\hfill 0.03784180&\hfill   $-1$&\hfill 1.78991061&\cr
\+\hfill 6&\hfill 62.86740029&\hfill 0.92037201&\hfill 0.00911713&\hfill   $-1$&\hfill 0.89517371&\cr
\+\hfill 7&\hfill 63.76257400&\hfill 0.92051446&\hfill $-0.00526369$&\hfill    1&\hfill 0.44761417&\cr
\+\hfill 8&\hfill 63.31495983&\hfill 0.92055559&\hfill 0.00192783&\hfill   $-1$&\hfill 0.22381050&\cr
\+\hfill 9&\hfill 63.53877033&\hfill 0.92056312&\hfill $-0.00166809$&\hfill    1&\hfill 0.11190568&\cr
\+\hfill 10&\hfill 63.42686465&\hfill 0.92056638&\hfill 0.00012989&\hfill   $-1$&\hfill 0.05595289&\cr
\+\hfill 11&\hfill 63.48281755&\hfill 0.92056650&\hfill $-0.00076910$&\hfill    1&\hfill 0.02797645&\cr
\+\hfill 12&\hfill 63.45484109&\hfill 0.92056688&\hfill $-0.00031961$&\hfill    1&\hfill 0.01398823&\cr
\+\hfill 13&\hfill 63.44085287&\hfill 0.92056696&\hfill $-0.00009486$&\hfill    1&\hfill 0.00699411&\cr
\+\hfill 14&\hfill 63.43385875&\hfill 0.92056697&\hfill 0.00001751&\hfill   $-1$&\hfill 0.00349706&\cr
\+\hfill 15&\hfill 63.43735581&\hfill 0.92056697&\hfill $-0.00003867$&\hfill    1&\hfill 0.00174853&\cr
\+\hfill 16&\hfill 63.43560728&\hfill 0.92056697&\hfill $-0.00001058$&\hfill    1&\hfill 0.00087426&\cr
\+\hfill 17&\hfill 63.43473302&\hfill 0.92056697&\hfill 0.00000347&\hfill   $-1$&\hfill 0.00043713&\cr
\+\hfill 18&\hfill 63.43517015&\hfill 0.92056697&\hfill $-0.00000356$&\hfill    1&\hfill 0.00021857&\cr
\+\hfill 19&\hfill 63.43495158&\hfill 0.92056697&\hfill $-0.00000004$&\hfill    1&\hfill 0.00010928&\cr
\+\hfill 20&\hfill 63.43484230&\hfill 0.92056697&\hfill 0.00000171&\hfill   $-1$&\hfill 0.00005464&\cr
\+\hfill 21&\hfill 63.43489694&\hfill 0.92056697&\hfill 0.00000083&\hfill   $-1$&\hfill 0.00002732&\cr
\+\hfill 22&\hfill 63.43492426&\hfill 0.92056697&\hfill 0.00000039&\hfill   $-1$&\hfill 0.00001366&\cr
\+\hfill 23&\hfill 63.43493792&\hfill 0.92056697&\hfill 0.00000018&\hfill   $-1$&\hfill 0.00000683&\cr
\+\hfill 24&\hfill 63.43494475&\hfill 0.92056697&\hfill 0.00000007&\hfill\cr
}
$$
The entries in the $S$ column are approaching 0; the
entries in the $Z$-column
are approaching $\arctan(2)$.  It is left as an exercise
for you to identify the
number that is being approached by the entries in the $C$ column.
(The answer is useful and will appear in a few pages.)
The recursive CORDIC approach to calculating $\arctan(T)$ is defined as
follows:
$$
\eqalign{
&Z_0 = 0\hbox{\ ,\ } S_0 = C_0T\cr
&Z_{m+1} = Z_m - D_mA_m\cr
&C_{m+1} = C_m - 2^{-m}D_mS_m\cr
&S_{m+1} = S_m + 2^{-m}D_mC_m\cr
}
$$
where $D_m = \pm1$ is chosen so that $D_mC_m$ and $S_m$ have
opposite signs.  This drives
$S_m$ toward 0.  In the process, $Z_m$ is driven towards $\arctan(T)$.
This algorithm
can be applied to any angle within the scope of the fan, which includes all
acute angles and some obtuse ones.
\vfil
\eject
As for inverse sines and cosines, they can be dealt with similarly.  In fact,
any such problem can be converted into an inverse tangent problem by means of
a preliminary Pythagorean computation.  For instance, finding
$\arcsin(0.6)$ is
equivalent to finding $\arctan(0.75)$, and finding $\arccos(u)$
is equivalent to finding
$\displaystyle\arctan\left(\sqrt{1-u^2}\over u\right)$.
\vskip .2in
If this were all that CORDIC could perform for us, it would be a remarkable
invention.  There is still much more, however.
\vskip .2in
\bf Exponents and logarithms\rm
\vskip .15in
The utility and elegance of mathematics resides in its ability to
exploit formal connections between apparently distinct problems.  A case
in point is the system of hyperbolic functions,
namely sinh, cosh, tanh, csch,
sech, and coth.  Recall that
$$
\cosh(u) = {1\over2}\left(e^u+e^{-u}\right)
\hbox{\quad and\quad}
\sinh(u) = {1\over2}\left(e^u-e^{-u}\right),
$$
and that tanh(u) = sinh(u)/cosh(u), sech(u) = 1/cosh(u), and so on.  Despite
the appearance of these functions, their very names suggest that there are
important similarities with the circular functions.  For CORDIC, the most
useful identities are the following:
\vskip .15in
\centerline{$[\cosh(u)]^2 - [\sinh(u)]^2 = 1$}\par
\centerline{$\cosh(u\pm v) = \cosh(u)\cosh(v) \pm \sinh(u)\sinh(v)$} \par
\centerline{$\sinh(u\pm v) = \sinh(u)\cosh(v) \pm \cosh(u)\sinh(v)$}
\vskip .15in
The calculator does not actually know of any geometric significance to the
numbers $A_m$ and $P$ that it combines to evaluate circular
functions.  All it has
to work with are the formal identities, applied in a recursive way.
There is
every reason to hope, therefore, that the CORDIC approach will be able to 
evaluate hyperbolic functions as easily as it evaluates circular functions. 
Define $B_m$ provisionally by the equation $\tanh(B_m) = 2^{-m}$
for $m$ = 1, 2, \dots, $n$, let
$Q$ be the product $\cosh(B_1)\cosh(B_2)\cdots\cosh(B_n)$,
and consider the equations
$$
\eqalign{
&Z_1 = T\hbox{\ ,\ } C_1 = Q\hbox{\ ,\ } S_1 = 0\cr
&Z_{m+1} = Z_m - D_mB_m\cr
&C_{m+1} = C_m + 2^{-m-1}D_mS_m\cr
&S_{m+1} = S_m + 2^{-m-1}D_mC_m\cr
}
$$
where $D_m = \pm1$ is always chosen to have the same sign as $Z_m$.
It is necessary to look at the fine details of this proposal to see whether
there are subtle flaws.  You have probably already noted slight departures
from the circular model.  The sign change in the addition formula for
$\cosh(u\pm v)$ has been incorporated into the recursion;
it is not expected to
cause any difficulty.  On the other hand, because the
equation $\tanh(u) = 1$ has
no solutions, the list of special \it arguments \rm $B_m$
begins with the solution to $\tanh(B_1) = 1/2$.
The indices in the recursion have
been adjusted accordingly.
\vfil
\eject
\bf Approximating hyperbolic arguments is not routine\rm
\vskip .15in
The table below shows the results of \it trying \rm to
approximate the value 0.549 by
combining the special arguments $B_1$, $B_2$, ..., $B_{24}$:
$$\vbox{\settabs 5\columns
\+\phantom{MM}Arg&\phantom{,}Subtotal&\phantom{MM}Arg&\phantom{,}Subtotal&\cr
\smallskip
\+0.54930614(+)    &0.54930614  &0.00012207(+)    &0.54452168&\cr
\+0.25541281($-$)    &0.29389333  &0.00006104(+)    &0.54458271&\cr
\+0.12565721(+)    &0.41955055  &0.00003052(+)    &0.54461323&\cr
\+0.06258157(+)    &0.48213212  &0.00001526(+)    &0.54462849&\cr
\+0.03126018(+)    &0.51339230  &0.00000763(+)    &0.54463612&\cr
\+0.01562627(+)    &0.52901857  &0.00000381(+)    &0.54463994&\cr
\+0.00781266(+)    &0.53683123  &0.00000191(+)    &0.54464184&\cr
\+0.00390627(+)    &0.54073750  &0.00000095(+)    &0.54464280&\cr
\+0.00195313(+)    &0.54269062  &0.00000048(+)    &0.54464327&\cr
\+0.00097656(+)    &0.54366719  &0.00000024(+)    &0.54464351&\cr
\+0.00048828(+)    &0.54415547  &0.00000012(+)    &0.54464363&\cr
\+0.00024414(+)    &0.54439961  &0.00000006(+)    &0.54464369&\cr
}
$$
The problem is that $B_2$ is greater (by more than 0.00466)
than the sum of $B_3$, $B_4$, \dots, $B_{24}$.
This is a situation where it seems desirable to skip one of the
special terms, for subtracting $B_2$ has left the
subtotal much farther from the
target than it was before $B_1$ was subtracted --- so far, in fact, that the
difference can not be closed with later terms.
\vskip .2in
The inadequacy of this sequence of special arguments casts some doubt on the
ability of CORDIC to evaluate exponential functions.  Because the
special arguments $B_m$ lack the essential covering property
discussed earlier, the algorithm can not
approximate arguments such as $T=0.549$ with sufficient
accuracy to permit computation of usable values for $\cosh(T)$ and $\sinh(T)$.
\vskip .15in
The remedy is simple, however --- make \it duplicate entries \rm in
the list of special
arguments.  In other words, allow the algorithm to
\it reuse \rm certain arguments, in
order that it be able to close all gaps such as in the example.  This
selection of duplicates must be made once
and for all, so that the constant $Q$
can be calculated and stored along with the arguments $B_m$.
One solution is
presented on the next page, together with a demonstration of its correctness.
The proof consists of verifying that every
argument in the list is at most
equal to the sum of all the arguments that follow it in the list, except for
an allowable gap equal to the last argument in the list.
\vfil
\eject
The illustration below shows the eighteen special
arguments $\tanh^{-1}(2^{-m})$ for
$m$ = 1, 2, \dots, 18.  Next to each is tabled the sum of
all the special arguments
that follow it in the list.  Notice that every entry
exceeds the corresponding sum by more than the allowed 0.00000381.
$$\vbox{\settabs 5\columns
\+\phantom{m}Argum&\phantom{Mm}Sum&\phantom{m}Argum&\phantom{Mm}Sum&\cr
\smallskip
\+0.54930614     &0.50615941       &0.00097656     &0.00097275&\cr
\+0.25541281     &0.25074660       &0.00048828     &0.00048447&\cr
\+0.12565721     &0.12508939       &0.00024414     &0.00024033&\cr
\+0.06258157     &0.06250782       &0.00012207     &0.00011826&\cr
\+0.03126018     &0.03124764       &0.00006104     &0.00005722&\cr
\+0.01562627     &0.01562137       &0.00003052     &0.00002670&\cr
\+0.00781266     &0.00780871       &0.00001526     &0.00001144&\cr
\+0.00390627     &0.00390244       &0.00000763     &0.00000381&\cr
\+0.00195313     &0.00194931       &0.00000381&\cr
}
$$
The next table shows the effect of duplicating six chosen entries (which are
marked).  Now every special argument is exceeded by the sum of the arguments
that follow it in the list.  This verifies the covering property that is
necessary for the CORDIC algorithm to approximate arguments to a predictable
degree of accuracy.
$$\vbox{\settabs 5\columns
\+\phantom{m}Argum&\phantom{Mm}Sum&\phantom{m}Argum&\phantom{Mm}Sum&\cr
\smallskip
\+0.54930614     &0.57712204       &0.00048828     &0.00105286&\cr
\+0.25541281     &0.32170922       &0.00048828*    &0.00056458&\cr
\+0.12565721     &0.19605201       &0.00024414     &0.00032043&\cr
\+0.06258157     &0.13347044       &0.00012207     &0.00019836&\cr
\+0.06258157*    &0.07088887       &0.00006104     &0.00013733&\cr
\+0.03126018     &0.03962869       &0.00006104*    &0.00007629&\cr
\+0.01562627     &0.02400242       &0.00003052     &0.00004578&\cr
\+0.00781266     &0.01618976       &0.00001526     &0.00003052&\cr
\+0.00781266*    &0.00837710       &0.00001526*    &0.00001526&\cr
\+0.00390627     &0.00447083       &0.00000763     &0.00000763&\cr
\+0.00195313     &0.00251770       &0.00000381     &0.00000381&\cr
\+0.00097656     &0.00154114       &0.00000381*&\cr
}
$$
Every argument that lies within the scope of the table (from 0.0 to about
1.12642818) can be approximated to within 0.00000381 (the last entry in the
list).  The next page shows a new, successful attempt on the example $T=0.549$.
\vfil
\eject
How to accurately represent $T=0.549$ as a combination of special arguments $B_m$:
$$\vbox{\settabs 5\columns
\+\phantom{MM}Arg&\phantom{,}Subtotal&\phantom{MM}Arg&\phantom{,}Subtotal&\cr
\smallskip
\+0.54930614(+)    &0.54930614     &0.00048828($-$)    &0.54911683&\cr
\+0.25541281($-$)    &0.29389333     &0.00048828($-$)    &0.54862855&\cr
\+0.12565721(+)    &0.41955055     &0.00024414(+)    &0.54887269&\cr
\+0.06258157(+)    &0.48213212     &0.00012207(+)    &0.54899476&\cr
\+0.06258157(+)    &0.54471369     &0.00006104(+)    &0.54905580&\cr
\+0.03126018(+)    &0.57597387     &0.00006104($-$)    &0.54899476&\cr
\+0.01562627($-$)    &0.56034760     &0.00003052(+)    &0.54902528&\cr
\+0.00781266($-$)    &0.55253494     &0.00001526($-$)    &0.54901002&\cr
\+0.00781266($-$)    &0.54472228     &0.00001526($-$)    &0.54899476&\cr
\+0.00390627(+)    &0.54862855     &0.00000763(+)    &0.54900239&\cr
\+0.00195313(+)    &0.55058168     &0.00000381($-$)    &0.54899858&\cr
\+0.00097656($-$)    &0.54960511     &0.00000381(+)    &0.54900239&\cr
}
$$
Now the provisional definition of the list of
special arguments can be put in
a reliable form.  The 24 special values will be
denoted $B_0$, $B_1$, \dots, $B_{23}$ (in
the interest of uniformity), even though no simple formula for
$\tanh(B_m)$ is
available (because of the duplications).  All that needs to be stored is a
list of binary-point shifts, however; see the example below.  The CORDIC
algorithm for the hyperbolic functions cosh and sinh is
$$
\eqalign{
&Z_0 = T\hbox{\ ,\ } C_0 = Q\hbox{\ ,\ } S_0 = 0\cr
&Z_{m+1} = Z_m - D_mB_m\cr
&C_{m+1} = C_m + E_mD_mS_m\cr
&S_{m+1} = S_m + E_mD_mC_m,\cr
}
$$
where $D_m=\pm1$ is always chosen to have the same sign as
$Z_m$ (thus driving $Z_m$
toward 0), $Q$ is the constant
$\cosh(B_0)\cosh(B_1)\cdots\cosh(B_{23}) = 1.20753406...$, and
$E_m = \tanh(B_m)$ is an integral power of 1/2
(represented by the shift entry listed below).
\vskip .2in
Tabled on the next page is a table of all the intermediate
stages of a 24-cycle computation of $\cosh(1.0)$
and $\sinh(1.0)$, using this algorithm.
\vfil
\eject
All the intermediate stages of a 24-cycle CORDIC computation of
$\cosh(1.0)$ and $\sinh(1.0)$ are shown below.
$$\vbox{
\settabs
\+24&0000070.00000000&MM0.60725294&MM0.00000000&MM1&MMMM&MM45.00000000&&\cr
\+\hfill $m$&\phantom{000000000n}$Z_m$&\phantom{00000000}$C_m$&\phantom{00000000}$S_m$&\hfill $D_m$&\hfill$\hphantom{0000}Shift$&\hfill$B_m\hphantom{0i0}$&\cr
\smallskip
\+\hfill 0&\hfill 1.00000000&\hfill 1.20753406&\hfill0.00000000&\hfill 1&\hfill 1&\hfill    0.54930614&\cr
\+\hfill 1&\hfill 0.45069386&\hfill 1.20753406&\hfill0.60376703&\hfill 1&\hfill 2&\hfill    0.25541281&\cr
\+\hfill 2&\hfill 0.19528104&\hfill 1.35847581&\hfill0.90565054&\hfill 1&\hfill 3&\hfill    0.12565721&\cr
\+\hfill 3&\hfill 0.06962383&\hfill 1.47168213&\hfill1.07546002&\hfill 1&\hfill 4&\hfill    0.06258157&\cr
\+\hfill 4&\hfill 0.00704226&\hfill 1.53889838&\hfill1.16744015&\hfill 1&\hfill 4&\hfill    0.06258157&\cr
\+\hfill 5&\hfill -0.05553931&\hfill1.61186339&\hfill1.26362130&\hfill $-1$&\hfill 5&\hfill    0.03126018&\cr
\+\hfill 6&\hfill -0.02427913&\hfill1.57237523&\hfill1.21325057&\hfill $-1$&\hfill 6&\hfill    0.01562627&\cr
\+\hfill 7&\hfill -0.00865286&\hfill1.55341819&\hfill1.18868221&\hfill $-1$&\hfill 7&\hfill    0.00781266&\cr
\+\hfill 8&\hfill -0.00084020&\hfill1.54413161&\hfill1.17654613&\hfill $-1$&\hfill 7&\hfill    0.00781266&\cr
\+\hfill 9&\hfill 0.00697245&\hfill 1.53493984&\hfill1.16448260&\hfill 1&\hfill 8&\hfill    0.00390627&\cr
\+\hfill10&\hfill 0.00306618&\hfill 1.53948860&\hfill1.17047846&\hfill 1&\hfill 9&\hfill    0.00195313&\cr
\+\hfill11&\hfill 0.00111306&\hfill 1.54177469&\hfill1.17348527&\hfill 1&\hfill 10&\hfill    0.00097656&\cr
\+\hfill12&\hfill 0.00013649&\hfill 1.54292067&\hfill1.17499091&\hfill 1&\hfill 11&\hfill    0.00048828&\cr
\+\hfill13&\hfill -0.00035179&\hfill1.54349440&\hfill1.17574429&\hfill $-1$&\hfill 11&\hfill    0.00048828&\cr
\+\hfill14&\hfill 0.00013649&\hfill 1.54292030&\hfill1.17499063&\hfill 1&\hfill 12&\hfill    0.00024414&\cr
\+\hfill15&\hfill -0.00010765&\hfill1.54320717&\hfill1.17536732&\hfill $-1$&\hfill 13&\hfill    0.00012207&\cr
\+\hfill16&\hfill 0.00001442&\hfill 1.54306369&\hfill1.17517894&\hfill 1&\hfill 14&\hfill    0.00006104&\cr
\+\hfill17&\hfill -0.00004661&\hfill1.54313542&\hfill1.17527312&\hfill $-1$&\hfill 14&\hfill    0.00006104&\cr
\+\hfill18&\hfill 0.00001442&\hfill 1.54306368&\hfill1.17517894&\hfill 1&\hfill 15&\hfill    0.00003052&\cr
\+\hfill19&\hfill -0.00001609&\hfill1.54309955&\hfill1.17522603&\hfill $-1$&\hfill 16&\hfill    0.00001526&\cr
\+\hfill20&\hfill -0.00000083&\hfill1.54308162&\hfill1.17520248&\hfill $-1$&\hfill 16&\hfill    0.00001526&\cr
\+\hfill21&\hfill 0.00001442&\hfill 1.54306368&\hfill1.17517894&\hfill 1&\hfill 17&\hfill    0.00000763&\cr
\+\hfill22&\hfill 0.00000679&\hfill 1.54307265&\hfill1.17519071&\hfill 1&\hfill 18&\hfill    0.00000381&\cr
\+\hfill23&\hfill 0.00000298&\hfill 1.54307713&\hfill1.17519659&\hfill 1&\hfill 18&\hfill    0.00000381&\cr
\+\hfill24&\hfill -0.00000083&\hfill1.54308162&\hfill1.17520248&\hfill&\cr
}
$$
The values $C_{24}$ and $S_{24}$ are good approximations to cosh(1.0) and sinh(1.0),
respectively.  Their sum is 2.71828410, which has a familiar look to it:
\vskip .2in
\centerline{CORDIC evaluates $e^x$ by calculating cosh($x$)+sinh($x$).}
\vskip .2in
The approximation of arguments within the scope of this algorithm is accurate
to within 0.00000381.  The cosh and sinh functions can magnify any error by as
much as 1.4 or 1.7, respectively, so the results are accurate only to within
0.00000534 or 0.00000648.  This in turn makes the calculation of $e^x$
reliable only to within 0.00001182 (although the value for
$e$ found above was actually within 0.0000023 of being correct).
\vskip .15in
Remember that the above calculations, when carried out in base 2 arithmetic,
involve addition, subtraction, and
point-shifting only --- there is no multiplication or division.
\vfil
\eject
\bf Back into reverse gear\rm
\vskip .2in
Now that you have seen how CORDIC produces exponential values, it is time to
explore the very interesting inverse process.  As you would expect, the
function of central importance is the inverse hyperbolic tangent.
The illustration below shows the computation of
$\tanh^{-1}(1/3)$, which is initialized by
setting $Z_0 = 0$, $C_0 = 1$, and $S_0 = 3$.  As $S_m$ is driven toward 0,
$Z_m$ is driven toward the answer.
$$\vbox{
\settabs
\+24&0000070.00000000&MM0.60725294&MM0.00000000&MM1&MMMM&MM45.00000000&&\cr
\+\hfill $m$&\phantom{000000000n}$Z_m$&\phantom{00000000}$C_m$&\phantom{00000000}$S_m$&\hfill $D_m$&\hfill$\hphantom{0000}Shift$&\hfill$B_m\hphantom{0i0}$&\cr
\smallskip
\+\hfill 0&\hfill 0.00000000&\hfill 3.00000000&\hfill 1.00000000&\hfill   $-1$&\hfill     1&\hfill    0.54930614&\cr
\+\hfill 1&\hfill 0.54930614&\hfill 2.50000000&\hfill $-0.50000000$&\hfill    1&\hfill     2&\hfill    0.25541281&\cr
\+\hfill 2&\hfill 0.29389333&\hfill 2.37500000&\hfill 0.12500000&\hfill   $-1$&\hfill     3&\hfill    0.12565721&\cr
\+\hfill 3&\hfill 0.41955055&\hfill 2.35937500&\hfill $-0.17187500$&\hfill    1&\hfill     4&\hfill    0.06258157&\cr
\+\hfill 4&\hfill 0.35696898&\hfill 2.34863281&\hfill $-0.02441406$&\hfill    1&\hfill     4&\hfill    0.06258157&\cr
\+\hfill 5&\hfill 0.29438740&\hfill 2.34710693&\hfill 0.12237549&\hfill   $-1$&\hfill     5&\hfill    0.03126018&\cr
\+\hfill 6&\hfill 0.32564758&\hfill 2.34328270&\hfill 0.04902840&\hfill   $-1$&\hfill     6&\hfill    0.01562627&\cr
\+\hfill 7&\hfill 0.34127385&\hfill 2.34251663&\hfill 0.01241460&\hfill   $-1$&\hfill     7&\hfill    0.00781266&\cr
\+\hfill 8&\hfill 0.34908651&\hfill 2.34241964&\hfill $-0.00588631$&\hfill    1&\hfill     7&\hfill    0.00781266&\cr
\+\hfill 9&\hfill 0.34127385&\hfill 2.34237366&\hfill 0.01241385&\hfill   $-1$&\hfill     8&\hfill    0.00390627&\cr
\+\hfill10&\hfill 0.34518012&\hfill 2.34232516&\hfill 0.00326395&\hfill   $-1$&\hfill     9&\hfill    0.00195313&\cr
\+\hfill11&\hfill 0.34713325&\hfill 2.34231879&\hfill $-0.00131090$&\hfill    1&\hfill    10&\hfill    0.00097656&\cr
\+\hfill12&\hfill 0.34615669&\hfill 2.34231751&\hfill 0.00097652&\hfill   $-1$&\hfill    11&\hfill    0.00048828&\cr
\+\hfill13&\hfill 0.34664497&\hfill 2.34231703&\hfill $-0.00016719$&\hfill    1&\hfill    11&\hfill    0.00048828&\cr
\+\hfill14&\hfill 0.34615669&\hfill 2.34231695&\hfill 0.00097652&\hfill   $-1$&\hfill    12&\hfill    0.00024414&\cr
\+\hfill15&\hfill 0.34640083&\hfill 2.34231671&\hfill 0.00040466&\hfill   $-1$&\hfill    13&\hfill    0.00012207&\cr
\+\hfill16&\hfill 0.34652290&\hfill 2.34231666&\hfill 0.00011873&\hfill   $-1$&\hfill    14&\hfill    0.00006104&\cr
\+\hfill17&\hfill 0.34658393&\hfill 2.34231665&\hfill $-0.00002423$&\hfill    1&\hfill    14&\hfill    0.00006104&\cr
\+\hfill18&\hfill 0.34652290&\hfill 2.34231665&\hfill 0.00011873&\hfill   $-1$&\hfill    15&\hfill    0.00003052&\cr
\+\hfill19&\hfill 0.34655342&\hfill 2.34231665&\hfill 0.00004725&\hfill   $-1$&\hfill    16&\hfill    0.00001526&\cr
\+\hfill20&\hfill 0.34656868&\hfill 2.34231665&\hfill 0.00001151&\hfill   $-1$&\hfill    16&\hfill    0.00001526&\cr
\+\hfill21&\hfill 0.34658393&\hfill 2.34231665&\hfill $-0.00002423$&\hfill    1&\hfill    17&\hfill    0.00000763&\cr
\+\hfill22&\hfill 0.34657631&\hfill 2.34231665&\hfill $-0.00000636$&\hfill    1&\hfill    18&\hfill    0.00000381&\cr
\+\hfill23&\hfill 0.34657249&\hfill 2.34231665&\hfill 0.00000258&\hfill   $-1$&\hfill    18&\hfill    0.00000381&\cr
\+\hfill24&\hfill 0.34657631&\hfill 2.34231665&\hfill $-0.00000636$&\hfill&\cr
}
$$
The recursive CORDIC approach to calculating $\tanh^{-1}(T)$ is
$$
\eqalign{
&Z_0 = 0\hbox{\ ,\ } S_0 = C_0T\cr
&Z_{m+1} = Z_m - D_mB_m\cr
&C_{m+1} = C_m + E_mD_mS_m\cr
&S_{m+1} = S_m + E_mD_mC_m\cr
}
$$
where $D_m=\pm1$ is chosen so that $D_mC_m$ and $S_m$
have opposite signs.  This drives
$S_m$ toward 0.  In the process, $Z_m$ is driven toward
$\tanh^{-1}(S_0/C_0)$.
\vfil
\eject
Our interest in the values of the inverse hyperbolic
tangent stems from its connection with logarithms:
$$
\tanh^{-1}(u) = {1\over2}\ln\,{1+u\over1-u}
$$
This can be rewritten in a form more useful to CORDIC:
$$
\ln(x) = 2\tanh^{-1}{x-1\over x+1}
$$
In particular, the calculation above shows that
$2\tanh^{-1}(1/3)=0.69315262$, a good approximation to ln(2) = 0.69314718\dots
This is how CORDIC directly
evaluates logarithms that lie within the scope of the above algorithm.
\vskip .2in
\bf Square roots\rm
\vskip .1in
A few pages back, a question was raised about the inverse tangent algorithm;
namely, what is the eventual value of the $C$-variable?
(Recall that $Z$ is driven toward the desired angle while
$S$ is driven toward 0.)  The answer is that $C$ is driven towards
1/P times the initial value of $\sqrt{C_0^2+S_0^2}$.
The is because the 24-step folding process \it always \rm magnifies
the length of the initial segment by a factor of 1/$P$.
\vskip .1in
A similar question can be raised about the CORDIC algorithm for the inverse
hyperbolic tangent; namely, what is the significance of the terminal value
$C_{24} = 2.34231665$ in the preceding table?
It should come as no surprise that
it is just 1/$Q$ times the initial value of $\sqrt{C_0^2-S_0^2}$
(which is $\sqrt8$).  There is no
geometric model (fan) to make this clear, but it is not hard to verify that
$$
C_{m+1}^2-S_{m+1}^2 = {C_m^2-S_m^2\over[\cosh(B_m)]^2}
$$
by using the hyperbolic identities; this provides an inductive proof.
\vskip .1in
In other words, $\sqrt8 = C_{24}Q$.
This is in fact how CORDIC evaluates square roots, as a \it byproduct \rm of
the calculation of inverse hyperbolic tangents:
\vskip .1in
{
\parindent=0.44in\narrower\smallskip\noindent
If the inverse hyperbolic tangent algorithm is applied to
the seed values $C_0 = x + 0.25$ and $S_0 = x - 0.25$, then $\sqrt{x}=C_{24}Q$,
because $C_0^2-S_0^2=x$.
\smallskip
}
\vskip .1in
In contrast to many of the other evaluations of elementary functions, it is
interesting that this application of
CORDIC \it does \rm require a postmultiplication to complete.
\vfil
\eject
\bf Summary\rm
\vskip .15in
The preceding examples demonstrate the utility and efficiency of the three
recursive equations
$$
\eqalign{
&Z_{m+1} = Z_m - D_mA_m\cr
&C_{m+1} = C_m - kE_mD_mS_m\cr
&S_{m+1} = S_m + E_mD_mC_m\cr
}
$$
for evaluating the standard elementary functions.  In the above display, the
letter $k$ stands for either 1 (circular function mode) or $-1$ (hyperbolic
function mode).  The meanings of the symbols $A_m$ depend on the setting of the
mode indicator $k$.  Each set of values is permanently stored in the hardware,
along with the product of all the cosine values of these special arguments.
The meaning of the symbols $E_m$ also depends on the value of $k$;
in either case,
however, they are powers of 1/2, and thus represent binary-point shifting in
the actual arithmetic.  The remaining numbers are variables whose values
depend on the immediate application.
\vskip .1in
The actual implementation of this theory requires considerable refinement, and
there are features that no doubt vary from one calculator to another.  For
example, achieving satisfactory accuracy requires that the calculator process
more than just two dozen terms; how many of course depends on the number of
significant digits the calculator is designed to display.
\vskip .1in
Another issue that affects the implementation is the conversion of numerical
data from decimal form to binary form or from binary form to decimal form.
The time that this takes can be viewed as the price (not insignificant) that
must be paid for the ease of using the above algorithms.  There are other
options, however.  For instance, it is not necessary to work in binary scale.
The preceding approach could be reworked using powers of 1/10 instead of
powers of 1/2; it is only necessary (as was done for the hyperbolic examples)
to work with lists that contain many duplicate entries.
\vskip .1in
Another detail that has been largely ignored in the whole discussion is the
question of scope.  As described, CORDIC can only handle requests for trigonometric
values that are found in the first quadrant.  This is seen to be an easy
hurdle to get over, thanks to (among other things) the periodicity of the
circular functions.  The question becomes conspicuous, however, when the mode
is switched to hyperbolic.  In the simple version described above, CORDIC can
evaluate ex only for $x$-values between 0.0 and 1.1264, and ln($x$)
only for $x$-values between 1.0 and 9.5149.
It is thus clear that there must be additional
algorithms at work when a calculator evaluates ln(100) = 4.605170186 or when
it evaluates $e^{10} = 22026.46579$  These algorithms are beyond the scope of
this paper.
\vskip .2in
Extending the range of convergence of CORDIC is a significant challenge.  As
reference [3] illustrates, it is a topic of current research.  The optimal
solution has not yet been found.
\vfil
\eject
\bf A final surprise\rm
\vskip .15in
There is no obvious reason for doing so, but setting the
mode variable $k$ equal
to 0 has interesting consequences, if the associated list
of special arguments is
given by $A_m = 2^{-m}$.  The recursive equations now look like
$$
\eqalign{
&Z_{m+1} = Z_m - 2^{-m}D_m\cr
&C_{m+1} = C_m\cr
&S_{m+1} = S_m + 2^{-m}D_mC_m\cr
}
$$
Suppose that initial values $C_0$ and $Z_0$ are given,
$S_0$ is initialized at 0, and
that the $D_m$ are chosen (as usual) to drive $Z_m$ to 0.
In the process, $S_m$ will
be driven toward $Z_0C_0$.  This is how CORDIC does ordinary multiplication!  In
reverse gear, $Z_0$ is initialized at 0 and values $C_0$ and $S_0$ are given.
As $S_m$ is
driven toward 0, $Z_m$ is driven toward $S_0/C_0$.
This is how CORDIC does ordinary division!
\vskip .1in
It is not hard to see why this works.  Take multiplication, for example:  The
result of driving $Z_m$ toward zero is to generate a binary expansion
$$
Z_{24} = D_02^0 + D_12^{-1} + \cdots + D_{23}2^{-23}
$$
in which the coefficients $D_m$ are all $\pm1$.
As above, this approximates $Z_0$ to a
known degree of accuracy.  Meanwhile, the algorithm is generating the value
$$
S_{24} = D_0C_02^0 + D_1C_02^{-1} + \cdots + D_{23}C_02^{-23} = Z_{24}C_0
$$
which approximates $Z_0C_0$.
\vskip .1in
Thus the CORDIC mode $k = 0$ (which might be called the \it linear \rm mode,
in contrast
to the circular mode $k = 1$ and the hyperbolic mode $k = -1$)
also provides the
basic arithmetic services of multiplication and division.
For further details
(and additional references), see the references.
\vskip .25in
Richard Parris \par
Phillips Exeter Academy \par
Exeter, NH   03833-2460
\vskip .3in
\bf References \rm
\vskip .1in
1.\ James Kropa, "Calculator Algorithms", \it Mathematics Magazine\rm,
volume 51 (March 1978), pages 106-109. \par
2.\ Charles Schelin, "Calculator Function Approximation", \it The American
Mathematical Monthly\rm, volume 90 (May 1983), pages 317-325.\par
3.\ Xiaobo Hu, Ronald Harber, and Steven Bass, "Expanding the Range of Con-
vergence of the CORDIC Algorithm", \it IEEE Transactions on Computers\rm,
volume 40 (January 1991), pages 13-21.

\end

