\documentclass{beamer}
\usepackage{graphics,amsmath}
%\geometry{paperheight=8.5in,paperwidth=11in,tmargin=0.75in,bmargin=0.75in,inner=0.75in,outer=0.75in}
\usetheme{AnnArbor}
\DeclareMathOperator{\arctanh}{arctanh}
\DeclareMathOperator{\sgn}{sgn}
\renewcommand{\today}{April 25, 1997}
\usecolortheme{dolphin}
\author{Helmut Knaust}
\title{ How Do Calculators Calculate?}
\begin{document}
\begin{frame}
\begin{center}
{\bf How Do Calculators Calculate?}\\[4\baselineskip]
\textsc{Helmut Knaust\smallskip\\
Department of Mathematical Sciences\\
University of Texas at El Paso}
\end{center}
\end{frame}

\section{History}
\begin{frame}
We give an introduction to the 
\begin{center}
{\bf CORDIC met\-hod}
\end{center}
 used my most handheld calculators (such as the ones by Texas Instruments and Hewlett-Packard) to approximate the standard transcendental functions.

The CORDIC algorithm does not use Calculus based methods such as polynomial or rational function approximation.
\end{frame}

\begin{frame}
The CORDIC (= {\bf CO}ordinate {\bf R}otation {\bf DI}gital {\bf C}omputer) algorithm was developed by 
\begin{center}
{\bf Jack E. Volder}
\end{center}
 in 1959.


His objective was to build a real-time navigational computer for use on 
aircrafts, so he was primarily interested in computing trigonometric 
functions.



Subsequently, the CORDIC scheme was extended by 
\begin{center}
{\bf J. Walther}
\end{center}
in 1971 to other transcendental functions.
\end{frame}


\section{Introduction}
\begin{frame}
Hand-held calculators do not convert numbers to base 2.



They use a binary-coded decimal (BCD) system instead.



Calculators can only perform four operations inexpensively:
\begin{enumerate}
\item {\bf Addition} and {\bf Subtraction}
\item {\bf Storing}  in memory and {\bf Retrieving} from memory
\item {\bf Digit shift} (multiplication/division by  the base)
\item {\bf Comparisons}
\end{enumerate}
\end{frame}



\begin{frame}
The CORDIC Algorithm is a unified computational scheme to perform
\begin{enumerate}
\item multiplication and division
\item computations of  the trigonometric functions
\begin{center}
$\sin, \cos, \arctan$
\end{center}
\item computations of  the hyperbolic trigonometric functions
\begin{center}
$\sinh, \cosh, \arctanh$
\end{center}
\item  and consequently can also compute the exponential function, the natural logarithm and the square root
\end{enumerate}
\end{frame}


\begin{frame}
\begin{center}
{\bf The CORDIC Algorithm\\
(Binary Version)}
\end{center}


\begin{eqnarray}
x_{k+1}&=&x_k- m \delta_k y_k 2^{-k}\\
y_{k+1}&=&y_k+\delta_k x_k 2^{-k}\\
z_{k+1}&=&z_k-\delta_k \varepsilon_k\\[2\baselineskip]
\delta_k&=&\pm 1 \mbox{ (depending on $y_k$ or $z_k$)}\\[2\baselineskip]
m&=&0,\pm 1\end{eqnarray}
The $\varepsilon_k$'s  are prestored constants.

\end{frame}

\section{Example 1}
\begin{frame}
\begin{center}
{\bf A Warm-Up Example:\\
Multiplication}
\end{center}
To compute the product of $a$ and $b$ for  $|a|\leq 2$ and $|b|\leq 2$ we let 
\[m=0,\ \varepsilon_k=2^{-k}.\] 
The scheme becomes
\begin{eqnarray}
x_{k+1}&=&x_k\quad(=x_0)\\
y_{k+1}&=&y_k+\delta_k x_k 2^{-k}\\
z_{k+1}&=&z_k-\delta_k 2^{-k}\\[\baselineskip]
\delta_k&=&\sgn (z_k)\\[\baselineskip]
x_0&=&a\\
y_0&=&0\\
z_0&=&b
\end{eqnarray}
\end{frame}


