#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