#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}$ \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