\begin{frame}
From the previous examples we suspect that $z_n\to 0$ and that $y_n\to ab$. Let's check:


\begin{theorem}
$|z_{n+1}|\leq 2^{-n}$
\end{theorem}

{\bf Proof by induction:} By the restriction placed on $b$ 
\[|z_0|=|b|\leq 2^{-(-1)}=2.\]


Now suppose $|z_n|\leq 2^{-(n-1)}=2^{-n+1}$. By definition $z_{n+1}=z_n- \sgn (z_n) 2^{-n}$. There are two cases to consider:


If $0\leq z_n\leq 2^{-n+1}$, then $\sgn (z_n)=1$, and consequently
$-2^{-n} \leq z_{n+1}\leq 2^{-n}$.


If on the other hand $-2^{-n+1}\leq z_n<0$, then $\sgn(z_n)=-1$, and consequently $-2^{-n} \leq z_{n+1}\leq 2^{-n}$.
\end{frame}


\begin{frame}
\begin{theorem}
$|y_{n+1}- a b|\leq 2^{-n+1}$
\end{theorem}

{\bf Proof:} Note that the iterative formulas imply:
\[z_{n+1}=z_0-\sum_{k=0}^n \delta_k 2^{-k},\]
and
\[y_{n+1}=y_0+\left(\sum_{k=0}^n \delta_k 2^{-k}\right)x_0.\]
Consequently
\begin{eqnarray*}
|y_{n+1}- a b|&=&|y_{n+1}- x_0 z_0|\\
&=&\left|\left(y_0+(z_0-z_{n+1})x_0\right)-x_0 z_0\right|\\
&=&|0-z_{n+1}x_0|\\
&\leq&2^{-n}\cdot 2=2^{-n+1}
\end{eqnarray*}
\end{frame}


\section{Example 2}
\begin{frame}
\begin{center}
{\bf An Example: 
Computing $\sin$ and $\cos$}
\end{center}
To compute $\sin \theta$ and $\cos \theta$ for $|\theta|\leq\pi/2$ we let 
\[m=1,\ \varepsilon_k=\arctan(2^{-k}).\] 
We also define 
\[C=\prod_{k=0}^n \cos(\varepsilon_k).\]
The scheme becomes
\begin{eqnarray}
x_{k+1}&=&x_k- \delta_k y_k 2^{-k}\\
y_{k+1}&=&y_k+\delta_k x_k 2^{-k}\\
z_{k+1}&=&z_k-\delta_k \varepsilon_k\\%[2\baselineskip]
\delta_k&=&\sgn (z_k)\\%[2\baselineskip]
x_0&=&C\\
y_0&=&0\\
z_0&=&\theta
\end{eqnarray}
\end{frame}

\section{The CORDIC Theorem}
\begin{frame}
\begin{theorem}
{\bf The Cordic Representation Theorem}
\end{theorem}
{\em Suppose $(\varepsilon_k)_{k=0}^n$ is a decreasing sequence of positive real numbers satisfying
\[\varepsilon_k \leq\left(\sum_{j=k+1}^n \varepsilon_j\right)+\varepsilon_n\]
for $k=0,1,\dots,n$, and suppose $r$ is a real number such that 
\[|r|\leq\sum_{k=0}^n \varepsilon_j.\]
If $s_0=0$, and $s_{k+1}=s_k+\delta_k \varepsilon_k$, for $k=0,1,\ldots,n$, where
$\delta_k=\sgn\left(r-s_k\right)$.
Then
\[|r-s_{n+1}|=|r-\sum_{k=0}^n \delta_k\varepsilon_k|< \varepsilon_n.\vspace*{\fill}\]}
{\bf Proof:} By induction.

\end{frame}



\begin{frame}
The previous theorem  and some computations tell us that it is possible to write the angle $r=\theta$ as a combination of the angles $\varepsilon_k$, more precisely, we can choose $\delta_k=\pm1$ so that 
\[|\theta-\sum_{k=0}^n\delta_k \varepsilon_k|<\varepsilon_n.\]
Set $s_{n+1}=\sum_{k=0}^n\delta_k \varepsilon_k$.
\end{frame}

\begin{frame}
\begin{center}
\resizebox{.9\textwidth}{!}{\includegraphics{cordic1.pdf}} 
\end{center}
\end{frame}

