diff options
Diffstat (limited to 'vol2/4.3.1.lyx')
| -rw-r--r-- | vol2/4.3.1.lyx | 1608 |
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 |