 # Contents of /pubs/books/ucbka/trunk/c_ras0/c_ras0.tex

Wed Aug 14 23:10:36 2019 UTC (4 years, 1 month ago) by dashley
File MIME type: application/x-tex
File size: 2532 byte(s)
Change keyword substitution (migration from cvs to svn).

 1 %$Header$ 2 3 \chapter[Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}] 4 {Solutions: \cratzeroxrefcomma{}Chapter \ref{crat0}, \cratzerolongtitle{}} 5 6 \label{cras0} 7 8 \vworkexercisechapterheader{} 9 \begin{vworkexercisesolution}{\ref{exe:crat0:sexe0:01}} 10 The value of the \texttt{state} variable when 11 evaluating the \emph{if()} clause on the 12 $n+1$'th invocation is 13 14 \begin{equation} 15 \label{eq:cras0:exe01:01} 16 K_1 - nK_4 + (n+1) K_2 . 17 \end{equation} 18 19 We require on the $n+1$'th invocation, in order for the 20 test of the \emph{if()} clause to fail (i.e. that the function 21 \texttt{A()}'' has been run on the first $n$ invocations of 22 the base subroutine but is not run on the $n+1$'th invocation), 23 that: 24 25 \begin{equation} 26 \label{eq:cras0:exe01:01b} 27 K_1 - nK_4 + (n+1) K_2 < K_3. 28 \end{equation} 29 30 Solving this inequality for the smallest integral 31 value of $n$ yields: 32 33 \begin{equation} 34 \label{eq:cras0:exe01:01c} 35 n = \left\lceil 36 \frac{K_1 + K_2 - K_3 + 1}{K_4 - K_2} 37 \right\rceil . 38 \end{equation} 39 40 It can be verified using an example that 41 (\ref{eq:cras0:exe01:01c}). For example, with 42 $K_1 = 10$, $K_2 = 3$, $K_3 = 7$, and $K_4 = 5$, 43 (\ref{eq:cras0:exe01:01}) predicts that on the first 44 $\lceil 7/2 \rceil = 4$ invocations of the base subroutine 45 the subroutine \texttt{A()}'' will be run but on the 5th 46 invocation it will not. Tracing the algorithm with the 47 parameters specified reveals that at the 48 test in the \emph{if()} statement 49 on the first invocation of the 50 subroutine, \texttt{state}=13 (\texttt{A()}'' executed); 51 on the second invocation of the 52 subroutine, \texttt{state}=11 (\texttt{A()}'' executed); 53 on the third invocation of the 54 subroutine, \texttt{state}=9 (\texttt{A()}'' executed); 55 on the fourth invocation of the 56 subroutine, \texttt{state}=7 (\texttt{A()}'' executed); 57 and on the fifth invocation of the 58 subroutine, \texttt{state}=5 (\texttt{A()}'' not executed). 59 This is in agreement with 60 (\ref{eq:cras0:exe01:01}). 61 \end{vworkexercisesolution} 62 %\vworkexerciseseparator 63 %\begin{vworkexercisesolution}{\ref{exe:cfry0:sexe0:02}} 64 %Placeholder. 65 %\end{vworkexercisesolution} 66 \vworkexercisechapterfooter 67 68 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 69 \vfill 70 \noindent\begin{figure}[!b] 71 \noindent\rule[-0.25in]{\textwidth}{1pt} 72 \begin{tiny} 73 \begin{verbatim} 74 $HeadURL$ 75 $Revision$ 76 $Date$ 77 $Author$ 78 \end{verbatim} 79 \end{tiny} 80 \noindent\rule[0.25in]{\textwidth}{1pt} 81 \end{figure} 82 83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 84 % 85 %End of file C_RAS0.TEX

## Properties

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