\begin{frame}
We then have the following

\begin{theorem}
If $x_0=\prod_{k=0}^n \cos \varepsilon_k$ and $y_0=0$, then
$x_ {n+1}=\cos s_{n+1}$ and $y_{n+1}=\sin s_{n+1}$.
\end{theorem}


\noindent{\bf Proof (by induction, sketch):} 
\begin{eqnarray*}x_{n+1}&=&x_n-\delta_n y_n 2^{-n}\\
&=&\left(\cos s_{n}\cos \varepsilon_n\right)-\delta_n \left(\sin s_{n}\cos \varepsilon_n\right) \tan \varepsilon_n\\
&=&\cos s_{n} \cos \varepsilon_n -\delta_n \sin s_{n}\sin\varepsilon_n\\
&=&\cos( s_{n}+\delta_n \varepsilon_n)\\
&=& \cos( s_{n+1})
\end{eqnarray*}
\end{frame}

\section{Computing Transcendental Functions}
\begin{frame}
\begin{center}
{\bf Trigonometric Functions}
\end{center}


$\underline{m=1}$ 
\begin{enumerate}
\item
$x_{n+1}\approx \cos \theta$, $y_{n+1}\approx\sin\theta$:\medskip\\
$\varepsilon_k=\arctan(2^{-k})$, $\delta_k=\sgn z_k$,\\
$x_0=\prod_{k=0}^n \cos(\varepsilon_k)$, $y_0=0$, $z_0=\theta$
\item
$z_{n+1}\approx\arctan(y_0/x_0)$:\medskip\\
$\varepsilon_k=\arctan(2^{-k})$, $\delta_k=-\sgn y_k$,\\
$z_0=0$
\end{enumerate}
\end{frame}

\begin{frame}
\begin{center}
{\bf Hyperbolic Functions}
\end{center}


$\underline{m=-1}$ 
\begin{enumerate}
\item
$x_{n+1}\approx \cosh \theta$, $y_{n+1}\approx\sinh\theta$,\\ and thus $x_{n+1}+y_{n+1}\approx e^\theta$:\medskip\\
$\varepsilon_k=\arctanh (2^{-k})$ (repeated), $\delta_k=\sgn z_k$,\\
$x_0=C'$, $y_0=0$, $z_0=\theta$
\item
$z_{n+1}\approx\arctanh (y_0/x_0)$, $x_{n+1}\approx C' \sqrt{x_0^2-y_0^2}$, \\
and thus we obtain an approximation of $\displaystyle{\ln x=2\  \arctanh \left(\frac{x-1}{x+1}\right)}$:\medskip\\
$\varepsilon_k=\arctanh(2^{-k})$ (repeated), $\delta_k=-\sgn y_k$,\\
$z_0=0$
\end{enumerate}
\end{frame}

\section{Multiplication and Division}
\begin{frame}
\begin{center}
{\bf Multiplication and Division}
\end{center}
$\underline{m=0}$ 
\begin{enumerate}
\item
$y_{n+1}\approx x_0 z_0$:\medskip\\
$\varepsilon_k=2^{-k}$, $\delta_k=\sgn z_k$,\\
$y_0=0$
\item
$z_{n+1}\approx y_0/x_0$:\medskip\\
$\varepsilon_k=2^{-k}$, $\delta_k=-\sgn y_k$,\\
$z_0=0$
\end{enumerate}
\end{frame}
 
\section{} 
\begin{frame}
\begin{center}
{\bf References}
\end{center}
\begin{enumerate}
\item Charles W. Schelin\\{\em Calculator Function Approximation}\\
American Math. Monthly 90, 1983, 317--325.
\item Jack E. Volder\\{\em The CORDIC Trigonometric Computing Technique}\\
IRE Transcactions EC-8, 1959, 330--334
\item Richard J. Pulskamp and James A. Delaney\\
{\em Computer and Calculator Computation of Elementary Functions}\\
UMAP Module 708, 1991.\vfill
\end{enumerate}
\begin{flushright}{\footnotesize Beamer version: December 2012.\\Last edit: December 2020.}\end{flushright}
\end{frame}
\end{document}
