| 1 |
dashley |
140 |
%$Header$ |
| 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 |
dashley |
275 |
$HeadURL$ |
| 111 |
|
|
$Revision$ |
| 112 |
|
|
$Date$ |
| 113 |
|
|
$Author$ |
| 114 |
dashley |
140 |
\end{verbatim} |
| 115 |
|
|
\end{tiny} |
| 116 |
|
|
\noindent\rule[0.25in]{\textwidth}{1pt} |
| 117 |
|
|
\end{figure} |
| 118 |
|
|
|
| 119 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 120 |
|
|
% |
| 121 |
|
|
%End of file C_CFS0.TEX |
Parent Directory
| 
Revision Log