1 files changed, 834 insertions, 0 deletions
diff --git a/vol2/3.2.2.lyx b/vol2/3.2.2.lyx
new file mode 100644
index 0000000..173f721
--- /dev/null
+++ b/vol2/3.2.2.lyx
@@ -0,0 +1,834 @@
+#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
+rexerc1[12]
+\end_layout
+
+\end_inset
+
+In practice,
+ we form random numbers using 
+\begin_inset Formula $X_{n+1}=(aX_{n}+c)\bmod m$
+\end_inset
+
+,
+ where the 
+\begin_inset Formula $X$
+\end_inset
+
+'s are 
+\emph on
+integers
+\emph default
+,
+ afterwards treating them as the 
+\emph on
+fractions
+\emph default
+ 
+\begin_inset Formula $U_{n}=X_{n}/m$
+\end_inset
+
+.
+ The recurrence relation for 
+\begin_inset Formula $U_{n}$
+\end_inset
+
+ is actually
+\begin_inset Formula 
+\[
+U_{n+1}=(aU_{n}+c/m)\bmod1.
+\]
+
+\end_inset
+
+Discuss the generation of random sequences using this relation 
+\emph on
+directly
+\emph default
+,
+ by making use of floating point arithmetic on the computer.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Despite the appeal of the idea for simplicity,
+ there is the problem of precision,
+ as the computer needs to be able to represent numbers as high as 
+\begin_inset Formula $a$
+\end_inset
+
+ (almost) with a precision of 
+\begin_inset Formula $1/m$
+\end_inset
+
+;
+ otherwise some numbers would be truncated and the period would be smaller than expected.
+ Also,
+ there might be issues due to rounding if 
+\begin_inset Formula $m$
+\end_inset
+
+ is not a divisor of a power of the computer's base (i.e.
+ 2,
+ or in some old computers 10),
+ but if it is,
+ then it's just faster to use integer arithmetic.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc2[M20]
+\end_layout
+
+\end_inset
+
+A good source of random numbers will have 
+\begin_inset Formula $X_{n-1}<X_{n+1}<X_{n}$
+\end_inset
+
+ about one-sixth of the time,
+ since each of the six possible relative orders of 
+\begin_inset Formula $X_{n-1}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $X_{n}$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $X_{n+1}$
+\end_inset
+
+ should be equally probable.
+ However,
+ show that the ordering above 
+\emph on
+never
+\emph default
+ occurs if the Fibonacci sequence (5) is used.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+If 
+\begin_inset Formula $X_{n+1}<X_{n}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $X_{n-1}=(X_{n+1}-X_{n})\bmod m=X_{n+1}-X_{n}+m>X_{n+1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc4[00]
+\end_layout
+
+\end_inset
+
+Why is the most significant byte used in the first line of program (14),
+ instead of some other byte?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+It follows Algorithm B,
+ and it's the byte that's the most random.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc5[20]
+\end_layout
+
+\end_inset
+
+Discuss using 
+\begin_inset Formula $X_{n}=Y_{n}$
+\end_inset
+
+ in Algorithm M,
+ in order to improve the speed of generation.
+ Is the result analogous to Algorithm B?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+This would use the next element in the sequence to choose which of the previous elements to use.
+ By the discussion about Exercise 15,
+ the period of the sequence would be the same as the original one,
+ and the resulting might actually be less random.
+ This is different than Algorithm B where the element used to choose is the one that was chosen from the table in the previous iteration,
+ so the index 
+\begin_inset Formula $j$
+\end_inset
+
+ itself is shuffled.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc6[10]
+\end_layout
+
+\end_inset
+
+In the binary method (10),
+ the text states that the low-order bit of 
+\family typewriter
+X
+\family default
+ is random,
+ if the code is performed repeatedly.
+ Why isn't the entire 
+\emph on
+word
+\emph default
+ 
+\family typewriter
+X
+\family default
+ random?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Because there is a high correlation between one element and the next:
+ if the higher order bit is 0,
+ the next word is simply twice the previous one.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc9[M24]
+\end_layout
+
+\end_inset
+
+(R.
+ R.
+ Coveyou.) Use the result of exercise 8 to prove that the modified middle-square method (4) has a period of length 
+\begin_inset Formula $2^{e-2}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+After several trials of the middle-square method,
+ we hypothesize that,
+ when 
+\begin_inset Formula $e\geq2$
+\end_inset
+
+,
+ 
+\begin_inset Formula $X_{n}=4Y_{n}+2$
+\end_inset
+
+ for each 
+\begin_inset Formula $n\geq0$
+\end_inset
+
+,
+ where 
+\begin_inset Formula $(Y_{n})_{n}$
+\end_inset
+
+ is the quadratic congruential sequence given by
+\begin_inset Formula 
+\begin{align*}
+X_{0} & =4Y_{0}+2, & Y_{n+1} & =(4Y_{n}+1)(Y_{n}+1)\bmod2^{e-2}.
+\end{align*}
+
+\end_inset
+
+This sequence has 
+\begin_inset Formula $d=4$
+\end_inset
+
+,
+ 
+\begin_inset Formula $a=5$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $c=1$
+\end_inset
+
+,
+ so it meets the conditions from exercise 8 and therefore has period 
+\begin_inset Formula $2^{e-2}$
+\end_inset
+
+.
+ We can prove this identity by induction,
+ as if 
+\begin_inset Formula $X_{n}=4Y_{n}+2$
+\end_inset
+
+,
+ then
+\begin_inset Formula 
+\begin{multline*}
+X_{n+1}=X_{n}(X_{n}+1)\bmod2^{e}=(4Y_{n}+2)(4Y_{n}+3)\bmod2^{e}=\\
+=16Y_{n}^{2}+20Y_{n}+6\bmod2^{e}=4(4Y_{n}+1)(Y_{n}+1)+2\bmod2^{e}=4Y_{n+1}+2.
+\end{multline*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc22[M24]
+\end_layout
+
+\end_inset
+
+The text restricts discussion of the extended linear sequences (8) to the case that 
+\begin_inset Formula $m$
+\end_inset
+
+ is prime.
+ Prove that reasonably long periods can also be obtained when 
+\begin_inset Formula $m$
+\end_inset
+
+ is 
+\begin_inset Quotes eld
+\end_inset
+
+squarefree,
+\begin_inset Quotes erd
+\end_inset
+
+ that is,
+ the product of distinct primes.
+ (Examinations of Table 3.2.1.1–1 shows that 
+\begin_inset Formula $m=w\pm1$
+\end_inset
+
+ often satisfies this hypothesis;
+ many of the results of the text can therefore be carried over to that case,
+ which is somewhat more convenient for calculation.)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+If 
+\begin_inset Formula $m=p_{1}\cdots p_{t}$
+\end_inset
+
+ where the 
+\begin_inset Formula $p_{k}$
+\end_inset
+
+ are distinct primes,
+ then integers 
+\begin_inset Formula $a\in\{0,\dots,m-1\}$
+\end_inset
+
+ can be associated with the tuples 
+\begin_inset Formula $(a\bmod p_{1},\dots,a\bmod p_{t})$
+\end_inset
+
+ because of the Chinese remainder theorem.
+ Furthermore,
+ equation (8) respects this association,
+ in the sense that 
+\begin_inset Formula $X_{n}\bmod p_{i}=((a_{1}\bmod p_{i})(X_{n-1}\bmod p_{i})+\dots+(a_{k}\bmod p_{i})(X_{n-k}\bmod p_{i}))\bmod p_{i}$
+\end_inset
+
+ and therefore we could as well calculate the sequence using these 
+\begin_inset Quotes eld
+\end_inset
+
+coordinates
+\begin_inset Quotes erd
+\end_inset
+
+.
+ We also know that the 
+\begin_inset Formula $a_{j}\bmod p_{i}$
+\end_inset
+
+ can be chosen to make 
+\begin_inset Formula $(X_{n}\bmod p_{i})_{n}$
+\end_inset
+
+ have period 
+\begin_inset Formula $p_{i}^{k}-1$
+\end_inset
+
+,
+ so the 
+\begin_inset Formula $a_{j}$
+\end_inset
+
+ can be chosen to make 
+\begin_inset Formula $(X_{n})_{n}$
+\end_inset
+
+ have period 
+\begin_inset Formula $\text{lcm}\{p_{1}^{k}-1,\dots,p_{t}^{k}-1\}$
+\end_inset
+
+,
+ which we deem reasonably long.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc23[20]
+\end_layout
+
+\end_inset
+
+Discuss the sequence defined by 
+\begin_inset Formula $X_{n}=(X_{n-55}-X_{n-24})\bmod m$
+\end_inset
+
+ as an alternative to (7).
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+The period is still at least 
+\begin_inset Formula $2^{55}-1$
+\end_inset
+
+,
+ since the sequence defined by the lowest bit in (7) has this period and the one defined by the lowest bit in this formula is exactly the same.
+ We don't know if exercise 30 still applies as we haven't done it.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{samepage}
+\end_layout
+
+\end_inset
+
+
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc33[M23]
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+Let 
+\begin_inset Formula $g_{n}(z)=X_{n+30}+X_{n+29}z+\dots+X_{n}z^{30}+X_{n+54}z^{31}+\dots+X_{n+31}z^{54}$
+\end_inset
+
+,
+ where the 
+\begin_inset Formula $X$
+\end_inset
+
+'s satisfy the lagged Fibonacci recurrence (7).
+ Find a simple relation between 
+\begin_inset Formula $g_{n}(z)$
+\end_inset
+
+ and 
+\begin_inset Formula $g_{n+t}(z)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Express 
+\begin_inset Formula $X_{500}$
+\end_inset
+
+ in terms of 
+\begin_inset Formula $X_{0},\dots,X_{54}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{samepage}
+\end_layout
+
+\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 obviously had to look at the answers.)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula 
+\begin{align*}
+g_{n+1}(z) & =X_{n+31}+X_{n+30}z+\dots+X_{n+1}z^{30}+X_{n+55}z^{31}+\dots+X_{n+32}z^{54}\\
+ & =zg_{n}(z)+X_{n+31}-X_{n}z^{31}+X_{n+55}z^{31}-X_{n+31}z^{55}\\
+ & =zg_{n}(z)+X_{n+31}(z^{31}-z^{55}+1)+km,
+\end{align*}
+
+\end_inset
+
+for some small integer 
+\begin_inset Formula $k$
+\end_inset
+
+.
+ If we see the 
+\begin_inset Formula $g_{n}$
+\end_inset
+
+ as polynomials on 
+\begin_inset Formula $z$
+\end_inset
+
+,
+ in the domain 
+\begin_inset Formula $\mathbb{Z}[X]$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $g_{n+t}(z)\equiv z^{t}g_{n}(z)$
+\end_inset
+
+ in 
+\begin_inset Formula $A\coloneqq\mathbb{Z}[X]/(m\mathbb{Z}[X]+(z^{55}-z^{31}-1)\mathbb{Z}[X])\cong\mathbb{Z}_{m}[X]/(z^{55}-z^{31}-1)\mathbb{Z}_{m}[X]$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+We prove by strong induction that,
+ if 
+\begin_inset Formula $a_{0}+\dots+a_{54}z^{54}=z^{k}\bmod(z^{55}-z^{31}-1)$
+\end_inset
+
+ in 
+\begin_inset Formula $\mathbb{Z}_{m}[X]$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $X_{k}=a_{0}X_{0}+\dots+a_{54}X^{54}\bmod m$
+\end_inset
+
+.
+ If 
+\begin_inset Formula $k<55$
+\end_inset
+
+,
+ this is obvious;
+ otherwise 
+\begin_inset Formula $X_{k}=X_{k-55}+X_{k-24}$
+\end_inset
+
+ and 
+\begin_inset Formula $z^{k}\bmod(z^{55}-z^{31}-1)=(z^{k-55}+z^{k-24})\bmod(z^{55}-z^{31}-1)$
+\end_inset
+
+ by the division algorithm.
+ With this,
+ we run 
+\family typewriter
+divide(z^500,
+ z^55-z^31-1,
+ z)
+\family default
+ in Maxima and we get that 
+\begin_inset Formula $X_{500}=120X_{54}+462X_{50}+455X_{57}+X_{44}+120X_{43}+1001X_{40}+18X_{37}+9X_{36}+1287X_{33}+16X_{30}+462X_{26}+105X_{23}+210X_{19}+364X_{16}+X_{13}+36X_{12}+715X_{9}+17X_{6}+X_{5}+792X_{2}\bmod m$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document