Changed layout for more manageable volumes

1 files changed, 0 insertions, 834 deletions

diff --git a/3.2.2.lyx b/3.2.2.lyx
deleted file mode 100644
index 173f721..0000000
--- a/3.2.2.lyx
+++ /dev/null
@@ -1,834 +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
-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