/[dtapublic]/pubs/books/ucbka/trunk/c_cfs0/c_cfs0.tex
ViewVC logotype

Contents of /pubs/books/ucbka/trunk/c_cfs0/c_cfs0.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4 - (show annotations) (download) (as text)
Thu Oct 6 03:15:02 2016 UTC (6 years, 2 months ago) by dashley
File MIME type: application/x-tex
File size: 6169 byte(s)
Initial commit after migrating from CVS.
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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25