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