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

revision 4 by dashley, Thu Oct 6 03:15:02 2016 UTC revision 140 by dashley, Mon Jul 3 01:59:16 2017 UTC
# Line 1  Line 1
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
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
80  \frac{243}{151} < 1.609344 < \frac{103}{64}.  \frac{243}{151} < 1.609344 < \frac{103}{64}.
81
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

Legend:
 Removed from v.4 changed lines Added in v.140