4.3.1 The Classical Algorithms

1 files changed, 1608 insertions, 0 deletions

diff --git a/vol2/4.3.1.lyx b/vol2/4.3.1.lyx
new file mode 100644
index 0000000..b541c7e
--- /dev/null
+++ b/vol2/4.3.1.lyx
@@ -0,0 +1,1608 @@
+#LyX 2.4 created this file. For more info see https://www.lyx.org/
+\lyxformat 620
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input defs
+\end_preamble
+\use_default_options true
+\maintain_unincluded_children no
+\language english
+\language_package default
+\inputencoding utf8
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement class
+\float_alignment class
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_formatted_ref 0
+\use_minted 0
+\use_lineno 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes false
+\output_changes false
+\change_bars false
+\postpone_fragile_content false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\docbook_mathml_prefix 1
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+16+4;
+ 6,
+ 9,
+ 11,
+ 14,
+ 16,
+ 19,
+ 21,
+ 22,
+ 30,
+ 37,
+ 43 (2:58) -> 12d,
+ -2/3
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc6[22]
+\end_layout
+
+\end_inset
+
+Design an algorithm that adds from left to right (as in exercise 5),
+ but never stores a digit of the answer until this digit cannot possibly be affected by future carries;
+ there is to be no changing of any answer digit once it has been stored.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+This algorithm adds two numbers 
+\begin_inset Formula $u=(u_{n-1}\dots u_{0})_{b}$
+\end_inset
+
+ and 
+\begin_inset Formula $v=(v_{n-1}\dots v_{0})_{b}$
+\end_inset
+
+ and stores the answer as 
+\begin_inset Formula $w=(w_{n}\dots w_{0})_{b}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+[Initialize.] Let 
+\begin_inset Formula $i\gets n-1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $c\gets0$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $r\gets0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:e4316b"
+
+\end_inset
+
+[Add digits.] Let 
+\begin_inset Formula $s\gets u_{i}+v_{i}$
+\end_inset
+
+.
+ 
+\end_layout
+
+\begin_layout Enumerate
+[Check if we can propagate carry.] If 
+\begin_inset Formula $s=b-1$
+\end_inset
+
+,
+ set 
+\begin_inset Formula $c\gets c+1$
+\end_inset
+
+ and go to step 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "enu:e4316g"
+plural "false"
+caps "false"
+noprefix "false"
+nolink "false"
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+[Check our carry.] If 
+\begin_inset Formula $s\geq b$
+\end_inset
+
+,
+ set 
+\begin_inset Formula $w_{i+c+1}\gets r+1$
+\end_inset
+
+,
+ 
+\begin_inset Formula $s\gets s-b$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $w_{i+k}\gets0$
+\end_inset
+
+ for 
+\begin_inset Formula $k=1,\dots,c$
+\end_inset
+
+;
+ otherwise set 
+\begin_inset Formula $w_{i+c+1}\gets r$
+\end_inset
+
+ and 
+\begin_inset Formula $w_{i+k}\gets b-1$
+\end_inset
+
+ for 
+\begin_inset Formula $k=1,\dots,c$
+\end_inset
+
+.
+ Then set 
+\begin_inset Formula $c\gets0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:e4316g"
+
+\end_inset
+
+[Loop on 
+\begin_inset Formula $i$
+\end_inset
+
+.] If 
+\begin_inset Formula $i=0$
+\end_inset
+
+,
+ set 
+\begin_inset Formula $w_{0}\gets s$
+\end_inset
+
+,
+ 
+\begin_inset Formula $w_{k}\gets b-1$
+\end_inset
+
+ for 
+\begin_inset Formula $k=1,\dots,c$
+\end_inset
+
+,
+ and terminate the algorithm.
+ Otherwise set 
+\begin_inset Formula $r\gets s$
+\end_inset
+
+,
+ 
+\begin_inset Formula $i\gets i-1$
+\end_inset
+
+,
+ and go back to step 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "enu:e4316b"
+plural "false"
+caps "false"
+noprefix "false"
+nolink "false"
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc9[21]
+\end_layout
+
+\end_inset
+
+Generalize Algorithm A to obtain an algorithm that adds two 
+\begin_inset Formula $n$
+\end_inset
+
+-place numbers in a 
+\emph on
+mixed-radix
+\emph default
+ number system,
+ with bases 
+\begin_inset Formula $b_{0}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $b_{1}$
+\end_inset
+
+,
+ ...
+ (from right to left).
+ Thus the least significant digits lie between 0 and 
+\begin_inset Formula $b_{0}-1$
+\end_inset
+
+,
+ the next digits lie between 0 and 
+\begin_inset Formula $b_{1}-1$
+\end_inset
+
+,
+ etc.;
+ see Eq.
+ 4.1–(9).
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Just change 
+\begin_inset Formula $b$
+\end_inset
+
+ to 
+\begin_inset Formula $b_{j}$
+\end_inset
+
+ in the two occurrences of step A2.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc11[10]
+\end_layout
+
+\end_inset
+
+Design an algorithm that compares two nonnegative 
+\begin_inset Formula $n$
+\end_inset
+
+-place integers 
+\begin_inset Formula $u=(u_{n-1}\dots u_{1}u_{0})_{b}$
+\end_inset
+
+ and 
+\begin_inset Formula $v=(v_{n-1}\dots v_{1}v_{0})_{b}$
+\end_inset
+
+,
+ to determine whether 
+\begin_inset Formula $u<v$
+\end_inset
+
+,
+ 
+\begin_inset Formula $u=v$
+\end_inset
+
+,
+ or 
+\begin_inset Formula $u>v$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+[Initialize.] Set 
+\begin_inset Formula $i\gets n-1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+[Compare.] If 
+\begin_inset Formula $u_{i}>v_{i}$
+\end_inset
+
+,
+ report that 
+\begin_inset Formula $u>v$
+\end_inset
+
+.
+ Otherwise,
+ if 
+\begin_inset Formula $u_{i}<v_{i}$
+\end_inset
+
+,
+ report that 
+\begin_inset Formula $u<v$
+\end_inset
+
+.
+ Otherwise,
+ if 
+\begin_inset Formula $i=0$
+\end_inset
+
+,
+ report that 
+\begin_inset Formula $u=v$
+\end_inset
+
+.
+ Otherwise set 
+\begin_inset Formula $i\gets i-1$
+\end_inset
+
+ and repeat this step.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc14[M22]
+\end_layout
+
+\end_inset
+
+Give a formal proof of the validity of Algorithm M,
+ using the method of inductive assertions explained in Section 1.2.1.
+ (See exercise 4.)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Consider the following diagram:
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{center}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{tikzpicture}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+path (0,0) node[draw](M1){M1} (1.5,0) node[draw](M2){M2}
+\end_layout
+
+\begin_layout Plain Layout
+
+      (3,0) node[draw](M3){M3} (4.5,0) node[draw](M4){M4}
+\end_layout
+
+\begin_layout Plain Layout
+
+      (6,0) node[draw](M5){M5} (7.5,0) node[draw](M5p){$
+\backslash
+text{M5}'$}
+\end_layout
+
+\begin_layout Plain Layout
+
+      (9,0) node[draw](M6){M6}
+\end_layout
+
+\begin_layout Plain Layout
+
+      (10,0) node[circle,draw,inner sep=2pt](END){$
+\backslash
+cdot$};
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+filldraw (-1,0) circle(2pt);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (-1,0) -- (M1);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M1) -- (M2);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M2) to[bend right] (M6);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M2) -- (M3);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M3) -- (M4);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M4) -- (M5);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M5) to[bend right] (M4);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M5) -- (M5p);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M5p) -- (M6);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M6) to[bend right] (M2);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+draw[->] (M6) -- (END);
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{tikzpicture}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{center}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Here 
+\begin_inset Formula $\text{M5}'$
+\end_inset
+
+ refers to the instruction 
+\begin_inset Formula $w_{j+m}\gets k$
+\end_inset
+
+ in M5,
+ which is only run in the final iteration of the inner loop.
+ The arrow from M6 to M2 is only traversed 
+\begin_inset Formula $m-1$
+\end_inset
+
+ times because of the iteration in 
+\begin_inset Formula $j$
+\end_inset
+
+,
+ and the one from M5 to M4 is only traversed 
+\begin_inset Formula $n-1$
+\end_inset
+
+ times because of the iteration in 
+\begin_inset Formula $i$
+\end_inset
+
+,
+ proving that the algorithm terminates.
+\end_layout
+
+\begin_layout Standard
+We assert that,
+ by the beginning of M2 and by the end of M6,
+ 
+\begin_inset Formula $(w_{j+m-1}\dots w_{0})=u\cdot(v_{j-1}\dots v_{0})$
+\end_inset
+
+.
+ In the arrow from M1 to M2,
+ this is true because 
+\begin_inset Formula $j=0$
+\end_inset
+
+ and 
+\begin_inset Formula $(w_{m-1}\dots w_{0})=0=u\cdot0$
+\end_inset
+
+,
+ and now we have to see that this 
+\begin_inset Quotes eld
+\end_inset
+
+carries out
+\begin_inset Quotes erd
+\end_inset
+
+ by induction to the end of M6.
+\end_layout
+
+\begin_layout Standard
+For this,
+ we assert that,
+ by the beginning of M4 and the end of M5,
+ 
+\begin_inset Formula $(w_{j+m-1}\dots w_{0})+kb^{i+j}=u\cdot(v_{j-1}\dots v_{0})+(u_{i-1}\dots u_{0})\cdot v_{j}$
+\end_inset
+
+.
+ In the arrow from M3 to M4,
+ this is true because of the previous induction hypothesis and the fact that 
+\begin_inset Formula $i,k=0$
+\end_inset
+
+.
+ Then,
+ M4 modifies 
+\begin_inset Formula $w_{i+j}$
+\end_inset
+
+ and 
+\begin_inset Formula $k$
+\end_inset
+
+ so that 
+\begin_inset Formula $w'_{i+j}+k'b=w_{i+j}+k+u_{i}v_{j}$
+\end_inset
+
+,
+ where 
+\begin_inset Formula $w'_{i+j}$
+\end_inset
+
+ and 
+\begin_inset Formula $k'$
+\end_inset
+
+ are the new values of these two variables;
+ this means that
+\begin_inset Formula 
+\begin{multline*}
+(w'_{j+m-1}\dots w'_{0})+k'b^{i+j+1}=u\cdot(v_{j-1}\dots v_{1}v_{0})+(u_{i-1}\dots u_{0})\cdot v_{j}+u_{i}v_{j}b^{i+j}=\\
+=u\cdot(v_{j-1}\dots v_{1}v_{0})+(u_{i}\dots u_{0})v_{j},
+\end{multline*}
+
+\end_inset
+
+and the condition follows after M5 increases 
+\begin_inset Formula $i$
+\end_inset
+
+ by 1.
+\end_layout
+
+\begin_layout Standard
+When we go from M5 to 
+\begin_inset Formula $\text{M5}'$
+\end_inset
+
+,
+ 
+\begin_inset Formula $i=m$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $\text{M5}'$
+\end_inset
+
+ just sets
+\begin_inset Formula 
+\begin{multline*}
+(w_{j+m}\dots w_{0})=(w_{j+m-1}\dots w_{0})+kb^{m+j}=\\
+=u\cdot(v_{j-1}\dots v_{0})+(u_{m-1}\dots u_{0})\cdot v_{j}=u\cdot(v_{j}\dots v_{0}).
+\end{multline*}
+
+\end_inset
+
+If instead 
+\begin_inset Formula $v_{j}=0$
+\end_inset
+
+ and we go directly from step M2 to M6,
+ then 
+\begin_inset Formula $(v_{j}\dots v_{0})=(v_{j-1}\dots v_{0})$
+\end_inset
+
+ and 
+\begin_inset Formula $(w_{j+m}\dots w_{0})=(w_{j+m-1}\dots w_{0})$
+\end_inset
+
+ by the beginning of M6,
+ so the same condition holds and the optimization is valid.
+ After increasing 
+\begin_inset Formula $j$
+\end_inset
+
+,
+ we get the desired condition,
+ and when the program terminates,
+ 
+\begin_inset Formula $j=n$
+\end_inset
+
+ and 
+\begin_inset Formula $w=(w_{m+n-1}\dots w_{0})=u\cdot(v_{n-1}\dots v_{0})=uv$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc16[20]
+\end_layout
+
+\end_inset
+
+(
+\emph on
+Short division.
+\emph default
+) Design an algorithm that divides a nonnegative 
+\begin_inset Formula $n$
+\end_inset
+
+-place integer 
+\begin_inset Formula $(u_{n-1}\dots u_{1}u_{0})_{b}$
+\end_inset
+
+ by 
+\begin_inset Formula $v$
+\end_inset
+
+,
+ where 
+\begin_inset Formula $v$
+\end_inset
+
+ is a single-precision number (that is,
+ 
+\begin_inset Formula $0<v<b$
+\end_inset
+
+),
+ producing the quotient 
+\begin_inset Formula $(w_{n-1}\dots w_{1}w_{0})_{b}$
+\end_inset
+
+ and remainder 
+\begin_inset Formula $r$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+[Initialize.] Set 
+\begin_inset Formula $i=n-1$
+\end_inset
+
+ and 
+\begin_inset Formula $r\gets0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+[Divide.] Set 
+\begin_inset Formula $w_{i}\gets\lfloor(rb+u_{i})/v\rfloor$
+\end_inset
+
+ and 
+\begin_inset Formula $r\gets(rb+u_{i})\bmod v$
+\end_inset
+
+.
+ (We assume that we have this double-precision division available.
+ By induction,
+ we always have 
+\begin_inset Formula $rb+u_{i}<vb$
+\end_inset
+
+.)
+\end_layout
+
+\begin_layout Enumerate
+[Loop on 
+\begin_inset Formula $i$
+\end_inset
+
+.] If 
+\begin_inset Formula $i=0$
+\end_inset
+
+,
+ the algorithm terminates.
+ Otherwise set 
+\begin_inset Formula $i\gets i-1$
+\end_inset
+
+ and go to the previous step.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc19[M21]
+\end_layout
+
+\end_inset
+
+In the notation of Fig.
+ 6,
+ let 
+\begin_inset Formula $\hat{q}$
+\end_inset
+
+ be an approximation to 
+\begin_inset Formula $q$
+\end_inset
+
+,
+ and let 
+\begin_inset Formula $\hat{r}=u_{n}b+u_{n-1}-\hat{q}v_{n-1}$
+\end_inset
+
+.
+ Assume that 
+\begin_inset Formula $v_{n-1}>0$
+\end_inset
+
+.
+ Show that if 
+\begin_inset Formula $\hat{q}v_{n-2}>b\hat{r}+u_{n-2}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $q<\hat{q}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+We can rearrange terms to get 
+\begin_inset Formula $\hat{q}(v_{n-1}b+v_{n-2})\geq u_{n}b^{2}+u_{n-1}b+u_{n-2}+1$
+\end_inset
+
+.
+ Then,
+ following the proof of Theorem A,
+\begin_inset Formula 
+\begin{align*}
+u-\hat{q}v & \leq u-\hat{q}(v_{n-1}b+v_{n-2})b^{n-2}\\
+ & \leq u_{n}b^{n}+\dots+u_{0}-(u_{n}b^{n}+u_{n-1}b^{n-1}+u_{n-2}b^{n-2}+b^{n-2})\\
+ & =u_{n-3}+\dots+u_{0}-b^{n-2}<0,
+\end{align*}
+
+\end_inset
+
+so 
+\begin_inset Formula $u<\hat{q}v$
+\end_inset
+
+ and 
+\begin_inset Formula $\hat{q}>\frac{u}{v}\geq q$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc21[M23]
+\end_layout
+
+\end_inset
+
+Show that if 
+\begin_inset Formula $v_{n-1}\geq\lfloor b/2\rfloor$
+\end_inset
+
+,
+ and if 
+\begin_inset Formula $\hat{q}v_{n-2}\leq b\hat{r}+u_{n-2}$
+\end_inset
+
+ but 
+\begin_inset Formula $\hat{q}\neq q$
+\end_inset
+
+ in the notation of exercises 19 and 20,
+ then 
+\begin_inset Formula $u\bmod v\geq(1-2/b)v$
+\end_inset
+
+.
+ (The latter event occurs with approximate probability 
+\begin_inset Formula $2/b$
+\end_inset
+
+,
+ so that when 
+\begin_inset Formula $b$
+\end_inset
+
+ is the word size of a computer we must have 
+\begin_inset Formula $q_{j}=\hat{q}$
+\end_inset
+
+ in Algorithm D except in very rare circumstances.)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Rearranging terms,
+ 
+\begin_inset Formula $\hat{q}(v_{n-1}b+v_{n-2})\leq u_{n}b^{2}+u_{n-1}b+u_{n-2}$
+\end_inset
+
+.
+ By Exercise 20,
+ 
+\begin_inset Formula $q=\hat{q}-1$
+\end_inset
+
+,
+ so
+\begin_inset Formula 
+\begin{align*}
+u\bmod v-v & =u-qv-v=u-\hat{q}v\geq u-\hat{q}(v_{n-1}b+v_{n-2}+1)b^{n-2}\\
+ & \geq u-(u_{n}b^{2}+u_{n-1}b+u_{n-2})b^{n-2}-\hat{q}b^{n-2}\\
+ & \geq u_{n-3}b^{n-3}+\dots+u_{0}-b^{n-1}\geq b^{n-2}-b^{n-1}=(1-b)b^{n-2},
+\end{align*}
+
+\end_inset
+
+but
+\begin_inset Formula 
+\[
+\frac{2}{b}v\geq\frac{2}{b}\lfloor b/2\rfloor b^{n-1}\geq\frac{2}{b}\frac{b-1}{2}b^{n-1}=(b-1)b^{n-2},
+\]
+
+\end_inset
+
+so 
+\begin_inset Formula $u\bmod v-v\geq(1-b)b^{n-2}\geq-\frac{2}{b}v$
+\end_inset
+
+ and 
+\begin_inset Formula $u\bmod v\geq(1-2/b)v$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc22[24]
+\end_layout
+
+\end_inset
+
+Find an example of a four-digit number divided by a three-digit number for which step D6 is necessary in Algorithm D,
+ when the radix 
+\begin_inset Formula $b$
+\end_inset
+
+ is 10.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+We may take 
+\begin_inset Formula $u=8830$
+\end_inset
+
+ and 
+\begin_inset Formula $v=985$
+\end_inset
+
+.
+ After a first step where normalization changes 8830 to 08830 giving us 
+\begin_inset Formula $q_{1}=0$
+\end_inset
+
+,
+ we should have 
+\begin_inset Formula $q_{0}=\lfloor\frac{8830}{985}\rfloor=8$
+\end_inset
+
+,
+ but we get 
+\begin_inset Formula $\hat{q}=\lfloor\frac{88}{9}\rfloor=9$
+\end_inset
+
+ and 
+\begin_inset Formula $\hat{r}=7$
+\end_inset
+
+ and then 
+\begin_inset Formula $\hat{q}v_{n-2}=72\leq b\hat{r}+u_{j+n-2}=73$
+\end_inset
+
+,
+ so we don't subtract 1 from 
+\begin_inset Formula $\hat{q}$
+\end_inset
+
+ and instead we replace 
+\begin_inset Formula $u$
+\end_inset
+
+ with 
+\begin_inset Formula $u-9v=-35$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc30[22]
+\end_layout
+
+\end_inset
+
+If memory space is limited,
+ it may be desirable to use the same storage locations for both input and output during the performance of some of the algorithms in this section.
+ Is it possible to have 
+\begin_inset Formula $w_{0},w_{1},\dots,w_{n-1}$
+\end_inset
+
+ stored in the same respective locations as 
+\begin_inset Formula $u_{0},\dots,u_{n-1}$
+\end_inset
+
+ or 
+\begin_inset Formula $v_{0},\dots,v_{n-1}$
+\end_inset
+
+ during Algorithm A or S?
+ Is it possible to have the quotient 
+\begin_inset Formula $q_{0},\dots,q_{m}$
+\end_inset
+
+ occupy the same location as 
+\begin_inset Formula $u_{n},\dots,u_{m+n}$
+\end_inset
+
+ in Algorithm D?
+ Is there any permissible overlap of memory locations between input and output in Algorithm M?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+In Algorithms A and S,
+ this is clearly possible,
+ since we don't read 
+\begin_inset Formula $u_{j}$
+\end_inset
+
+ after writing 
+\begin_inset Formula $w_{j}$
+\end_inset
+
+ (actually,
+ this is only true if we change the order of evaluation of 
+\begin_inset Formula $k$
+\end_inset
+
+ and 
+\begin_inset Formula $w_{j}$
+\end_inset
+
+ in step 2 or if we compute 
+\begin_inset Formula $u_{j}+v_{j}+k$
+\end_inset
+
+ first and then store 
+\begin_inset Formula $w_{j}$
+\end_inset
+
+ and 
+\begin_inset Formula $k$
+\end_inset
+
+ from there).
+ In Algorithm Q,
+ the proposed option is possible as well,
+ because 
+\begin_inset Formula $q_{j}$
+\end_inset
+
+ is stored only written to after the last read from 
+\begin_inset Formula $u_{j+n}$
+\end_inset
+
+,
+ but only if we don't store 
+\begin_inset Formula $u_{j+n}$
+\end_inset
+
+ in step D6 (this doesn't change anything since 
+\begin_inset Formula $u_{j+n}$
+\end_inset
+
+ isn't read afterwards).
+ In Algorithm M,
+ it is possible to overlap 
+\begin_inset Formula $w_{m},\dots,w_{m+n-1}$
+\end_inset
+
+ to 
+\begin_inset Formula $v_{0},\dots,v_{n-1}$
+\end_inset
+
+,
+ since the first write to 
+\begin_inset Formula $w_{j+m}$
+\end_inset
+
+ happens after the last read of 
+\begin_inset Formula $v_{j}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc37[20]
+\end_layout
+
+\end_inset
+
+(E.
+ Salamin.) Explain how to avoid the normalization and unnormalization steps of Algorithm D,
+ when 
+\begin_inset Formula $d$
+\end_inset
+
+ is a power of 2 on a binary computer,
+ without changing the sequence of trial quotient digits computed by that algorithm.
+ (How can 
+\begin_inset Formula $\hat{q}$
+\end_inset
+
+ be computed in step D3 if the normalization of step D1 hasn't been done?)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+If 
+\begin_inset Formula $d\eqqcolon2^{q}$
+\end_inset
+
+,
+ instead of just reading 
+\begin_inset Formula $u_{j+n}$
+\end_inset
+
+ and 
+\begin_inset Formula $u_{j+n-1}$
+\end_inset
+
+,
+ we would have to read 
+\begin_inset Formula $u_{j+n-2}$
+\end_inset
+
+ and shift everything,
+ and similarly for 
+\begin_inset Formula $v_{n-1}$
+\end_inset
+
+.
+ Then we would have to apply a similar logic for the subsequent test.
+ We would still have to set 
+\begin_inset Formula $u_{m+n}\gets0$
+\end_inset
+
+ since we cannot assume that 
+\begin_inset Formula $u<b^{m}v$
+\end_inset
+
+.
+ 
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc43[22]
+\end_layout
+
+\end_inset
+
+Shades of gray or components of color values in digitized images are usually represented as 8-bit numbers 
+\begin_inset Formula $u$
+\end_inset
+
+ in the range 
+\begin_inset Formula $[0..255]$
+\end_inset
+
+,
+ denoting the fraction 
+\begin_inset Formula $u/255$
+\end_inset
+
+.
+ Given two such fractions 
+\begin_inset Formula $u/255$
+\end_inset
+
+ and 
+\begin_inset Formula $v/255$
+\end_inset
+
+,
+ graphical algorithms often need to compute their approximate product 
+\begin_inset Formula $w/255$
+\end_inset
+
+,
+ where 
+\begin_inset Formula $w$
+\end_inset
+
+ is the nearest integer to 
+\begin_inset Formula $uv/255$
+\end_inset
+
+.
+ Prove that 
+\begin_inset Formula $w$
+\end_inset
+
+ can be obtained from the efficient formula
+\begin_inset Formula 
+\begin{align*}
+t & =uv+128, & w & =\lfloor(\lfloor t/256\rfloor+t)/256\rfloor.
+\end{align*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+
+\begin_inset Note Greyedout
+status open
+
+\begin_layout Plain Layout
+(I had to look up the solution.)
+\end_layout
+
+\end_inset
+
+Because 
+\begin_inset Formula $t$
+\end_inset
+
+ is an integer,
+ it's easy to see that
+\begin_inset Formula 
+\[
+w=\left\lfloor \frac{\frac{t}{256}+t}{256}\right\rfloor =\left\lfloor \frac{257t}{256^{2}}\right\rfloor =\left\lfloor \frac{257(uv+128)}{256^{2}}\right\rfloor .
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Let 
+\begin_inset Formula $q\coloneqq\lfloor uv/255\rfloor$
+\end_inset
+
+ and 
+\begin_inset Formula $r\coloneqq uv\bmod255$
+\end_inset
+
+,
+ then 
+\begin_inset Formula 
+\[
+w=\left\lfloor \frac{257(255q+r+128)}{256^{2}}\right\rfloor =\left\lfloor \frac{256^{2}-1}{256^{2}}\left(q+\frac{r+128}{255}\right)\right\rfloor .
+\]
+
+\end_inset
+
+Furthermore,
+\begin_inset Formula 
+\[
+\frac{256^{2}-1}{256^{2}}(q+1)=(q+1)-\frac{1}{256^{2}}(q+1)\leq(q+1)-\frac{1}{256},
+\]
+
+\end_inset
+
+so if 
+\begin_inset Formula $r\geq128$
+\end_inset
+
+,
+\begin_inset Formula 
+\[
+q+1\leq\left\lfloor \frac{256^{2}-1}{256^{2}}\left(q+1+\frac{1}{255}\right)\right\rfloor \leq w\leq\left\lfloor \frac{(256^{2}-1)}{256^{2}}(q+2)\right\rfloor <q+2,
+\]
+
+\end_inset
+
+and similarly,
+ if 
+\begin_inset Formula $r<128$
+\end_inset
+
+,
+\begin_inset Formula 
+\[
+q\leq\left\lfloor \frac{256^{2}-1}{256^{2}}\left(q+\frac{1}{2}\right)\right\rfloor \leq w\leq\left\lfloor \frac{256^{2}-1}{256^{2}}(q+1)\right\rfloor <q+1.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document