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

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

Parent Directory Parent Directory | Revision Log Revision Log


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