%$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cfs0/c_cfs0.tex,v 1.2 2001/07/01 21:10:59 dtashley Exp $

\chapter[Solutions: \ccfrzeroxrefcomma{}Chapter \ref{ccfr0}]
        {Solutions: \ccfrzeroxrefcomma{}Chapter \ref{ccfr0}, \ccfrzerolongtitle{}}

\label{ccfs0}

\vworkexercisechapterheader{}
\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:a01}}
Placeholder.

\end{vworkexercisesolution}
\vworkexerciseseparator
\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:b01}}
Note that $1.609344 > 255/255$ (i.e. beyond the ``corner point''
in the sense suggested by Fig. \cfryzeroxrefhyphen{}\ref{fig:cfry0:ili0:00}), 
so it is necessary to find
the Farey neighbors of $1.609344^{-1}$ in $F_{255}$
(Algorithm \ccfrzeroxrefhyphen{}\ref{alg:ccfr0:scba0:cfenclosingneighborsfab}),
and then invert and re-order the results.

Table \ref{tbl:ccfs0:exe:cfr0:sexe0:b01:01} 
shows the application of 
Algorithm \ccfrzeroxrefhyphen{}\ref{alg:ccfr0:scrn0:akgenalg}
to form the continued fraction partial quotients and
convergents of $1.609344^{-1}$ = 1,000,000/1,609,344.

\begin{table}
\caption{Continued Fraction Partial Quotients And Convergents Of $1.609344^{-1}$, 
         The Reciprocal Of The Conversion Factor From Miles
         To Kilometers (Solution To Exercise \ccfrzeroxrefhyphen{}\ref{exe:cfr0:sexe0:b01})}
\label{tbl:ccfs0:exe:cfr0:sexe0:b01:01}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\small{Index}     &      \small{Dividend}  &       \small{Divisor} &  $a_k$ &   \small{Remainder} & $p_k$ & $q_k$ \\
\small{(k)}       &                        &                       &        &                     &       &       \\
\hline
\hline
       \small{-1} & \small{N/A}            & \small{1,000,000}     &     \small{N/A} &   \small{1,609,344}   &      \small{1} &       \small{0}  \\
\hline
       \small{0}  & \small{1,000,000}      & \small{1,609,344}     &     \small{0}   &   \small{1,000,000}   &      \small{0} &       \small{1}  \\
\hline
       \small{1}  & \small{1,609,344}      & \small{1,000,000}     &     \small{1}   &     \small{609,344}   &      \small{1} &       \small{1}  \\
\hline
       \small{2}  & \small{1,000,000}      &   \small{609,344}     &     \small{1}   &     \small{390,656}   &      \small{1} &       \small{2}  \\
\hline
       \small{3}  &   \small{609,344}      &   \small{390,656}     &     \small{1}   &     \small{218,688}   &      \small{2} &       \small{3}  \\
\hline
       \small{4}  &   \small{390,656}      &   \small{218,688}     &     \small{1}   &     \small{171,968}   &      \small{3} &       \small{5}  \\
\hline
       \small{5}  &   \small{218,688}      &   \small{171,968}     &     \small{1}   &      \small{46,720}   &      \small{5} &       \small{8}  \\
\hline
       \small{6}  &   \small{171,968}      &    \small{46,720}     &     \small{3}   &      \small{31,808}   &     \small{18} &      \small{29}  \\
\hline
       \small{7}  &    \small{46,720}      &    \small{31,808}     &     \small{1}   &      \small{14,912}   &     \small{23} &      \small{37}  \\
\hline
       \small{8}  &    \small{31,808}      &    \small{14,912}     &     \small{2}   &       \small{1,984}   &     \small{64} &     \small{103}  \\
\hline
       \small{9}  &    \small{14,912}      &     \small{1,984}     &     \small{7}   &       \small{1,024}   &    \small{471} &     \small{758}  \\
\hline
      \small{10}  &     \small{1,984}      &     \small{1,024}     &     \small{1}   &         \small{960}   &    \small{535} &     \small{861}  \\
\hline
      \small{11}  &     \small{1,024}      &       \small{960}     &     \small{1}   &          \small{64}   &  \small{1,006} &   \small{1,619} \\
\hline
      \small{12}  &       \small{960}      &        \small{64}     &    \small{15}   &           \small{0}   & \small{15,625} &  \small{25,146} \\
\hline
\end{tabular}
\end{center}
\end{table}

From the table, the highest-ordered convergent with a denominator not greater
than 255 is 64/103.  Applying 
Theorem \ccfrzeroxrefhyphen{}\ref{thm:ccfr0:scba0:convergentbetterappthanlesserdenominator}
yields 151/243 as the other neighbor to 
$1.609344^{-1}$ in $F_{255}$.  Inverting and ordering these 
fractions yields

\begin{equation}
\frac{243}{151} < 1.609344 < \frac{103}{64}.
\end{equation}

Either rational approximation is quite good, but 103/64 is closer
to 1.609344 than 243/151, and so we choose 103/64 as the best
rational approximation under the constraints.
\end{vworkexercisesolution}
\vworkexerciseseparator
\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:b02}}
To find the best rational approximation to 1.609344 with
a numerator and denominator no larger than 65,535, first consider the
possibility that 1.609344 is already a rational number that can
be expressed under these constraints.  Examining the final
convergent\footnote{For a rational number, the final convergent
is the rational number in lowest terms.  This is established
by Theorem \ccfrzeroxrefhyphen{}\ref{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan}.}
of Table \ref{tbl:ccfs0:exe:cfr0:sexe0:b01:01} verifies
that 1.609344 = 25,146/15,625.  Thus, the best rational 
approximation under
the constraints is 25,146/15,625, which is precisely equal to the
number to be approximated.
\end{vworkexercisesolution}
\vworkexercisechapterfooter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vfill
\noindent\begin{figure}[!b]
\noindent\rule[-0.25in]{\textwidth}{1pt}
\begin{tiny}
\begin{verbatim}
$RCSfile: c_cfs0.tex,v $
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cfs0/c_cfs0.tex,v $
$Revision: 1.2 $
$Author: dtashley $
$Date: 2001/07/01 21:10:59 $
\end{verbatim}
\end{tiny}
\noindent\rule[0.25in]{\textwidth}{1pt}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Log: c_cfs0.tex,v $
% Revision 1.2  2001/07/01 21:10:59  dtashley
% Safety check-in after major re-org.
%
% Revision 1.1.1.1  2001/07/01 00:14:34  dtashley
% Initial import.
%
%
%End of file C_CFS0.TEX