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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 278 - (show annotations) (download) (as text)
Wed Aug 14 23:10:36 2019 UTC (4 years, 6 months 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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25