# Annotation of /pubs/books/ucbka/trunk/c_cfs0/c_cfs0.tex

Mon Aug 12 00:47:10 2019 UTC (4 years, 11 months ago) by dashley
File MIME type: application/x-tex
File size: 5595 byte(s)
Change keyword substitution (migration from cvs to svn).

 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 80 \frac{243}{151} < 1.609344 < \frac{103}{64}. 81 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

## Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision URL Header