1 files changed, 719 insertions, 0 deletions
diff --git a/vol2/3.2.1.1.lyx b/vol2/3.2.1.1.lyx
new file mode 100644
index 0000000..7eec653
--- /dev/null
+++ b/vol2/3.2.1.1.lyx
@@ -0,0 +1,719 @@
+#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 ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc3[M25]
+\end_layout
+
+\end_inset
+
+Many computers do not provide the ability to divide a two-word number by a one-word number;
+ they provide only operations on single-word numbers,
+ such as 
+\begin_inset Formula $\text{himult}(x,y)=\lfloor xy/w\rfloor$
+\end_inset
+
+ and 
+\begin_inset Formula $\text{lomult}(x,y)=xy\bmod w$
+\end_inset
+
+,
+ when 
+\begin_inset Formula $x$
+\end_inset
+
+ and 
+\begin_inset Formula $y$
+\end_inset
+
+ are nonnegative integers less than the word size 
+\begin_inset Formula $w$
+\end_inset
+
+.
+ Explain how to evaluate 
+\begin_inset Formula $ax\bmod m$
+\end_inset
+
+ in terms of 
+\begin_inset Formula $\text{himult}$
+\end_inset
+
+ and 
+\begin_inset Formula $\text{lomult}$
+\end_inset
+
+,
+ assuming that 
+\begin_inset Formula $0\leq a,x<m<w$
+\end_inset
+
+ and that 
+\begin_inset Formula $m\bot w$
+\end_inset
+
+.
+ You may use precomputed constants that depend on 
+\begin_inset Formula $a$
+\end_inset
+
+,
+ 
+\begin_inset Formula $m$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $w$
+\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 answer,
+ I would have never guessed it.)
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $b\coloneqq aw\bmod m$
+\end_inset
+
+ and 
+\begin_inset Formula $c\in\{0,\dots,w-1\}$
+\end_inset
+
+ such that 
+\begin_inset Formula $mc\equiv1\pmod w$
+\end_inset
+
+,
+ we compute 
+\begin_inset Formula $y\gets\text{lomult}(b,x)$
+\end_inset
+
+,
+ 
+\begin_inset Formula $z\gets\text{himult}(b,x)$
+\end_inset
+
+,
+ 
+\begin_inset Formula $t\gets\text{lomult}(c,y)$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $u\gets\text{himult}(m,t)$
+\end_inset
+
+,
+ and return 
+\begin_inset Formula $z-u+[z<u]m$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+To see that this works,
+ we note that 
+\begin_inset Formula 
+\[
+mt=m(cbx\bmod w)\equiv mcbx\equiv bx\pmod w,
+\]
+
+\end_inset
+
+so
+\begin_inset Formula 
+\[
+bx-mt=\left(\left\lfloor \frac{bx}{w}\right\rfloor -\left\lfloor \frac{mt}{w}\right\rfloor \right)w=(z-u)w
+\]
+
+\end_inset
+
+and,
+ taking modulo 
+\begin_inset Formula $m$
+\end_inset
+
+ on both sides,
+ 
+\begin_inset Formula $awx\bmod m=(z-u)w\bmod m$
+\end_inset
+
+ and 
+\begin_inset Formula $ax\bmod m=(z-u)\bmod m$
+\end_inset
+
+ by canceling 
+\begin_inset Formula $w$
+\end_inset
+
+.
+ Finally,
+ 
+\begin_inset Formula $0\leq z=\lfloor\frac{(aw\bmod m)x}{w}\rfloor\leq\lfloor\frac{mx}{w}\rfloor<m$
+\end_inset
+
+ and 
+\begin_inset Formula $0\leq u=\lfloor\frac{m(cy\bmod w)}{w}\rfloor<m$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $-m<z-u<m$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc4[21]
+\end_layout
+
+\end_inset
+
+Discuss the calculation of linear congruential sequences with 
+\begin_inset Formula $m=2^{32}$
+\end_inset
+
+ on two's-complement machines such as the System/370 series.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+When multiplying 
+\begin_inset Formula $a$
+\end_inset
+
+ times 
+\begin_inset Formula $x$
+\end_inset
+
+,
+ one or two of them could instead be 
+\begin_inset Formula $a-m$
+\end_inset
+
+ or 
+\begin_inset Formula $x-m$
+\end_inset
+
+;
+ however,
+ for 
+\begin_inset Formula $i,j\in\{0,1\}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $(a-im)(x-jm)\equiv am\pmod m$
+\end_inset
+
+,
+ so no further action is necessary given that taking modulo 
+\begin_inset Formula $m=2^{32}$
+\end_inset
+
+ is trivial.
+ Of course,
+ the resulting number could be negative,
+ but the bit pattern would be the same.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc6[20]
+\end_layout
+
+\end_inset
+
+The previous exercise suggests that subtraction mod 
+\begin_inset Formula $m$
+\end_inset
+
+ is easier to perform than addition mod 
+\begin_inset Formula $m$
+\end_inset
+
+.
+ Discuss sequences generated by the rule
+\begin_inset Formula 
+\[
+X_{n+1}=(aX_{n}-c)\bmod m.
+\]
+
+\end_inset
+
+Are these sequences essentially different from linear congruential sequences as defined in the text?
+ Are they more suited to efficient computer calculation?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+These are the same,
+ as subtracting 
+\begin_inset Formula $c$
+\end_inset
+
+ is the same modulo 
+\begin_inset Formula $m$
+\end_inset
+
+ as adding 
+\begin_inset Formula $m-c$
+\end_inset
+
+.
+ Although they are equivalent,
+ computing them this way could be slightly more efficient.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc8[20]
+\end_layout
+
+\end_inset
+
+Write a 
+\family typewriter
+MIX
+\family default
+ program analogous to (2) that computes 
+\begin_inset Formula $(aX)\bmod(w-1)$
+\end_inset
+
+.
+ The values 0 and 
+\begin_inset Formula $w-1$
+\end_inset
+
+ are to be treated as equivalent in the input and output of your program.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $c\coloneqq\text{himult}(a,X)$
+\end_inset
+
+ and 
+\begin_inset Formula $d\coloneqq\text{lomult}(a,X)$
+\end_inset
+
+,
+ then
+\begin_inset Formula 
+\[
+aX=cw+d\equiv(cw+d)-c(w-1)=c+d\pmod m,
+\]
+
+\end_inset
+
+so assuming the overflow bit was off,
+ we could write:
+\begin_inset listings
+inline false
+status open
+
+\begin_layout Plain Layout
+
+LDA  X
+\end_layout
+
+\begin_layout Plain Layout
+
+MUL  A
+\end_layout
+
+\begin_layout Plain Layout
+
+STX  TEMP
+\end_layout
+
+\begin_layout Plain Layout
+
+ADD  TEMP
+\end_layout
+
+\begin_layout Plain Layout
+
+JNOV *+2
+\end_layout
+
+\begin_layout Plain Layout
+
+INCA 1
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+The last instruction is valid because the value of 
+\begin_inset Formula $c+d$
+\end_inset
+
+ can never reach 
+\begin_inset Formula $2w-1$
+\end_inset
+
+,
+ so 
+\family typewriter
+INCA
+\family default
+ cannot produce a second overflow.
+ However 
+\begin_inset Formula $c+d$
+\end_inset
+
+ could be 
+\begin_inset Formula $w-1$
+\end_inset
+
+ or 0 and no effort is made to make rA be equal in these two cases.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc9[M25]
+\end_layout
+
+\end_inset
+
+Most high-level programming languages do not provide a good way to divide a two-word integer by a one-word integer,
+ nor do they provide the 
+\begin_inset Formula $\text{himult}$
+\end_inset
+
+ operation of exercise 3.
+ The purpose of this exercise is to find a reasonable way to cope with such limitations when we wish to evaluate 
+\begin_inset Formula $ax\bmod m$
+\end_inset
+
+ for variable 
+\begin_inset Formula $x$
+\end_inset
+
+ and for constants 
+\begin_inset Formula $0<a<m$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Prove that if 
+\begin_inset Formula $q=\lfloor m/a\rfloor$
+\end_inset
+
+,
+ we have 
+\begin_inset Formula $a(x-(x\bmod q))=\lfloor x/q\rfloor(m-(m\bmod a))$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Use the identity of part 1 to evaluate 
+\begin_inset Formula $ax\bmod m$
+\end_inset
+
+ without computing any numbers that exceed 
+\begin_inset Formula $m$
+\end_inset
+
+ in absolute value,
+ assuming that 
+\begin_inset Formula $a^{2}\leq m$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+First I challenge the idea that most high-level languages do not provide these features.
+ While this might have been true when the book was written,
+ it's not true today with languages like Python,
+ Ruby,
+ or JavaScript dominating the industry,
+ you can do that but it's slow.
+ (I guess the the text said 
+\begin_inset Quotes eld
+\end_inset
+
+most
+\begin_inset Quotes erd
+\end_inset
+
+ was about the Lisp family of languages.) Anyway,
+ a lot of them like Go are still stuck in the 70s so...
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $a(x-(x\bmod q))=a\lfloor\frac{x}{q}\rfloor q=\lfloor\frac{x}{q}\rfloor a\lfloor\frac{m}{a}\rfloor=\lfloor\frac{x}{q}\rfloor(m-(m\bmod a))$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+If we operate modulo 
+\begin_inset Formula $m$
+\end_inset
+
+,
+\begin_inset Formula 
+\[
+ax=a(x\bmod q)+\left\lfloor \frac{x}{q}\right\rfloor (m-(m\bmod a))\equiv a(x\bmod q)-\left\lfloor \frac{x}{q}\right\rfloor (m\bmod a)\mod m,
+\]
+
+\end_inset
+
+so 
+\begin_inset Formula $ax\bmod m=\left(a(x\bmod q)-\lfloor\frac{x}{q}\rfloor(m\bmod a)\right)\bmod m$
+\end_inset
+
+.
+ Since 
+\begin_inset Formula $a^{2}\leq m$
+\end_inset
+
+,
+ 
+\begin_inset Formula $a\leq\frac{m}{a}$
+\end_inset
+
+ and therefore 
+\begin_inset Formula $a\leq q$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $\lfloor\frac{x}{q}\rfloor\leq\lfloor\frac{x}{a}\rfloor\leq\frac{x}{a}$
+\end_inset
+
+ and,
+ multiplied by 
+\begin_inset Formula $m\bmod a$
+\end_inset
+
+ (a constant),
+ the product is no greater than 
+\begin_inset Formula $x$
+\end_inset
+
+.
+ In the first factor,
+ however,
+ 
+\begin_inset Formula $x\bmod q\leq q\leq\frac{m}{a}$
+\end_inset
+
+,
+ so again the product by 
+\begin_inset Formula $a$
+\end_inset
+
+ is no greater than 
+\begin_inset Formula $m$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document