| 1 |
%$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 $
|
| 2 |
|
| 3 |
\chapter[Solutions: \ccfrzeroxrefcomma{}Chapter \ref{ccfr0}]
|
| 4 |
{Solutions: \ccfrzeroxrefcomma{}Chapter \ref{ccfr0}, \ccfrzerolongtitle{}}
|
| 5 |
|
| 6 |
\label{ccfs0}
|
| 7 |
|
| 8 |
\vworkexercisechapterheader{}
|
| 9 |
\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:a01}}
|
| 10 |
Placeholder.
|
| 11 |
|
| 12 |
\end{vworkexercisesolution}
|
| 13 |
\vworkexerciseseparator
|
| 14 |
\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:b01}}
|
| 15 |
Note that $1.609344 > 255/255$ (i.e. beyond the ``corner point''
|
| 16 |
in the sense suggested by Fig. \cfryzeroxrefhyphen{}\ref{fig:cfry0:ili0:00}),
|
| 17 |
so it is necessary to find
|
| 18 |
the Farey neighbors of $1.609344^{-1}$ in $F_{255}$
|
| 19 |
(Algorithm \ccfrzeroxrefhyphen{}\ref{alg:ccfr0:scba0:cfenclosingneighborsfab}),
|
| 20 |
and then invert and re-order the results.
|
| 21 |
|
| 22 |
Table \ref{tbl:ccfs0:exe:cfr0:sexe0:b01:01}
|
| 23 |
shows the application of
|
| 24 |
Algorithm \ccfrzeroxrefhyphen{}\ref{alg:ccfr0:scrn0:akgenalg}
|
| 25 |
to form the continued fraction partial quotients and
|
| 26 |
convergents of $1.609344^{-1}$ = 1,000,000/1,609,344.
|
| 27 |
|
| 28 |
\begin{table}
|
| 29 |
\caption{Continued Fraction Partial Quotients And Convergents Of $1.609344^{-1}$,
|
| 30 |
The Reciprocal Of The Conversion Factor From Miles
|
| 31 |
To Kilometers (Solution To Exercise \ccfrzeroxrefhyphen{}\ref{exe:cfr0:sexe0:b01})}
|
| 32 |
\label{tbl:ccfs0:exe:cfr0:sexe0:b01:01}
|
| 33 |
\begin{center}
|
| 34 |
\begin{tabular}{|c|c|c|c|c|c|c|}
|
| 35 |
\hline
|
| 36 |
\small{Index} & \small{Dividend} & \small{Divisor} & $a_k$ & \small{Remainder} & $p_k$ & $q_k$ \\
|
| 37 |
\small{(k)} & & & & & & \\
|
| 38 |
\hline
|
| 39 |
\hline
|
| 40 |
\small{-1} & \small{N/A} & \small{1,000,000} & \small{N/A} & \small{1,609,344} & \small{1} & \small{0} \\
|
| 41 |
\hline
|
| 42 |
\small{0} & \small{1,000,000} & \small{1,609,344} & \small{0} & \small{1,000,000} & \small{0} & \small{1} \\
|
| 43 |
\hline
|
| 44 |
\small{1} & \small{1,609,344} & \small{1,000,000} & \small{1} & \small{609,344} & \small{1} & \small{1} \\
|
| 45 |
\hline
|
| 46 |
\small{2} & \small{1,000,000} & \small{609,344} & \small{1} & \small{390,656} & \small{1} & \small{2} \\
|
| 47 |
\hline
|
| 48 |
\small{3} & \small{609,344} & \small{390,656} & \small{1} & \small{218,688} & \small{2} & \small{3} \\
|
| 49 |
\hline
|
| 50 |
\small{4} & \small{390,656} & \small{218,688} & \small{1} & \small{171,968} & \small{3} & \small{5} \\
|
| 51 |
\hline
|
| 52 |
\small{5} & \small{218,688} & \small{171,968} & \small{1} & \small{46,720} & \small{5} & \small{8} \\
|
| 53 |
\hline
|
| 54 |
\small{6} & \small{171,968} & \small{46,720} & \small{3} & \small{31,808} & \small{18} & \small{29} \\
|
| 55 |
\hline
|
| 56 |
\small{7} & \small{46,720} & \small{31,808} & \small{1} & \small{14,912} & \small{23} & \small{37} \\
|
| 57 |
\hline
|
| 58 |
\small{8} & \small{31,808} & \small{14,912} & \small{2} & \small{1,984} & \small{64} & \small{103} \\
|
| 59 |
\hline
|
| 60 |
\small{9} & \small{14,912} & \small{1,984} & \small{7} & \small{1,024} & \small{471} & \small{758} \\
|
| 61 |
\hline
|
| 62 |
\small{10} & \small{1,984} & \small{1,024} & \small{1} & \small{960} & \small{535} & \small{861} \\
|
| 63 |
\hline
|
| 64 |
\small{11} & \small{1,024} & \small{960} & \small{1} & \small{64} & \small{1,006} & \small{1,619} \\
|
| 65 |
\hline
|
| 66 |
\small{12} & \small{960} & \small{64} & \small{15} & \small{0} & \small{15,625} & \small{25,146} \\
|
| 67 |
\hline
|
| 68 |
\end{tabular}
|
| 69 |
\end{center}
|
| 70 |
\end{table}
|
| 71 |
|
| 72 |
From the table, the highest-ordered convergent with a denominator not greater
|
| 73 |
than 255 is 64/103. Applying
|
| 74 |
Theorem \ccfrzeroxrefhyphen{}\ref{thm:ccfr0:scba0:convergentbetterappthanlesserdenominator}
|
| 75 |
yields 151/243 as the other neighbor to
|
| 76 |
$1.609344^{-1}$ in $F_{255}$. Inverting and ordering these
|
| 77 |
fractions yields
|
| 78 |
|
| 79 |
\begin{equation}
|
| 80 |
\frac{243}{151} < 1.609344 < \frac{103}{64}.
|
| 81 |
\end{equation}
|
| 82 |
|
| 83 |
Either rational approximation is quite good, but 103/64 is closer
|
| 84 |
to 1.609344 than 243/151, and so we choose 103/64 as the best
|
| 85 |
rational approximation under the constraints.
|
| 86 |
\end{vworkexercisesolution}
|
| 87 |
\vworkexerciseseparator
|
| 88 |
\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:b02}}
|
| 89 |
To find the best rational approximation to 1.609344 with
|
| 90 |
a numerator and denominator no larger than 65,535, first consider the
|
| 91 |
possibility that 1.609344 is already a rational number that can
|
| 92 |
be expressed under these constraints. Examining the final
|
| 93 |
convergent\footnote{For a rational number, the final convergent
|
| 94 |
is the rational number in lowest terms. This is established
|
| 95 |
by Theorem \ccfrzeroxrefhyphen{}\ref{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan}.}
|
| 96 |
of Table \ref{tbl:ccfs0:exe:cfr0:sexe0:b01:01} verifies
|
| 97 |
that 1.609344 = 25,146/15,625. Thus, the best rational
|
| 98 |
approximation under
|
| 99 |
the constraints is 25,146/15,625, which is precisely equal to the
|
| 100 |
number to be approximated.
|
| 101 |
\end{vworkexercisesolution}
|
| 102 |
\vworkexercisechapterfooter
|
| 103 |
|
| 104 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
| 105 |
\vfill
|
| 106 |
\noindent\begin{figure}[!b]
|
| 107 |
\noindent\rule[-0.25in]{\textwidth}{1pt}
|
| 108 |
\begin{tiny}
|
| 109 |
\begin{verbatim}
|
| 110 |
$RCSfile: c_cfs0.tex,v $
|
| 111 |
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cfs0/c_cfs0.tex,v $
|
| 112 |
$Revision: 1.2 $
|
| 113 |
$Author: dtashley $
|
| 114 |
$Date: 2001/07/01 21:10:59 $
|
| 115 |
\end{verbatim}
|
| 116 |
\end{tiny}
|
| 117 |
\noindent\rule[0.25in]{\textwidth}{1pt}
|
| 118 |
\end{figure}
|
| 119 |
|
| 120 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
| 121 |
% $Log: c_cfs0.tex,v $
|
| 122 |
% Revision 1.2 2001/07/01 21:10:59 dtashley
|
| 123 |
% Safety check-in after major re-org.
|
| 124 |
%
|
| 125 |
% Revision 1.1.1.1 2001/07/01 00:14:34 dtashley
|
| 126 |
% Initial import.
|
| 127 |
%
|
| 128 |
%
|
| 129 |
%End of file C_CFS0.TEX
|
Parent Directory
| 
Revision Log