From 4f670b750af5c11e1eac16d9cd8556455f89f46a Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan@mnpi.eu>
Date: Fri, 16 May 2025 22:18:44 +0200
Subject: Changed layout for more manageable volumes

---
 3.2.1.1.lyx | 719 ------------------------------------------------------------
 1 file changed, 719 deletions(-)
 delete mode 100644 3.2.1.1.lyx

(limited to '3.2.1.1.lyx')

diff --git a/3.2.1.1.lyx b/3.2.1.1.lyx
deleted file mode 100644
index 7eec653..0000000
--- a/3.2.1.1.lyx
+++ /dev/null
@@ -1,719 +0,0 @@
-#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
-- 
cgit v1.2.3