--- pubs/books/ucbka/trunk/c_cfs0/c_cfs0.tex 2016/10/06 03:15:02 4 +++ pubs/books/ucbka/trunk/c_cfs0/c_cfs0.tex 2017/07/03 01:59:16 140 @@ -1,129 +1,129 @@ -%$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 $ - -\chapter[Solutions: \ccfrzeroxrefcomma{}Chapter \ref{ccfr0}] - {Solutions: \ccfrzeroxrefcomma{}Chapter \ref{ccfr0}, \ccfrzerolongtitle{}} - -\label{ccfs0} - -\vworkexercisechapterheader{} -\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:a01}} -Placeholder. - -\end{vworkexercisesolution} -\vworkexerciseseparator -\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:b01}} -Note that $1.609344 > 255/255$ (i.e. beyond the ``corner point'' -in the sense suggested by Fig. \cfryzeroxrefhyphen{}\ref{fig:cfry0:ili0:00}), -so it is necessary to find -the Farey neighbors of $1.609344^{-1}$ in $F_{255}$ -(Algorithm \ccfrzeroxrefhyphen{}\ref{alg:ccfr0:scba0:cfenclosingneighborsfab}), -and then invert and re-order the results. - -Table \ref{tbl:ccfs0:exe:cfr0:sexe0:b01:01} -shows the application of -Algorithm \ccfrzeroxrefhyphen{}\ref{alg:ccfr0:scrn0:akgenalg} -to form the continued fraction partial quotients and -convergents of $1.609344^{-1}$ = 1,000,000/1,609,344. - -\begin{table} -\caption{Continued Fraction Partial Quotients And Convergents Of $1.609344^{-1}$, - The Reciprocal Of The Conversion Factor From Miles - To Kilometers (Solution To Exercise \ccfrzeroxrefhyphen{}\ref{exe:cfr0:sexe0:b01})} -\label{tbl:ccfs0:exe:cfr0:sexe0:b01:01} -\begin{center} -\begin{tabular}{|c|c|c|c|c|c|c|} -\hline -\small{Index} & \small{Dividend} & \small{Divisor} & $a_k$ & \small{Remainder} & $p_k$ & $q_k$ \\ -\small{(k)} & & & & & & \\ -\hline -\hline - \small{-1} & \small{N/A} & \small{1,000,000} & \small{N/A} & \small{1,609,344} & \small{1} & \small{0} \\ -\hline - \small{0} & \small{1,000,000} & \small{1,609,344} & \small{0} & \small{1,000,000} & \small{0} & \small{1} \\ -\hline - \small{1} & \small{1,609,344} & \small{1,000,000} & \small{1} & \small{609,344} & \small{1} & \small{1} \\ -\hline - \small{2} & \small{1,000,000} & \small{609,344} & \small{1} & \small{390,656} & \small{1} & \small{2} \\ -\hline - \small{3} & \small{609,344} & \small{390,656} & \small{1} & \small{218,688} & \small{2} & \small{3} \\ -\hline - \small{4} & \small{390,656} & \small{218,688} & \small{1} & \small{171,968} & \small{3} & \small{5} \\ -\hline - \small{5} & \small{218,688} & \small{171,968} & \small{1} & \small{46,720} & \small{5} & \small{8} \\ -\hline - \small{6} & \small{171,968} & \small{46,720} & \small{3} & \small{31,808} & \small{18} & \small{29} \\ -\hline - \small{7} & \small{46,720} & \small{31,808} & \small{1} & \small{14,912} & \small{23} & \small{37} \\ -\hline - \small{8} & \small{31,808} & \small{14,912} & \small{2} & \small{1,984} & \small{64} & \small{103} \\ -\hline - \small{9} & \small{14,912} & \small{1,984} & \small{7} & \small{1,024} & \small{471} & \small{758} \\ -\hline - \small{10} & \small{1,984} & \small{1,024} & \small{1} & \small{960} & \small{535} & \small{861} \\ -\hline - \small{11} & \small{1,024} & \small{960} & \small{1} & \small{64} & \small{1,006} & \small{1,619} \\ -\hline - \small{12} & \small{960} & \small{64} & \small{15} & \small{0} & \small{15,625} & \small{25,146} \\ -\hline -\end{tabular} -\end{center} -\end{table} - -From the table, the highest-ordered convergent with a denominator not greater -than 255 is 64/103. Applying -Theorem \ccfrzeroxrefhyphen{}\ref{thm:ccfr0:scba0:convergentbetterappthanlesserdenominator} -yields 151/243 as the other neighbor to -$1.609344^{-1}$ in $F_{255}$. Inverting and ordering these -fractions yields - -\begin{equation} -\frac{243}{151} < 1.609344 < \frac{103}{64}. -\end{equation} - -Either rational approximation is quite good, but 103/64 is closer -to 1.609344 than 243/151, and so we choose 103/64 as the best -rational approximation under the constraints. -\end{vworkexercisesolution} -\vworkexerciseseparator -\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:b02}} -To find the best rational approximation to 1.609344 with -a numerator and denominator no larger than 65,535, first consider the -possibility that 1.609344 is already a rational number that can -be expressed under these constraints. Examining the final -convergent\footnote{For a rational number, the final convergent -is the rational number in lowest terms. This is established -by Theorem \ccfrzeroxrefhyphen{}\ref{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan}.} -of Table \ref{tbl:ccfs0:exe:cfr0:sexe0:b01:01} verifies -that 1.609344 = 25,146/15,625. Thus, the best rational -approximation under -the constraints is 25,146/15,625, which is precisely equal to the -number to be approximated. -\end{vworkexercisesolution} -\vworkexercisechapterfooter - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\vfill -\noindent\begin{figure}[!b] -\noindent\rule[-0.25in]{\textwidth}{1pt} -\begin{tiny} -\begin{verbatim} -$RCSfile: c_cfs0.tex,v $ -$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cfs0/c_cfs0.tex,v $ -$Revision: 1.2 $ -$Author: dtashley $ -$Date: 2001/07/01 21:10:59 $ -\end{verbatim} -\end{tiny} -\noindent\rule[0.25in]{\textwidth}{1pt} -\end{figure} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% $Log: c_cfs0.tex,v $ -% Revision 1.2 2001/07/01 21:10:59 dtashley -% Safety check-in after major re-org. -% -% Revision 1.1.1.1 2001/07/01 00:14:34 dtashley -% Initial import. -% -% -%End of file C_CFS0.TEX +%$Header$ + +\chapter[Solutions: \ccfrzeroxrefcomma{}Chapter \ref{ccfr0}] + {Solutions: \ccfrzeroxrefcomma{}Chapter \ref{ccfr0}, \ccfrzerolongtitle{}} + +\label{ccfs0} + +\vworkexercisechapterheader{} +\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:a01}} +Placeholder. + +\end{vworkexercisesolution} +\vworkexerciseseparator +\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:b01}} +Note that $1.609344 > 255/255$ (i.e. beyond the ``corner point'' +in the sense suggested by Fig. \cfryzeroxrefhyphen{}\ref{fig:cfry0:ili0:00}), +so it is necessary to find +the Farey neighbors of $1.609344^{-1}$ in $F_{255}$ +(Algorithm \ccfrzeroxrefhyphen{}\ref{alg:ccfr0:scba0:cfenclosingneighborsfab}), +and then invert and re-order the results. + +Table \ref{tbl:ccfs0:exe:cfr0:sexe0:b01:01} +shows the application of +Algorithm \ccfrzeroxrefhyphen{}\ref{alg:ccfr0:scrn0:akgenalg} +to form the continued fraction partial quotients and +convergents of $1.609344^{-1}$ = 1,000,000/1,609,344. + +\begin{table} +\caption{Continued Fraction Partial Quotients And Convergents Of $1.609344^{-1}$, + The Reciprocal Of The Conversion Factor From Miles + To Kilometers (Solution To Exercise \ccfrzeroxrefhyphen{}\ref{exe:cfr0:sexe0:b01})} +\label{tbl:ccfs0:exe:cfr0:sexe0:b01:01} +\begin{center} +\begin{tabular}{|c|c|c|c|c|c|c|} +\hline +\small{Index} & \small{Dividend} & \small{Divisor} & $a_k$ & \small{Remainder} & $p_k$ & $q_k$ \\ +\small{(k)} & & & & & & \\ +\hline +\hline + \small{-1} & \small{N/A} & \small{1,000,000} & \small{N/A} & \small{1,609,344} & \small{1} & \small{0} \\ +\hline + \small{0} & \small{1,000,000} & \small{1,609,344} & \small{0} & \small{1,000,000} & \small{0} & \small{1} \\ +\hline + \small{1} & \small{1,609,344} & \small{1,000,000} & \small{1} & \small{609,344} & \small{1} & \small{1} \\ +\hline + \small{2} & \small{1,000,000} & \small{609,344} & \small{1} & \small{390,656} & \small{1} & \small{2} \\ +\hline + \small{3} & \small{609,344} & \small{390,656} & \small{1} & \small{218,688} & \small{2} & \small{3} \\ +\hline + \small{4} & \small{390,656} & \small{218,688} & \small{1} & \small{171,968} & \small{3} & \small{5} \\ +\hline + \small{5} & \small{218,688} & \small{171,968} & \small{1} & \small{46,720} & \small{5} & \small{8} \\ +\hline + \small{6} & \small{171,968} & \small{46,720} & \small{3} & \small{31,808} & \small{18} & \small{29} \\ +\hline + \small{7} & \small{46,720} & \small{31,808} & \small{1} & \small{14,912} & \small{23} & \small{37} \\ +\hline + \small{8} & \small{31,808} & \small{14,912} & \small{2} & \small{1,984} & \small{64} & \small{103} \\ +\hline + \small{9} & \small{14,912} & \small{1,984} & \small{7} & \small{1,024} & \small{471} & \small{758} \\ +\hline + \small{10} & \small{1,984} & \small{1,024} & \small{1} & \small{960} & \small{535} & \small{861} \\ +\hline + \small{11} & \small{1,024} & \small{960} & \small{1} & \small{64} & \small{1,006} & \small{1,619} \\ +\hline + \small{12} & \small{960} & \small{64} & \small{15} & \small{0} & \small{15,625} & \small{25,146} \\ +\hline +\end{tabular} +\end{center} +\end{table} + +From the table, the highest-ordered convergent with a denominator not greater +than 255 is 64/103. Applying +Theorem \ccfrzeroxrefhyphen{}\ref{thm:ccfr0:scba0:convergentbetterappthanlesserdenominator} +yields 151/243 as the other neighbor to +$1.609344^{-1}$ in $F_{255}$. Inverting and ordering these +fractions yields + +\begin{equation} +\frac{243}{151} < 1.609344 < \frac{103}{64}. +\end{equation} + +Either rational approximation is quite good, but 103/64 is closer +to 1.609344 than 243/151, and so we choose 103/64 as the best +rational approximation under the constraints. +\end{vworkexercisesolution} +\vworkexerciseseparator +\begin{vworkexercisesolution}{\ref{exe:cfr0:sexe0:b02}} +To find the best rational approximation to 1.609344 with +a numerator and denominator no larger than 65,535, first consider the +possibility that 1.609344 is already a rational number that can +be expressed under these constraints. Examining the final +convergent\footnote{For a rational number, the final convergent +is the rational number in lowest terms. This is established +by Theorem \ccfrzeroxrefhyphen{}\ref{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan}.} +of Table \ref{tbl:ccfs0:exe:cfr0:sexe0:b01:01} verifies +that 1.609344 = 25,146/15,625. Thus, the best rational +approximation under +the constraints is 25,146/15,625, which is precisely equal to the +number to be approximated. +\end{vworkexercisesolution} +\vworkexercisechapterfooter + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\vfill +\noindent\begin{figure}[!b] +\noindent\rule[-0.25in]{\textwidth}{1pt} +\begin{tiny} +\begin{verbatim} +$RCSfile: c_cfs0.tex,v $ +$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cfs0/c_cfs0.tex,v $ +$Revision: 1.2 $ +$Author: dtashley $ +$Date: 2001/07/01 21:10:59 $ +\end{verbatim} +\end{tiny} +\noindent\rule[0.25in]{\textwidth}{1pt} +\end{figure} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% $Log: c_cfs0.tex,v $ +% Revision 1.2 2001/07/01 21:10:59 dtashley +% Safety check-in after major re-org. +% +% Revision 1.1.1.1 2001/07/01 00:14:34 dtashley +% Initial import. +% +% +%End of file C_CFS0.TEX