#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 $uv$ \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}] (-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 $00$ \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