From 4f670b750af5c11e1eac16d9cd8556455f89f46a Mon Sep 17 00:00:00 2001 From: Juan Marín Noguera Date: Fri, 16 May 2025 22:18:44 +0200 Subject: Changed layout for more manageable volumes --- vol2/3.1.lyx | 1204 ++++++++++++++++++++++++++++++++++ vol2/3.2.1.1.lyx | 719 ++++++++++++++++++++ vol2/3.2.1.2.lyx | 1542 +++++++++++++++++++++++++++++++++++++++++++ vol2/3.2.1.3.lyx | 273 ++++++++ vol2/3.2.1.lyx | 320 +++++++++ vol2/3.2.2.lyx | 834 +++++++++++++++++++++++ vol2/3.3.1.lyx | 607 +++++++++++++++++ vol2/3.3.2.lyx | 1009 ++++++++++++++++++++++++++++ vol2/3.3.3.lyx | 1383 +++++++++++++++++++++++++++++++++++++++ vol2/3.3.4.lyx | 781 ++++++++++++++++++++++ vol2/3.4.1.lyx | 1677 +++++++++++++++++++++++++++++++++++++++++++++++ vol2/3.4.2.lyx | 537 +++++++++++++++ vol2/3.5.lyx | 1191 +++++++++++++++++++++++++++++++++ vol2/3.6.lyx | 496 ++++++++++++++ vol2/4.1.lyx | 1922 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ vol2/index.lyx | 1394 +++++++++++++++++++++++++++++++++++++++ 16 files changed, 15889 insertions(+) create mode 100644 vol2/3.1.lyx create mode 100644 vol2/3.2.1.1.lyx create mode 100644 vol2/3.2.1.2.lyx create mode 100644 vol2/3.2.1.3.lyx create mode 100644 vol2/3.2.1.lyx create mode 100644 vol2/3.2.2.lyx create mode 100644 vol2/3.3.1.lyx create mode 100644 vol2/3.3.2.lyx create mode 100644 vol2/3.3.3.lyx create mode 100644 vol2/3.3.4.lyx create mode 100644 vol2/3.4.1.lyx create mode 100644 vol2/3.4.2.lyx create mode 100644 vol2/3.5.lyx create mode 100644 vol2/3.6.lyx create mode 100644 vol2/4.1.lyx create mode 100644 vol2/index.lyx (limited to 'vol2') diff --git a/vol2/3.1.lyx b/vol2/3.1.lyx new file mode 100644 index 0000000..81d7d26 --- /dev/null +++ b/vol2/3.1.lyx @@ -0,0 +1,1204 @@ +#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[20] +\end_layout + +\end_inset + +Suppose that you wish to obtain a decimal digit at random, + not using a computer. + Which of the following methods would be suitable? +\end_layout + +\begin_layout Enumerate +Open a telephone directory to a random place by sticking your finger in it somewhere, + and use the units digit of the first number found on the selected page. +\end_layout + +\begin_layout Enumerate +Same as (a), + but use the units digit of the +\emph on +page +\emph default + number. +\end_layout + +\begin_layout Enumerate +Roll a die that is in the shape of a regular icosahedron, + whose twenty faces have been labeled with the digits 0, + 0, + 1, + 1, + ..., + 9, + 9. + Use the digit that appears on the top, + when the die comes to rest. + (A felt-covered table with a hard surface is recommended for rolling dice.) +\end_layout + +\begin_layout Enumerate +Expose a geiger counter to a source of radioactivity for one minute (shielding yourself) and use the units digit of the resulting count. + Assume that the geiger counter displays the number of counts in decimal notation, + and that the count is initially zero. +\end_layout + +\begin_layout Enumerate +Glance at your wristwatch; + and if the position of the second-hand is between +\begin_inset Formula $6n$ +\end_inset + + and +\begin_inset Formula $6(n+1)$ +\end_inset + + seconds, + choose the digit +\begin_inset Formula $n$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Ask a friend to think of a random digit, + and use the digit he names. +\end_layout + +\begin_layout Enumerate +Ask an enemy to think of a random digit, + and use the digit he names. +\end_layout + +\begin_layout Enumerate +Assume that 10 horses are entered in a race and that you know nothing whatever about their qualifications. + Assign to these horses the digits 0 to 9, + in arbitrary fashion, + and after the race use the winner's digit. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Enumerate +This would work for a typical phone book. + It wouldn't work if the book has, + say, + entries ordered by number with a fixed number of entries per page that is a multiple of 2 or 5. + And, + according to the official solution, + in some places people can choose phone numbers (presumably in the US where Knuth lives) so it wouldn't work there as people would tend to choose round numbers. +\end_layout + +\begin_layout Enumerate +This would be suitable, + although some adjustment would have to be made to account for the fact that left pages would have even numbers and right pages would have round numbers (say, + we could take the even number and divide it by two) and to avoid the last few pages if the total number is not a multiple of 20. +\end_layout + +\begin_layout Enumerate +This would work very well. +\end_layout + +\begin_layout Enumerate +This would work well assuming there are several digits between the most significant one and the units. +\end_layout + +\begin_layout Enumerate +This would work assuming you only have to do it once at a time and not at a specific time. +\end_layout + +\begin_layout Enumerate +This wouldn't work, + as humans are not good at mentally generating random numbers. +\end_layout + +\begin_layout Enumerate +This definitely wouldn't work, + as the enemy would probably be compelled to choose the number strategically instead of randomly. +\end_layout + +\begin_layout Enumerate +This could work, + although it would be time consuming. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc3[10] +\end_layout + +\end_inset + +What number follows 1010101010 in the middle-square method? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + + +\begin_inset Formula $1010101010^{2}=1020304050403020100$ +\end_inset + +, + so the next number would be 3040504030. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc6[M21] +\end_layout + +\end_inset + +Suppose that we want to generate a sequence of integers +\begin_inset Formula $X_{0},X_{1},X_{2},\dots$ +\end_inset + +, + in the range +\begin_inset Formula $0\leq X_{n}0$ +\end_inset + + such that +\begin_inset Formula $X_{n}=X_{2n}$ +\end_inset + +; + and the smallest such value of +\begin_inset Formula $n$ +\end_inset + + lies in the range +\begin_inset Formula $\mu\le n\leq\mu+\lambda$ +\end_inset + +. + Furthermore the value of +\begin_inset Formula $X_{n}$ +\end_inset + + is unique in the sense that if +\begin_inset Formula $X_{n}=X_{2n}$ +\end_inset + + and +\begin_inset Formula $X_{r}=X_{2r}$ +\end_inset + +, + then +\begin_inset Formula $X_{r}=X_{n}$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Use the idea of part +\begin_inset CommandInset ref +LatexCommand ref +reference "enu:e316b" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + to design an algorithm that calculates +\begin_inset Formula $\mu$ +\end_inset + + and +\begin_inset Formula $\lambda$ +\end_inset + + for any given function +\begin_inset Formula $f$ +\end_inset + + and any given +\begin_inset Formula $X_{0}$ +\end_inset + +, + using only +\begin_inset Formula $O(\mu+\lambda)$ +\end_inset + + steps and only a bounded number of memory locations. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Assume +\begin_inset Formula $f:\mathbb{Z}_{m}\to\mathbb{Z}_{m}$ +\end_inset + +, + as otherwise the statements below are not necessarily true (e.g. + if +\begin_inset Formula $f:\mathbb{R}\to\mathbb{R}$ +\end_inset + +, + +\begin_inset Formula $f(x)\coloneqq\frac{x}{2}$ +\end_inset + +, + and +\begin_inset Formula $X_{0}=\frac{m}{2}$ +\end_inset + +). +\end_layout + +\begin_layout Enumerate +Require that +\begin_inset Formula $\mu\in\mathbb{N}$ +\end_inset + + and +\begin_inset Formula $\lambda\in\mathbb{N}^{*}$ +\end_inset + +, + as otherwise it is unclear what is meant and, + in particular, + the statement is obviously true when +\begin_inset Formula $\mu\in\mathbb{N}$ +\end_inset + + and +\begin_inset Formula $\lambda=0$ +\end_inset + +. + Now, + since +\begin_inset Formula $\{X_{0},\dots,X_{m}\}\subseteq\{0,\dots,m-1\}$ +\end_inset + +, + then +\begin_inset Formula $|\{X_{0},\dots,X_{m}\}|\leq m$ +\end_inset + + and there must be integers +\begin_inset Formula $i$ +\end_inset + + and +\begin_inset Formula $j$ +\end_inset + +, + +\begin_inset Formula $0\leq i0$ +\end_inset + + be such that +\begin_inset Formula $X_{r}=X_{2r}$ +\end_inset + +, + so necessarily +\begin_inset Formula $2r\geq\mu+\lambda$ +\end_inset + +. + We note that, + for any +\begin_inset Formula $s\geq\mu$ +\end_inset + +, + by induction, + +\begin_inset Formula $X_{s}=X_{s-\lfloor\frac{s-\mu}{\lambda}\rfloor\lambda}=X_{\mu+((s-\mu)\bmod\lambda)}$ +\end_inset + +, + and we call +\begin_inset Formula $R(s)\coloneqq\mu+((s-\mu)\bmod\lambda)\in\{\mu,\dots,\mu+\lambda-1\}$ +\end_inset + +. + With this, + +\begin_inset Formula $X_{R(2r)}=X_{2r}=X_{r}$ +\end_inset + +, + so either +\begin_inset Formula $r=R(2r)$ +\end_inset + + or +\begin_inset Formula $r\geq\mu+\lambda$ +\end_inset + +; + in any case +\begin_inset Formula $r\geq\mu$ +\end_inset + + and +\begin_inset Formula $X_{R(2r)}=X_{R(r)}$ +\end_inset + +. + This means +\begin_inset Formula $R(2r)=R(r)$ +\end_inset + +, + so +\begin_inset Formula $r\equiv0\mod{\lambda}$ +\end_inset + + and +\begin_inset Formula $R(r)=\mu+(-\mu\bmod\lambda)\equiv0\bmod\lambda$ +\end_inset + +, + so +\begin_inset Formula $R(r)$ +\end_inset + + is unique and +\begin_inset Formula $X_{r}=X_{R(r)}=X_{R(n)}=X_{n}$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +First we set +\begin_inset Formula $a,b\gets X_{0}$ +\end_inset + + and then repeatedly set +\begin_inset Formula $a\gets f(a)$ +\end_inset + + and +\begin_inset Formula $b\gets f^{2}(b)$ +\end_inset + + until +\begin_inset Formula $a=b$ +\end_inset + +; + the number of times we do this operation is +\begin_inset Formula $n$ +\end_inset + +, + and in the end +\begin_inset Formula $a=X_{n}$ +\end_inset + +. + Then we set +\begin_inset Formula $b\gets a$ +\end_inset + + and repeat +\begin_inset Formula $b\gets f(b)$ +\end_inset + + until +\begin_inset Formula $b=a$ +\end_inset + +; + the number of times we do this operation is +\begin_inset Formula $\lambda$ +\end_inset + +. + Finally, + since +\begin_inset Formula $a$ +\end_inset + + is a multiple of +\begin_inset Formula $\lambda$ +\end_inset + +, + +\begin_inset Formula $X_{\mu}=X_{\mu+n}$ +\end_inset + +, + so we set +\begin_inset Formula $b\gets X_{0}$ +\end_inset + + and repeat +\begin_inset Formula $b\gets f(b)$ +\end_inset + + and +\begin_inset Formula $a\gets f(a)$ +\end_inset + + until +\begin_inset Formula $a=b$ +\end_inset + +; + the number of times we do this operation is +\begin_inset Formula $\mu$ +\end_inset + +. + In total this uses two slots of memory and runs in time +\begin_inset Formula $O(n)+O(\lambda)+O(\mu)=O(\mu+\lambda)$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc7[M21] +\end_layout + +\end_inset + +(R. + P. + Brent, + 1977.) Let +\begin_inset Formula $\ell(n)$ +\end_inset + + be the greatest power of 2 that is less than or equal to +\begin_inset Formula $n$ +\end_inset + +; + thus, + for example, + +\begin_inset Formula $\ell(15)=8$ +\end_inset + + and +\begin_inset Formula $\ell(\ell(n))=\ell(n)$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Show that, + in terms of the notation in exercise 6, + there exists an +\begin_inset Formula $n>0$ +\end_inset + + such that +\begin_inset Formula $X_{n}=X_{\ell(n)-1}$ +\end_inset + +. + Find a formula that expresses the least such +\begin_inset Formula $n$ +\end_inset + + in terms of the periodicity numbers +\begin_inset Formula $\mu$ +\end_inset + + and +\begin_inset Formula $\lambda$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Apply this result to design an algorithm that can be used in conjunction with any random number generator of the type +\begin_inset Formula $X_{n+1}=f(X_{n})$ +\end_inset + +, + to prevent it from cycling indefinitely. + Your algorithm should calculate the period length +\begin_inset Formula $\lambda$ +\end_inset + +, + and it should only use a small amount of memory space— +you must not simply store all the computed sequence values! +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Enumerate +For sufficiently large +\begin_inset Formula $r$ +\end_inset + +, + +\begin_inset Formula $n\coloneqq2^{r}-1+\lambda<2^{r+1}$ +\end_inset + + and then +\begin_inset Formula $X_{\ell(n)-1}=X_{2^{r}-1}=X_{n}$ +\end_inset + +, + and it's easy to convince ourselves that all such +\begin_inset Formula $n$ +\end_inset + + are of the form +\begin_inset Formula $2^{r}-1+k\lambda$ +\end_inset + + with +\begin_inset Formula $r\in\mathbb{N}$ +\end_inset + +, + +\begin_inset Formula $k\in\mathbb{N}^{*}$ +\end_inset + +, + +\begin_inset Formula $k\lambda-1<2^{r}$ +\end_inset + +, + and +\begin_inset Formula $2^{r}-1\geq\mu$ +\end_inset + +. + The minimum value, + then, + happens with +\begin_inset Formula $k=1$ +\end_inset + + and +\begin_inset Formula $2^{r}$ +\end_inset + + is the minimum such that +\begin_inset Formula $\lambda,\mu+1\leq2^{r}$ +\end_inset + +, + so if +\begin_inset Formula $u(n)$ +\end_inset + + is the lowest power of 2 that is greater than or equal to +\begin_inset Formula $n$ +\end_inset + +, + then +\begin_inset Formula +\[ +n=u(\max\{\lambda,\mu+1\})+\lambda-1. +\] + +\end_inset + + +\end_layout + +\begin_layout Enumerate +We set +\begin_inset Formula $a\gets b\gets X_{0}$ +\end_inset + + and +\begin_inset Formula $r\gets0$ +\end_inset + +. + Then repeat +\begin_inset Formula $b\gets f(b)$ +\end_inset + + up to +\begin_inset Formula $2^{r}$ +\end_inset + + times; + if at any point +\begin_inset Formula $b=a$ +\end_inset + +, + terminate with +\begin_inset Formula $\lambda$ +\end_inset + + equal to the number of times that +\begin_inset Formula $b\gets f(b)$ +\end_inset + + has been run in this iteration; + otherwise set +\begin_inset Formula $a\gets b$ +\end_inset + +, + +\begin_inset Formula $r\gets r+1$ +\end_inset + +, + and repeat this step. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc16[15] +\end_layout + +\end_inset + +A sequence generated as in exercise 6 must begin to repeat after at most +\begin_inset Formula $m$ +\end_inset + + values have been generated. + Suppose we generalize the method so that +\begin_inset Formula $X_{n+1}$ +\end_inset + + depends on +\begin_inset Formula $X_{n-1}$ +\end_inset + + as well as on +\begin_inset Formula $X_{n}$ +\end_inset + +; + formally, + let +\begin_inset Formula $f(x,y)$ +\end_inset + + be a function such that +\begin_inset Formula $0\leq x,y0. +\end{align*} + +\end_inset + +What is the maximum period conceivably attainable in this case? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +See exercise 17. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc17[10] +\end_layout + +\end_inset + +Generalize the situation in the previous exercise so that +\begin_inset Formula $X_{n+1}$ +\end_inset + + depends on the preceding +\begin_inset Formula $k$ +\end_inset + + values of the sequence. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +The maximum conceivable would be +\begin_inset Formula $m^{k}$ +\end_inset + +. + Why this is always attainable is not at all obvious. +\end_layout + +\end_body +\end_document diff --git a/vol2/3.2.1.1.lyx b/vol2/3.2.1.1.lyx new file mode 100644 index 0000000..7eec653 --- /dev/null +++ b/vol2/3.2.1.1.lyx @@ -0,0 +1,719 @@ +#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,x0$ +\end_inset + + such that +\begin_inset Formula $X_{n+\lambda}=X_{n}$ +\end_inset + + whenever +\begin_inset Formula $n\geq\mu$ +\end_inset + +, + and for which +\begin_inset Formula $\mu$ +\end_inset + + and +\begin_inset Formula $\lambda$ +\end_inset + + are the smallest possible values with this property. + (See exercises 3.1–6 and 3.2.1–1.) If +\begin_inset Formula $\mu_{j}$ +\end_inset + + and +\begin_inset Formula $\lambda_{j}$ +\end_inset + + are the indices corresponding to the sequences +\begin_inset Formula +\[ +(X_{0}\bmod p_{j}^{e_{j}},a\bmod p_{j}^{e_{j}},c\bmod p_{j}^{e_{j}},p_{j}^{e_{j}}), +\] + +\end_inset + +and if +\begin_inset Formula $\mu$ +\end_inset + + and +\begin_inset Formula $\lambda$ +\end_inset + + correspond to the composite sequence +\begin_inset Formula $(X_{0},a,c,p_{1}^{e_{1}}\cdots p_{t}^{e_{t}})$ +\end_inset + +, + Lemma Q states that +\begin_inset Formula $\lambda$ +\end_inset + + is the least common multiple of +\begin_inset Formula $\lambda_{1},\dots,\lambda_{t}$ +\end_inset + +. + What is the value of +\begin_inset Formula $\mu$ +\end_inset + + in terms of the values of +\begin_inset Formula $\mu_{1},\dots,\mu_{t}$ +\end_inset + +? + What is the maximum possible value of +\begin_inset Formula $\mu$ +\end_inset + + obtainable by varying +\begin_inset Formula $X_{0}$ +\end_inset + +, + +\begin_inset Formula $a$ +\end_inset + +, + and +\begin_inset Formula $c$ +\end_inset + +, + when +\begin_inset Formula $m=p_{1}^{e_{1}}\cdots p_{t}^{e_{t}}$ +\end_inset + + is fixed? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Since the +\begin_inset Formula $j$ +\end_inset + +th sequence has values +\begin_inset Formula $X_{n}\bmod p_{j}^{e_{j}}$ +\end_inset + +, + and the +\begin_inset Formula $X_{n}$ +\end_inset + + are uniquely determined by such values for all +\begin_inset Formula $j$ +\end_inset + +, + +\begin_inset Formula $(X_{n})_{n}$ +\end_inset + + enters into a loop whenever all the +\begin_inset Formula $X_{n}\bmod p_{j}^{e_{j}}$ +\end_inset + + have entered into a loop, + that is, + +\begin_inset Formula $\mu=\max_{j}\mu_{j}$ +\end_inset + +. + We are left to see what is the maximum +\begin_inset Formula $\mu$ +\end_inset + + when +\begin_inset Formula $m=p^{e}$ +\end_inset + + for some prime number +\begin_inset Formula $p$ +\end_inset + + and positive integer +\begin_inset Formula $e$ +\end_inset + + (for +\begin_inset Formula $m=1$ +\end_inset + +, + +\begin_inset Formula $\mu=0$ +\end_inset + +). + In this case, + +\begin_inset Formula $\mu$ +\end_inset + + is the lowest number such that +\begin_inset Formula +\[ +X_{\mu}=X_{\mu+\lambda}\equiv X_{\mu}a^{\lambda}+\frac{a^{\lambda}-1}{a-1}c\pmod{p^{e}}, +\] + +\end_inset + +if and only if +\begin_inset Formula $X_{\mu}(1-a^{\lambda})\equiv\frac{a^{\lambda}-1}{a-1}c\pmod{p^{e}}$ +\end_inset + +, + so for +\begin_inset Formula $\mu>0$ +\end_inset + +, + +\begin_inset Formula $\mu-1$ +\end_inset + + must be a number such that +\begin_inset Formula +\begin{align*} +X_{\mu-1}(1-a^{\lambda}) & \not\equiv\frac{a^{\lambda}-1}{a-1}c, & aX_{\mu-1}(1-a^{\lambda}) & \equiv a\frac{a^{\lambda}-1}{a-1}c & & \pmod{p^{e}}, +\end{align*} + +\end_inset + +where the first equation comes from changing +\begin_inset Formula $\mu$ +\end_inset + + to +\begin_inset Formula $\mu-1$ +\end_inset + + above and the second one from changing +\begin_inset Formula $X_{\mu}$ +\end_inset + + to +\begin_inset Formula $aX_{\mu-1}+c$ +\end_inset + + and rearranging terms. + This means that +\begin_inset Formula $a$ +\end_inset + + must be a multiple of +\begin_inset Formula $p$ +\end_inset + +. + Then, +\begin_inset Formula +\begin{align*} +X_{e} & \equiv X_{0}a^{e}+\frac{a^{e}-1}{a-1}c\equiv(a^{e-1}+a^{e-2}+\dots+a+1)c, & \pmod{p^{e}},\\ +X_{e+\lambda} & \equiv X_{0}a^{e+\lambda}+\frac{a^{e+\lambda}-1}{a-1}c\equiv(a^{e-1}+a^{e-2}+\dots+a+1)c, & \pmod{p^{e}}, +\end{align*} + +\end_inset + +since +\begin_inset Formula $a^{e}\equiv0$ +\end_inset + +, + so +\begin_inset Formula $\mu\leq e$ +\end_inset + +. + The value +\begin_inset Formula $\mu=e$ +\end_inset + + is reached when +\begin_inset Formula $(X_{0},a,c)=(1,p,0)$ +\end_inset + +. + Summing up, + the maximum for +\begin_inset Formula $m=p_{1}^{e_{1}}\cdots p_{t}^{e_{t}}$ +\end_inset + + is +\begin_inset Formula $\max\{e_{1},\dots,e_{t}\}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc9[M22] +\end_layout + +\end_inset + +(W. + E. + Thompson.) When +\begin_inset Formula $c=0$ +\end_inset + + and +\begin_inset Formula $m=2^{e}\geq16$ +\end_inset + +, + Theorems B and C say that the period has length +\begin_inset Formula $2^{e-2}$ +\end_inset + + if and only if the multiplier +\begin_inset Formula $a$ +\end_inset + + satisfies +\begin_inset Formula $a\bmod8=3$ +\end_inset + + or +\begin_inset Formula $a\bmod8=5$ +\end_inset + +. + Show that every such sequence is essentially a linear congruential sequence with +\begin_inset Formula $m=2^{e-2}$ +\end_inset + +, + having +\emph on +full +\emph default + period, + in the following sense: +\end_layout + +\begin_layout Enumerate +If +\begin_inset Formula $X_{n+1}=(4c+1)X_{n}\bmod2^{e}$ +\end_inset + +, + and +\begin_inset Formula $X_{n}=4Y_{n}+1$ +\end_inset + +, + then +\begin_inset Formula +\[ +Y_{n+1}=((4c+1)Y_{n}+c)\bmod2^{e-2}. +\] + +\end_inset + + +\end_layout + +\begin_layout Enumerate +If +\begin_inset Formula $X_{n+1}=(4c-1)X_{n}\bmod2^{e}$ +\end_inset + +, + and +\begin_inset Formula $X_{n}=((-1)^{n}(4Y_{n}+1))\bmod2^{e}$ +\end_inset + +, + then +\begin_inset Formula +\[ +Y_{n+1}=((1-4c)Y_{n}-c)\bmod2^{e-2}. +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +We start with +\begin_inset Formula $(Y_{n})_{n}$ +\end_inset + + as defined and see that +\begin_inset Formula $(X_{n})_{n}$ +\end_inset + + calculated from there matches the initial definition of +\begin_inset Formula $(X_{n})_{n}$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +We have +\begin_inset Formula $Y_{n}=\left((4c+1)^{n}Y_{0}+\frac{(4c+1)^{n}-1}{4\cancel{c}}\cancel{c}\right)\bmod2^{e-2}$ +\end_inset + +, + so +\begin_inset Formula +\[ +4Y_{n}+1\equiv(4Y_{0}+1)(4c+1)^{n}\equiv(4c+1)^{n}X_{0}\equiv X_{n}\pmod{2^{e}}. +\] + +\end_inset + + +\end_layout + +\begin_layout Enumerate +We have +\begin_inset Formula $Y_{n}=\left((1-4c)^{n}Y_{0}-\frac{(1-4c)^{n}-1}{-4c}c\right)\bmod2^{e-2}$ +\end_inset + +, + so +\begin_inset Formula +\begin{multline*} +(-1)^{n}(4Y_{n}+1)\equiv(-1)^{n}\left(4(1-4c)^{n}Y_{0}+(1-4c)^{n}\right)=(4Y_{0}+1)(4c-1)^{n}=\\ +=(4c-1)^{n}X_{0}\equiv X_{n+1}\pmod{2^{e}}. +\end{multline*} + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc16[M24] +\end_layout + +\end_inset + + +\emph on +(Existence of primitive roots.) +\emph default + Let +\begin_inset Formula $p$ +\end_inset + + be a prime number. +\end_layout + +\begin_layout Enumerate +Consider the polynomial +\begin_inset Formula $f(x)=x^{n}+c_{1}x^{n-1}+\dots+c_{n}$ +\end_inset + +, + where the +\begin_inset Formula $c$ +\end_inset + +'s are integers. + Given that +\begin_inset Formula $a$ +\end_inset + + is an integer for which +\begin_inset Formula $f(a)\equiv0\pmod p$ +\end_inset + +, + show that there exists a polynomial +\begin_inset Formula +\[ +q(x)=x^{n-1}+q_{1}x^{n-2}+\dots+q_{n-1} +\] + +\end_inset + +with integer coefficients such that +\begin_inset Formula $f(x)\equiv(x-a)q(x)\pmod p$ +\end_inset + + for all integers +\begin_inset Formula $x$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Let +\begin_inset Formula $f(x)$ +\end_inset + + be a polynomial as in (1). + Show that +\begin_inset Formula $f(x)$ +\end_inset + + has at most +\begin_inset Formula $n$ +\end_inset + + distinct +\begin_inset Quotes eld +\end_inset + +roots +\begin_inset Quotes erd +\end_inset + + modulo +\begin_inset Formula $p$ +\end_inset + +; + that is, + there are at most +\begin_inset Formula $n$ +\end_inset + + integers +\begin_inset Formula $a$ +\end_inset + +, + with +\begin_inset Formula $0\leq a0$ +\end_inset + +, + let +\begin_inset Formula $g(x)\coloneqq f(x)-c_{0}(x-a)x^{n-1}$ +\end_inset + + is a polynomial of degree +\begin_inset Formula $n-1$ +\end_inset + + such that +\begin_inset Formula $g(a)=f(a)=0$ +\end_inset + +, + so by induction there exists +\begin_inset Formula $r\in\mathbb{Z}_{p}(x)$ +\end_inset + + with +\begin_inset Formula $g(x)=(x-a)r(x)$ +\end_inset + +. + But then +\begin_inset Formula $f(x)=g(x)+c_{0}(x-a)x^{n-1}=(x-a)(r(x)+c_{0}x^{n-1})$ +\end_inset + +. + Note that this proof is valid even when changing +\begin_inset Formula $\mathbb{Z}_{p}$ +\end_inset + + to any other domain. +\end_layout + +\begin_layout Enumerate +If +\begin_inset Formula $a$ +\end_inset + + and +\begin_inset Formula $b$ +\end_inset + + are different roots of +\begin_inset Formula $f$ +\end_inset + +, + then +\begin_inset Formula $f(x)=(x-a)q(x)$ +\end_inset + + for some +\begin_inset Formula $q\in\mathbb{Z}_{p}[X]$ +\end_inset + +, + and +\begin_inset Formula $b$ +\end_inset + + is still a root of +\begin_inset Formula $q$ +\end_inset + + as, + if it wasn't, + it wouldn't be a root of +\begin_inset Formula $f$ +\end_inset + + either. + Therefore, + by induction, + a polynomial +\begin_inset Formula $f\in\mathbb{Z}_{p}[X]\setminus0$ +\end_inset + + with +\begin_inset Formula $n$ +\end_inset + + different roots has at least degree +\begin_inset Formula $n$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Yes. + Trivial. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc20[M24] +\end_layout + +\end_inset + +(G. + Marsaglia.) The purpose of this exercise is to study the period length of an +\emph on +arbitrary +\emph default + linear congruential sequence. + Let +\begin_inset Formula $Y_{n}=1+a+\dots+a^{n-1}$ +\end_inset + +, + so that +\begin_inset Formula $X_{n}=(AY_{n}+X_{0})\bmod m$ +\end_inset + + for some constant +\begin_inset Formula $A$ +\end_inset + + by Eq. + 3.2.1–(8). +\end_layout + +\begin_layout Enumerate +Prove that the period length of +\begin_inset Formula $\langle X_{n}\rangle$ +\end_inset + + is the period length of +\begin_inset Formula $\langle Y_{n}\bmod m'\rangle$ +\end_inset + +, + where +\begin_inset Formula $m'=m/\gcd(A,m)$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Prove that the period length of +\begin_inset Formula $\langle Y_{n}\bmod p^{e}\rangle$ +\end_inset + + satisfies the following when +\begin_inset Formula $p$ +\end_inset + + is prime: +\end_layout + +\begin_deeper +\begin_layout Enumerate +If +\begin_inset Formula $a\bmod p=0$ +\end_inset + +, + it is 1. +\end_layout + +\begin_layout Enumerate +If +\begin_inset Formula $a\bmod p=1$ +\end_inset + +, + it is +\begin_inset Formula $p^{e}$ +\end_inset + +, + except when +\begin_inset Formula $p=2$ +\end_inset + + and +\begin_inset Formula $e\geq2$ +\end_inset + + and +\begin_inset Formula $a\bmod4=3$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +If +\begin_inset Formula $p=2$ +\end_inset + +, + +\begin_inset Formula $e\geq2$ +\end_inset + +, + and +\begin_inset Formula $a\bmod4=3$ +\end_inset + +, + it is twice the order of +\begin_inset Formula $a$ +\end_inset + + modulo +\begin_inset Formula $p^{e}$ +\end_inset + + (see exercise 11), + unless +\begin_inset Formula $a\equiv-1\pmod{2^{e}}$ +\end_inset + + when it is 2. +\end_layout + +\begin_layout Enumerate +If +\begin_inset Formula $a\bmod p>1$ +\end_inset + +, + it is the order of +\begin_inset Formula $a$ +\end_inset + + modulo +\begin_inset Formula $p^{e}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula +\[ +X_{n}=X_{n+m}\iff AY_{n}\equiv AY_{n+m}\pmod m\iff Y_{n}\equiv Y_{n+m}\pmod{m'}. +\] + +\end_inset + +Note that +\begin_inset Formula $\langle Y_{n}\bmod t\rangle$ +\end_inset + +, + +\begin_inset Formula $t\in\mathbb{Z}^{+}$ +\end_inset + +, + is the linear congruential sequence with +\begin_inset Formula $Y_{0}=0$ +\end_inset + +, + +\begin_inset Formula $c=1$ +\end_inset + +, + +\begin_inset Formula $a=a$ +\end_inset + +, + and +\begin_inset Formula $m=t$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Enumerate +For +\begin_inset Formula $n\geq e-1$ +\end_inset + +, + +\begin_inset Formula $Y_{n}=(1+a+a^{2}+\dots+a^{e-1})\bmod p$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Then we're in the conditions of Theorem A. +\end_layout + +\begin_layout Enumerate +If +\begin_inset Formula $e=2$ +\end_inset + +, + then +\begin_inset Formula $a\equiv-1\pmod 4$ +\end_inset + + and this part doesn't apply, + so we assume +\begin_inset Formula $e>2$ +\end_inset + +. + Let +\begin_inset Formula $\lambda$ +\end_inset + + be the order of +\begin_inset Formula $a$ +\end_inset + + modulo +\begin_inset Formula $2^{e}$ +\end_inset + +, + obviously +\begin_inset Formula $\lambda>1$ +\end_inset + +, + so +\begin_inset Formula +\begin{multline*} +Y_{k}=1+a+\dots+a^{k-1}=\frac{a^{k}-1}{a-1}\equiv Y_{0}=0\pmod{2^{e}}\iff\\ +\iff a^{k}-1\equiv0\pmod{2^{e}(a-1)}\iff2^{e}(a-1)\mid a^{k}-1. +\end{multline*} + +\end_inset + +The order +\begin_inset Formula $\lambda$ +\end_inset + + of +\begin_inset Formula $a$ +\end_inset + + modulo +\begin_inset Formula $2^{e}$ +\end_inset + + is the smallest number such that +\begin_inset Formula $2^{e}\mid a^{k}-1$ +\end_inset + +, + and in fact +\begin_inset Formula +\[ +2^{e}\mid a^{k}-1\iff a^{k}\equiv1\pmod{2^{e}}\iff\lambda\mid k. +\] + +\end_inset + +Exercise 11 gives us an unique +\begin_inset Formula $f>1$ +\end_inset + + such that +\begin_inset Formula $a\bmod2^{f+1}=2^{f}\pm1$ +\end_inset + +, + and then says that +\begin_inset Formula $\lambda=2^{e-f}$ +\end_inset + +. + This can be used to prove that +\begin_inset Formula $a^{\lambda}-1$ +\end_inset + + is not a multiple of +\begin_inset Formula $2^{e}(a-1)$ +\end_inset + +, + as if this were the case, + then +\begin_inset Formula $a^{\lambda-1}$ +\end_inset + + would be a multiple of +\begin_inset Formula $2^{e+1}$ +\end_inset + + because +\begin_inset Formula $a-1$ +\end_inset + + is even, + but by Exercise 11 the order of +\begin_inset Formula $a$ +\end_inset + + modulo +\begin_inset Formula $e+1$ +\end_inset + + is +\begin_inset Formula $2^{e+1-f}>\lambda\#$ +\end_inset + +. + However, + since +\begin_inset Formula $a^{\lambda}-1$ +\end_inset + + is a multiple of both +\begin_inset Formula $2^{e}$ +\end_inset + + and +\begin_inset Formula $a^{\lambda}-1$ +\end_inset + +, + it is a multiple of +\begin_inset Formula $\text{lcm}\{2^{e},a^{\lambda}-1\}=\frac{2^{e}(a^{\lambda}-1)}{2}$ +\end_inset + + and therefore +\begin_inset Formula $a^{2\lambda}-1=(a^{\lambda}-1)(a^{\lambda}+1)=(a^{\lambda}-1)^{2}+2(a^{\lambda}-1)$ +\end_inset + + is a multiple of +\begin_inset Formula $2^{e}(a^{\lambda}-1)$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Like before, + +\begin_inset Formula $Y_{k}\equiv0\pmod{2^{e}}\iff p^{e}(a-1)\mid a^{k}-1$ +\end_inset + +. + This time, + however, + +\begin_inset Formula $\gcd\{a-1,p^{e}\}=1$ +\end_inset + +, + so +\begin_inset Formula $p^{e}(a-1)\mid a^{k}-1\iff p^{e},a-1\mid a^{k}-1\iff p^{e}\mid a^{k}-1$ +\end_inset + +, + and the lowest +\begin_inset Formula $k$ +\end_inset + + for which this happens is precisely the order of +\begin_inset Formula $a$ +\end_inset + + modulo +\begin_inset Formula $p^{e}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc22[M25] +\end_layout + +\end_inset + +Discuss the problem of finding moduli +\begin_inset Formula $m=b^{k}\pm b^{l}\pm1$ +\end_inset + + so that the subtract-with-borrow and add-with-carry generators of exercise 3.2.1.1–14 will have very long periods. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +First we would need the prime factorization of +\begin_inset Formula $m$ +\end_inset + +, + which is not easily characterized from +\begin_inset Formula $b$ +\end_inset + +, + +\begin_inset Formula $k$ +\end_inset + +, + and +\begin_inset Formula $l$ +\end_inset + +. + Once we have that we may apply Theorems A–C. + The solution in the book suggests looking for +\begin_inset Formula $m$ +\end_inset + + to be prime. +\end_layout + +\end_body +\end_document diff --git a/vol2/3.2.1.3.lyx b/vol2/3.2.1.3.lyx new file mode 100644 index 0000000..e94ce2c --- /dev/null +++ b/vol2/3.2.1.3.lyx @@ -0,0 +1,273 @@ +#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 +exerc1[M10] +\end_layout + +\end_inset + +Show that, + no matter what the byte size +\begin_inset Formula $B$ +\end_inset + + of +\family typewriter +MIX +\family default + happens to be, + the code (3) yields a random number generator of maximum period. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +This generator has +\begin_inset Formula $a=B^{2}+1$ +\end_inset + +, + +\begin_inset Formula $c=1$ +\end_inset + +, + and +\begin_inset Formula $m=B^{5}$ +\end_inset + +. + Since the prime divisors of +\begin_inset Formula $B^{5}$ +\end_inset + + and +\begin_inset Formula $B^{2}$ +\end_inset + + are the same, + the conditions of Theorem 3.2.1.2A are satisfied. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc2[10] +\end_layout + +\end_inset + +What is the potency of the generator represented by the +\family typewriter +MIX +\family default + code (3)? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +3. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc6[20] +\end_layout + +\end_inset + +Which of the values of +\begin_inset Formula $m=w\pm1$ +\end_inset + + in Table 3.2.1–1 can be used in a linear congruential sequence of maximum period whose potency is 4 or more? + (Use the result of exercise 5.) +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +By exercise 5, + for a modulus +\begin_inset Formula $m=p_{1}^{e_{1}}\cdots p_{t}^{e_{t}}$ +\end_inset + + with +\begin_inset Formula $e_{1}\geq\dots\geq e_{t}$ +\end_inset + +, + +\begin_inset Formula $a=p_{1}+1$ +\end_inset + + has the maximum potency, + which is +\begin_inset Formula $e_{1}$ +\end_inset + +, + except that if +\begin_inset Formula $m=p_{1}$ +\end_inset + +, + then the maximum potency is 0, + corresponding to +\begin_inset Formula $a=1$ +\end_inset + +. + Thus the values from the table that can be used are +\begin_inset Formula $10^{9}-1=3^{4}\cdot37\cdot333667$ +\end_inset + + and +\begin_inset Formula $2^{27}+1=3^{4}\cdot19\cdot87211$ +\end_inset + +. +\end_layout + +\end_body +\end_document diff --git a/vol2/3.2.1.lyx b/vol2/3.2.1.lyx new file mode 100644 index 0000000..f78e3ee --- /dev/null +++ b/vol2/3.2.1.lyx @@ -0,0 +1,320 @@ +#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 +exerc1[10] +\end_layout + +\end_inset + +Example (3) shows a situation in which +\begin_inset Formula $X_{4}=X_{0}$ +\end_inset + +, + so the sequence begins again from the beginning. + Give an example of a linear congruential sequence with +\begin_inset Formula $m=10$ +\end_inset + + for which +\begin_inset Formula $X_{0}$ +\end_inset + + never appears again in the sequence. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +This happens if +\begin_inset Formula $a=c=0$ +\end_inset + + and +\begin_inset Formula $0X_{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 diff --git a/vol2/3.3.1.lyx b/vol2/3.3.1.lyx new file mode 100644 index 0000000..f2bfc5c --- /dev/null +++ b/vol2/3.3.1.lyx @@ -0,0 +1,607 @@ +#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 FormulaMacro +\newcommand{\stirla}[2]{\genfrac[]{0pt}{}{#1}{#2}} +{\begin{bmatrix}{\textstyle #1}\\ +{\textstyle #2} +\end{bmatrix}} +\end_inset + + +\begin_inset FormulaMacro +\newcommand{\stirlb}[2]{\genfrac\{\}{0pt}{}{#1}{#2}} +{\begin{Bmatrix}{\textstyle #1}\\ +{\textstyle #2} +\end{Bmatrix}} +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc1[00] +\end_layout + +\end_inset + +What line of the chi-square table should be used to check whether or not the value +\begin_inset Formula $V=7\frac{7}{48}$ +\end_inset + + of Eq. + (5) is improbably high? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Row +\begin_inset Formula $\nu=k-1=11-1=10$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc3[23] +\end_layout + +\end_inset + +Some dice that were loaded as described in the previous exercise were rolled 144 times, + and the following values were observed: +\begin_inset Formula +\[ +\begin{array}{rrrrrrrrrrrr} +\text{value of }s= & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ +\text{observed number, }Y_{s}= & 2 & 6 & 10 & 16 & 18 & 32 & 20 & 13 & 16 & 9 & 2 +\end{array} +\] + +\end_inset + +Apply the chi-square test to +\emph on +these +\emph default + values, + using the probabilities in (1), + pretending that the dice are not in fact known to be faulty. + Does the chi-square test detect the bad dice? + If not, + explain why not. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +We take the values +\begin_inset Formula $np_{s}$ +\end_inset + + from (2), + to get: +\begin_inset Formula +\begin{align*} +V & =\sum_{s=2}^{12}\frac{(Y_{s}-np_{s})^{2}}{np_{s}}=\frac{4}{4}+\frac{4}{8}+\frac{4}{12}+\frac{0}{16}+\frac{4}{20}+\frac{64}{24}+\frac{0}{20}+\frac{9}{16}+\frac{16}{12}+\frac{1}{8}+\frac{4}{4}\\ + & =1+\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{8}{3}+\frac{9}{16}+\frac{4}{3}+\frac{1}{8}+1=2+\frac{13}{3}+\frac{19}{16}+\frac{1}{5}\\ + & =7+\frac{80+45+48}{240}=7+\frac{173}{240}. +\end{align*} + +\end_inset + +Using +\begin_inset Formula $n=10$ +\end_inset + + we get a probability between +\begin_inset Formula $.25$ +\end_inset + + and +\begin_inset Formula $.5$ +\end_inset + +, + which is not suspect. + This seems to be because the bias of one die compensates that of the other, + smoothing out the probability differences. + The difference could be discovered with a large enough value of +\begin_inset Formula $n$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc4[23] +\end_layout + +\end_inset + +The author actually obtained the data in experiment 1 of (9) by simulating dice in which one was normal, + the other was loaded so that it always turned up 1 or 6. + (The latter two possibilities were equally probable.) Compute the probabilities that replace (1) in this case, + and by using a chi-square test decide if the results of that experiment are consistent with the dice being loaded in this way. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +We compute the table with the sum of the two dice: +\begin_inset Formula +\[ +\begin{array}{r|rrrrrr} + & 1 & 2 & 3 & 4 & 5 & 6\\ +\hline 1 & 2 & 3 & 4 & 5 & 6 & 7\\ +6 & 7 & 8 & 9 & 10 & 11 & 12 +\end{array} +\] + +\end_inset + +This gives us the following table of probabilities: +\begin_inset Formula +\[ +\begin{array}{rrrrrrrrrrrr} +s= & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ +144p_{s}= & 12 & 12 & 12 & 12 & 12 & 24 & 12 & 12 & 12 & 12 & 12 +\end{array} +\] + +\end_inset + +Thus, +\begin_inset Formula +\begin{align*} +V & =\frac{1}{12}\left(8^{2}+2^{2}+2^{2}+1^{2}+8^{2}+\frac{6^{2}}{2}+6^{2}+1^{2}+1^{2}+2^{2}+1^{2}\right)\\ + & =\frac{1}{12}(64+4+4+1+64+18+26+1+1+2+1)=\frac{186}{12}=15+\frac{1}{2}. +\end{align*} + +\end_inset + +With +\begin_inset Formula $n=10$ +\end_inset + +, + this is somewhat in the middle of +\begin_inset Formula $p=.75$ +\end_inset + + and +\begin_inset Formula $p=.95$ +\end_inset + +, + which is consistent. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc8[00] +\end_layout + +\end_inset + +The text describes an experiment in which 20 values of the statistic +\begin_inset Formula $K_{10}^{+}$ +\end_inset + + were obtained in the study of a random sequence. + These values were plotted, + to obtain Fig. + 4, + and a KS statistic was computed from the resulting graph. + Why were the table entries for +\begin_inset Formula $n=20$ +\end_inset + + used to study the resulting statistic, + instead of the table entries for +\begin_inset Formula $n=10$ +\end_inset + +? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Because the value of +\begin_inset Formula $n$ +\end_inset + + to use is not about the underlying probability distribution (which can be an arbitrary real-valued one, + not just +\begin_inset Formula $K_{n}^{+}$ +\end_inset + + or +\begin_inset Formula $K_{n}^{-}$ +\end_inset + +), + but rather it is the number of observations we make for this distribution, + which is 20. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc9[20] +\end_layout + +\end_inset + +The experiment described in the text consisted of plotting 20 values of +\begin_inset Formula $K_{10}^{+}$ +\end_inset + +, + computed from the maximum-of-5 test applied to different parts of a random sequence. + We could have computed also the corresponding 20 values of +\begin_inset Formula $K_{10}^{-}$ +\end_inset + +; + since +\begin_inset Formula $K_{10}^{-}$ +\end_inset + + has the same distribution as +\begin_inset Formula $K_{10}^{+}$ +\end_inset + +, + we could lump together the 40 values thus obtained (that is, + 20 of the +\begin_inset Formula $K_{10}^{+}$ +\end_inset + +'s and 20 of the +\begin_inset Formula $K_{10}^{-}$ +\end_inset + +'s), + and a KS test could be applied so that we would get new values +\begin_inset Formula $K_{40}^{+}$ +\end_inset + +, + +\begin_inset Formula $K_{40}^{-}$ +\end_inset + +. + Discuss the merits of this idea. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +The issue here is that the 40 points would not be independent; + if the maximum of 5 is low, + the minimum of 5 must be necessarily lower, + the probability of it being higher is 0. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc10[20] +\end_layout + +\end_inset + +Suppose a chi-square test is done by making +\begin_inset Formula $n$ +\end_inset + + observations, + and the value +\begin_inset Formula $V$ +\end_inset + + is obtained. + Now we repeat the test on these same +\begin_inset Formula $n$ +\end_inset + + observations over again (getting, + of course, + the same results), + and we put together the data from both tests, + regarding it as a single chi-square test with +\begin_inset Formula $2n$ +\end_inset + + observations. + (This procedure violates the text's stipulation that all of the observations must be independent of one another.) How is the second value of +\begin_inset Formula $V$ +\end_inset + + related to the first one? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Let +\begin_inset Formula $Y'_{s}=2Y_{s}$ +\end_inset + + be the number of observations of category +\begin_inset Formula $s$ +\end_inset + + in the second test, + the second value of +\begin_inset Formula $V$ +\end_inset + + is +\begin_inset Formula +\[ +V'=\sum_{s=1}^{k}\frac{(Y'_{s}-2np_{s})^{2}}{2np_{s}}=\sum_{s=1}^{k}\frac{(2Y_{s}-2np_{s})^{2}}{2np_{s}}=2V. +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc11[10] +\end_layout + +\end_inset + +Solve exercise 10 substituting the KS test for the chi-square test. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +This time, + after sorting the +\begin_inset Formula $2n$ +\end_inset + + observations +\begin_inset Formula $X'_{1},\dots,X'_{2n}$ +\end_inset + +, + we have +\begin_inset Formula $X_{j}=X'_{2j-1}=X'_{2j}$ +\end_inset + +, + so +\begin_inset Formula +\[ +K_{2n}^{+}=\sqrt{2n}\max_{1\leq j\leq2n}\left(\frac{j}{2n}-F(X'_{j})\right)=\sqrt{2n}\max_{1\leq j\leq n}\left(\frac{2j}{2n}-F(X_{j})\right)=\sqrt{2}K_{n}^{+}, +\] + +\end_inset + +and similarly, +\begin_inset Formula +\[ +K_{2n}^{-}=\sqrt{2n}\max_{1\leq j\leq2n}\left(F(X'_{j})-\frac{j-1}{2n}\right)=\sqrt{2n}\max_{1\leq j\leq n}\left(F(X_{j})-\frac{2j-2}{2n}\right)=\sqrt{2}K_{n}^{-}. +\] + +\end_inset + + +\end_layout + +\end_body +\end_document diff --git a/vol2/3.3.2.lyx b/vol2/3.3.2.lyx new file mode 100644 index 0000000..03a3027 --- /dev/null +++ b/vol2/3.3.2.lyx @@ -0,0 +1,1009 @@ +#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 +exerc1[10] +\end_layout + +\end_inset + +Why should the serial test described in part B be applied to +\begin_inset Formula +\[ +(Y_{0},Y_{1}),(Y_{2},Y_{3}),\dots,(Y_{2n-2},Y_{2n-1}) +\] + +\end_inset + +instead of to +\begin_inset Formula $(Y_{0},Y_{1}),(Y_{1},Y_{2}),\dots,(Y_{n-1},Y_{n})$ +\end_inset + +? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Otherwise the points wouldn't be independent. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc2[10] +\end_layout + +\end_inset + +State an appropriate way to generalize the serial test to triples, + quadruples, + etc., + instead of pairs. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +For +\begin_inset Formula $k$ +\end_inset + +-tuples, + use points +\begin_inset Formula $(Y_{0},\dots,Y_{k-1}),(Y_{k},\dots,Y_{2k-1}),\dots,(Y_{k(n-1)},\dots,Y_{kn-1})$ +\end_inset + +. + The chi-square method is applied to the +\begin_inset Formula $d^{k}$ +\end_inset + + possible categories and at least +\begin_inset Formula $5d^{k}$ +\end_inset + + values of +\begin_inset Formula $U$ +\end_inset + + should be taken. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc3[M20] +\end_layout + +\end_inset + +How many +\begin_inset Formula $U$ +\end_inset + +'s need to be examined in the gap test (Algorithm G) before +\begin_inset Formula $n$ +\end_inset + + gaps have been found, + on average, + assuming that the sequence is random? + What is the standard deviation of this quantity? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +The probability of a given value being the end of a gap is +\begin_inset Formula $p\coloneqq\frac{1}{\beta-\alpha}$ +\end_inset + +, + so the gap lengths have approximately exponential distribution and therefore we should take about +\begin_inset Formula $np=\frac{n}{\beta-\alpha}$ +\end_inset + + +\begin_inset Formula $U$ +\end_inset + +'s. + More precisely, + let +\begin_inset Formula $q\coloneqq1-p$ +\end_inset + +, + the probability of a gap with length +\begin_inset Formula $k$ +\end_inset + + is +\begin_inset Formula $q^{k-1}p$ +\end_inset + +, + so the average is +\begin_inset Formula +\[ +\sum_{k=1}^{\infty}q^{k-1}pk=p\sum_{k=1}^{\infty}kq^{k-1}=p\sum_{j=1}^{\infty}\sum_{k=j}^{\infty}q^{k-1}=p\sum_{j=1}^{\infty}\frac{q^{j-1}}{1-q}=\sum_{j=0}^{\infty}q^{j}=\frac{1}{1-q}=\frac{1}{p}, +\] + +\end_inset + +so the approximation above is actually the exact value of the mean gap length and the average is exactly +\begin_inset Formula $\frac{n}{\beta-\alpha}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc7[08] +\end_layout + +\end_inset + +Apply the coupon collector's test procedure (Algorithm C), + with +\begin_inset Formula $d=3$ +\end_inset + + and +\begin_inset Formula $n=7$ +\end_inset + +, + to the sequence 1101221022120202001212201010201121. + What length do the seven subsequences have? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + + +\begin_inset Formula $5,3,5,6,5,5,4$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc8[M22] +\end_layout + +\end_inset + +How many +\begin_inset Formula $U$ +\end_inset + +'s need to be examined in the coupon collector's test, + on the average, + before +\begin_inset Formula $n$ +\end_inset + + complete sets have been found by Algorithm C, + assuming that the sequence is random? + What is the standard deviation? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Given that +\begin_inset Formula $\stirlb rd=0$ +\end_inset + + for +\begin_inset Formula $rk$ +\end_inset + +, +\begin_inset Formula +\[ +\sum_{0\leq jk$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc19[M23] +\end_layout + +\end_inset + +Show that the +\emph on +serial test +\emph default + can be analyzed over the full period, + in terms of generalized Dedekind sums, + by finding a formula for the probability that +\begin_inset Formula $\alpha\leq X_{n}<\beta$ +\end_inset + + and +\begin_inset Formula $\alpha'\leq X_{n+1}<\beta'$ +\end_inset + +, + when +\begin_inset Formula $\alpha$ +\end_inset + +, + +\begin_inset Formula $\beta$ +\end_inset + +, + +\begin_inset Formula $\alpha'$ +\end_inset + +, + and +\begin_inset Formula $\beta'$ +\end_inset + + are given integers with +\begin_inset Formula $0\leq\alpha<\beta\leq m$ +\end_inset + + and +\begin_inset Formula $0\leq\alpha'<\beta'\leq m$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + + +\begin_inset Formula $P(x)\coloneqq\left\lfloor \frac{x-\alpha}{m}\right\rfloor -\left\lfloor \frac{x-\beta}{m}\right\rfloor $ +\end_inset + + is 1 precisely when +\begin_inset Formula $x\in[\alpha,\beta)$ +\end_inset + + and 0 for any other +\begin_inset Formula $x\in[0,1)$ +\end_inset + +. + +\begin_inset Formula $Q(x)\coloneqq\left\lfloor \frac{x-\alpha'}{m}\right\rfloor -\left\lfloor \frac{x-\beta'}{m}\right\rfloor $ +\end_inset + + works in an analogous manner. + For a linear congruential sequence given by +\begin_inset Formula $S(x)\coloneqq(ax+c)\bmod m$ +\end_inset + + that has maximum period, + the probability that +\begin_inset Formula $x_{n}\in[\alpha,\beta)\land x_{n+1}\in[\alpha',\beta')$ +\end_inset + + is +\begin_inset Formula +\begin{multline*} +\frac{1}{m}\sum_{0\leq x0$ +\end_inset + +. + Then the graph for +\begin_inset Formula $\{ax+\theta\}$ +\end_inset + + is a sequence of lines. + The first goes from +\begin_inset Formula $(0,\theta)$ +\end_inset + + to +\begin_inset Formula $(\frac{1-\theta}{a},1)$ +\end_inset + +, + the next one from +\begin_inset Formula $(\frac{1-\theta}{a},0)$ +\end_inset + + to +\begin_inset Formula $(\frac{2-\theta}{a},1)$ +\end_inset + +, + etc., + and the last one goes from +\begin_inset Formula $(1-\tfrac{\theta}{a},0)$ +\end_inset + + to +\begin_inset Formula $(1,\theta)$ +\end_inset + + (we used that +\begin_inset Formula $a$ +\end_inset + + is an integer to calculate this). + Thus +\begin_inset Formula +\[ +\int_{0}^{1}x\{ax+\theta\}\text{d}x=\sum_{k=1}^{a-1}\int_{\frac{k-\theta}{a}}^{\frac{k+1-\theta}{a}}x(ax+\theta-k)\text{d}x+\int_{0}^{\frac{1-\theta}{a}}x(ax+\theta)\text{d}x+\int_{1-\frac{\theta}{a}}^{1}x(ax+\theta-a)\text{d}x. +\] + +\end_inset + +Now, +\begin_inset Formula +\[ +\int x(ax+\theta-k)\text{d}x=\frac{a}{3}x^{3}+\frac{\theta-k}{2}x^{2}+C, +\] + +\end_inset + +so if we call +\begin_inset Formula $x_{k}\coloneqq\frac{k-\theta}{a}$ +\end_inset + + except that +\begin_inset Formula $x_{0}\coloneqq0$ +\end_inset + + and +\begin_inset Formula $x_{a+1}\coloneqq1$ +\end_inset + +, + we have +\begin_inset Formula +\begin{multline*} +\int_{0}^{1}x\{ax+\theta\}\text{d}x=\sum_{0\leq k\leq a}\int_{x_{k}}^{x_{k+1}}x(ax+\theta-k)\text{d}x=\\ +=\sum_{0\leq k\leq a}\left(\frac{a}{3}x_{k+1}^{3}+\frac{\theta-k}{2}x_{k+1}^{2}-\frac{a}{3}x_{k}^{3}-\frac{\theta-k}{2}x_{k}^{2}\right)=\frac{a}{3}+\frac{\theta-a}{2}+\sum_{0V_{j}\cdot V_{j}$ +\end_inset + + in some step, + then +\begin_inset Formula +\[ +(V_{i}-qV_{j})\cdot(V_{i}-qV_{j})=V_{i}\cdot V_{i}-2qV_{i}\cdot V_{j}+V_{j}\cdot V_{j}1$ +\end_inset + +, + if there is a +\begin_inset Formula $j$ +\end_inset + + such that +\begin_inset Formula $n=n_{j}$ +\end_inset + +, + we pack the +\begin_inset Formula $n_{j}$ +\end_inset + + cubes of color +\begin_inset Formula $C_{j}$ +\end_inset + + into +\begin_inset Formula $B_{j}$ +\end_inset + +; + otherwise there exists +\begin_inset Formula $i$ +\end_inset + + and +\begin_inset Formula $j$ +\end_inset + + such that +\begin_inset Formula $n_{i}= $P[$piece] ) { +\end_layout + +\begin_layout Plain Layout + + $abs = $Y[$piece] + $dev * $Z[$piece]; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + elsif ( $piece <= 15 ) { +\end_layout + +\begin_layout Plain Layout + + $abs = $S[$piece] + $dev * $Q[$piece]; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + elsif ( $piece < 31 ) { +\end_layout + +\begin_layout Plain Layout + + $piece -= 16; +\end_layout + +\begin_layout Plain Layout + + my ( $u, + $v ); +\end_layout + +\begin_layout Plain Layout + + do { +\end_layout + +\begin_layout Plain Layout + + ( $u, + $v ) = ( rand, + rand ); +\end_layout + +\begin_layout Plain Layout + + ( $u, + $v ) = ( $v, + $u ) if $u > $v; +\end_layout + +\begin_layout Plain Layout + + $abs = $S[$piece] + $u / 5; +\end_layout + +\begin_layout Plain Layout + + } while ( $v < $D[$piece] +\end_layout + +\begin_layout Plain Layout + + || $v <= $u + +\end_layout + +\begin_layout Plain Layout + + $E[$piece] * ( exp( ( $S[ $piece + 1 ]**2 - $abs**2 ) / 2 ) - 1 ) ); +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + else { +\end_layout + +\begin_layout Plain Layout + + do { $abs = sqrt( 9 - 2 * log rand ) } while ( $abs * rand ) >= 3; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + return $sign ? + -$abs : + $abs; +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset listings +inline false +status open + +\begin_layout Plain Layout + +local D = ... +\end_layout + +\begin_layout Plain Layout + +local E = ... +\end_layout + +\begin_layout Plain Layout + +local P = ... +\end_layout + +\begin_layout Plain Layout + +local Q = ... +\end_layout + +\begin_layout Plain Layout + +local S = ... +\end_layout + +\begin_layout Plain Layout + +local Y = ... +\end_layout + +\begin_layout Plain Layout + +local Z = ... +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\begin_layout Plain Layout + +local function normal () +\end_layout + +\begin_layout Plain Layout + + local rand = math.random() +\end_layout + +\begin_layout Plain Layout + + local sign = math.floor(rand * 2) +\end_layout + +\begin_layout Plain Layout + + local piece = math.floor(rand * 64) % 32 +\end_layout + +\begin_layout Plain Layout + + local dev = (rand * 64) % 1 +\end_layout + +\begin_layout Plain Layout + + local abs +\end_layout + +\begin_layout Plain Layout + + if dev >= P[piece] then +\end_layout + +\begin_layout Plain Layout + + abs = Y[piece] + dev * Z[piece] +\end_layout + +\begin_layout Plain Layout + + elseif piece <= 15 then +\end_layout + +\begin_layout Plain Layout + + abs = S[piece] + dev * Q[piece] +\end_layout + +\begin_layout Plain Layout + + elseif piece < 31 then +\end_layout + +\begin_layout Plain Layout + + local u, + v +\end_layout + +\begin_layout Plain Layout + + repeat +\end_layout + +\begin_layout Plain Layout + + u, + v = math.random(), + math.random() +\end_layout + +\begin_layout Plain Layout + + if u > v then u, + v = v, + u end +\end_layout + +\begin_layout Plain Layout + + abs = S[piece-15] + u/5 +\end_layout + +\begin_layout Plain Layout + + until v >= D[piece-15] or +\end_layout + +\begin_layout Plain Layout + + v > u + E[piece-15] * (math.exp((S[piece-14]^2 - abs^2) / 2) - 1) +\end_layout + +\begin_layout Plain Layout + + else +\end_layout + +\begin_layout Plain Layout + + repeat +\end_layout + +\begin_layout Plain Layout + + abs = math.sqrt(9 - 2 * math.log(math.random())) +\end_layout + +\begin_layout Plain Layout + + until abs * rand >= 3 +\end_layout + +\begin_layout Plain Layout + + end +\end_layout + +\begin_layout Plain Layout + + if sign == 0 then return abs else return -abs end +\end_layout + +\begin_layout Plain Layout + +end +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset listings +inline false +status open + +\begin_layout Plain Layout + +from math import exp, + floor, + log, + sqrt +\end_layout + +\begin_layout Plain Layout + +from random import random +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\begin_layout Plain Layout + +D, + E, + P, + Q, + S, + Y, + Z = [], + [], + [], + [], + [], + [], + [] +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\begin_layout Plain Layout + +def normal(): +\end_layout + +\begin_layout Plain Layout + + rand = random() +\end_layout + +\begin_layout Plain Layout + + sign = floor(rand * 2) +\end_layout + +\begin_layout Plain Layout + + piece = floor(rand * 64) % 32 +\end_layout + +\begin_layout Plain Layout + + dev = (rand * 64) % 1 +\end_layout + +\begin_layout Plain Layout + + if dev >= P[piece]: +\end_layout + +\begin_layout Plain Layout + + result = Y[piece] + dev * Z[piece] +\end_layout + +\begin_layout Plain Layout + + elif piece <= 15: +\end_layout + +\begin_layout Plain Layout + + result = S[piece] + dev * Q[piece] +\end_layout + +\begin_layout Plain Layout + + elif piece < 31: +\end_layout + +\begin_layout Plain Layout + + piece = piece - 16 +\end_layout + +\begin_layout Plain Layout + + while True: +\end_layout + +\begin_layout Plain Layout + + u, + v = random(), + random() +\end_layout + +\begin_layout Plain Layout + + if u > v: +\end_layout + +\begin_layout Plain Layout + + u, + v = v, + u +\end_layout + +\begin_layout Plain Layout + + result = S[piece] + u/5 +\end_layout + +\begin_layout Plain Layout + + if v >= D[piece]: +\end_layout + +\begin_layout Plain Layout + + break +\end_layout + +\begin_layout Plain Layout + + if v < u + E[piece] * (exp((S[piece+1]**2 - abs**2)/2) - 1): +\end_layout + +\begin_layout Plain Layout + + break +\end_layout + +\begin_layout Plain Layout + + else: +\end_layout + +\begin_layout Plain Layout + + while True: +\end_layout + +\begin_layout Plain Layout + + result = sqrt(9 - 2*log(random())) +\end_layout + +\begin_layout Plain Layout + + if result * random() < 3: +\end_layout + +\begin_layout Plain Layout + + break +\end_layout + +\begin_layout Plain Layout + + if sign: +\end_layout + +\begin_layout Plain Layout + + result = -result +\end_layout + +\begin_layout Plain Layout + + return result +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc16[HM22] +\end_layout + +\end_inset + +(J. + H. + Ahrens.) Develop an algorithm for gamma deviates of order +\begin_inset Formula $a$ +\end_inset + + when +\begin_inset Formula $0x)=1-P(X>\lfloor x\rfloor)=1-(1-p)^{\max\{\lfloor x\rfloor,0\}}. +\] + +\end_inset + +The generating function is +\begin_inset Formula +\[ +G(z)\coloneqq\sum_{k\geq1}(1-p)^{k-1}pz^{k}=zp\sum_{k\geq0}(1-p)^{k}z^{k}=\frac{zp}{1-(1-p)z}=\frac{zp}{1-qz}, +\] + +\end_inset + +where +\begin_inset Formula $q\coloneqq1-p$ +\end_inset + +. + Then +\begin_inset Formula +\begin{align*} +G'(z) & =\frac{p-pqz+pqz}{(1-qz)^{2}}=\frac{p}{(1-qz)^{2}}, & G''(z) & =-\frac{2pq}{(1-qz)^{3}}, +\end{align*} + +\end_inset + +so the mean is +\begin_inset Formula +\[ +G'(1)=\frac{p}{(1-q)^{2}}=\frac{p}{p^{2}}=\frac{1}{p}, +\] + +\end_inset + +and the variance is +\begin_inset Formula +\[ +G''(1)+G'(1)-G'(1)^{2}=-\frac{2pq}{(1-q)^{3}}+\frac{1}{p}-\frac{1}{p^{2}}=\frac{2q}{p^{2}}+\frac{1}{p}-\frac{1}{p^{2}}=\frac{2q+p-1}{p^{2}}=\frac{q}{p^{2}}, +\] + +\end_inset + +so the standard deviation is +\begin_inset Formula $\frac{\sqrt{q}}{p}$ +\end_inset + +. +\end_layout + +\end_body +\end_document diff --git a/vol2/3.4.2.lyx b/vol2/3.4.2.lyx new file mode 100644 index 0000000..8d59cc5 --- /dev/null +++ b/vol2/3.4.2.lyx @@ -0,0 +1,537 @@ +#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[22] +\end_layout + +\end_inset + +The +\begin_inset Formula $(t+1)$ +\end_inset + +st item in Algorithm S is selected with probability +\begin_inset Formula $(n-m)/(N-t)$ +\end_inset + +, + not +\begin_inset Formula $n/N$ +\end_inset + +, + yet the text claims that the sample is unbiased; + thus each item should be selected with the +\emph on +same +\emph default + probability. + How can both of these statements be true? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +This is because +\begin_inset Formula $\frac{n-m}{N-t}$ +\end_inset + + appears as a +\emph on +conditioned +\emph default + probability, + where the condition depends on +\begin_inset Formula $t$ +\end_inset + +. + The actual probability of choosing the +\begin_inset Formula $(t+1)$ +\end_inset + +st element is +\begin_inset Formula +\[ +\sum_{m=0}^{t}P(\{m\text{ elements have been chosen between }1\text{ and }t\})\frac{n-m}{N-t}. +\] + +\end_inset + +Let +\begin_inset Formula $P_{mt}$ +\end_inset + + be the probability described with words inside this formula. + For +\begin_inset Formula $m>t$ +\end_inset + + or +\begin_inset Formula $m<0$ +\end_inset + +, + this probability is obviously 0, + and for +\begin_inset Formula $t=0$ +\end_inset + +, + +\begin_inset Formula $P_{00}=1$ +\end_inset + +. + For +\begin_inset Formula $t\geq1$ +\end_inset + + and +\begin_inset Formula $0\leq m\leq t$ +\end_inset + +, + +\begin_inset Formula +\[ +P_{mt}=P_{m(t-1)}\left(1-\frac{n-m}{N-t+1}\right)+P_{(m-1)(t-1)}\frac{n-m+1}{N-t+1}. +\] + +\end_inset + +Note that, + by this formula, + +\begin_inset Formula $P_{(n-1)t}=0$ +\end_inset + + always, + since the second term is 0 and the first term is a multiple of +\begin_inset Formula $P_{(n-1)(t-1)}$ +\end_inset + +, + which is 0 by induction since +\begin_inset Formula $P_{(n-1)(-1)}=0$ +\end_inset + +. + Then, + by induction in +\begin_inset Formula $m$ +\end_inset + +, + +\begin_inset Formula $P_{mt}=0$ +\end_inset + + for any +\begin_inset Formula $m>n$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Since the algorithm is said to be unbiased, + we would expect +\begin_inset Formula +\[ +P_{mt}=\frac{\binom{t}{m}\binom{N-t}{n-m}}{\binom{N}{n}}, +\] + +\end_inset + +that is, + the number of ways to choose +\begin_inset Formula $m$ +\end_inset + + elements among the first +\begin_inset Formula $t$ +\end_inset + + ones and +\begin_inset Formula $n-m$ +\end_inset + + elements among the rest, + divided by the total number of ways of choosing +\begin_inset Formula $n$ +\end_inset + + elements among +\begin_inset Formula $N$ +\end_inset + +. +\end_layout + +\begin_layout Standard +We prove this by induction. + For +\begin_inset Formula $t=0$ +\end_inset + + we have seen it already. + For +\begin_inset Formula $t>0$ +\end_inset + +, + if +\begin_inset Formula $m=0$ +\end_inset + +, +\begin_inset Formula +\[ +P_{0t}=P_{0(t-1)}\left(1-\frac{n}{N-t+1}\right)=\frac{\binom{N-t+1}{n}}{\binom{N}{n}}\frac{N-t-n+1}{N-t+1}=\frac{\binom{N-t}{n}}{\binom{N}{n}}, +\] + +\end_inset + +and if +\begin_inset Formula $m>0$ +\end_inset + +, +\begin_inset Formula +\begin{align*} +P_{mt} & =\frac{\binom{t-1}{m}\binom{N-t+1}{n-m}}{\binom{N}{n}}\frac{N-t-n+m+1}{N-t+1}+\frac{\binom{t-1}{m-1}\binom{N-t+1}{n-m+1}}{\binom{N}{n}}\frac{n-m+1}{N-t+1}=\\ + & =\frac{\binom{t-1}{m}\binom{N-t}{n-m}}{\binom{N}{n}}+\frac{\binom{t-1}{m-1}\binom{N-t}{n-m}}{\binom{N}{n}}=\frac{\binom{t}{m}\binom{N-t}{n-m}}{\binom{N}{n}}, +\end{align*} + +\end_inset + +where we make extensive use of Eq. + 1.2.6–(8). + Finally, + by Eq. + 1.2.6–(21), + the probability of choosing any given element is +\begin_inset Formula +\[ +\sum_{m=0}^{t}P_{mt}\frac{n-m}{N-t}=\frac{1}{\binom{N}{n}}\sum_{m=0}^{t}\binom{t}{m}\binom{N-1-t}{n-1-m}=\frac{\binom{N-1}{n-1}}{\binom{N}{n}}=\frac{\binom{N-1}{N-n}}{\binom{N}{N-n}}=\frac{n}{N}. +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc11[M25] +\end_layout + +\end_inset + +Let +\begin_inset Formula $p_{m}$ +\end_inset + + be the probability that exactly +\begin_inset Formula $m$ +\end_inset + + elements are put into the reservoir during the first pass of Algorithm R. + Determine the generating function +\begin_inset Formula $G(z)=\sum_{m}p_{m}z^{m}$ +\end_inset + +, + and find the mean and standard deviation. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Let +\begin_inset Formula $s_{k}\coloneqq P(\text{the }k\text{th element is copied to the reservoir})$ +\end_inset + +, + then +\begin_inset Formula $p_{m}$ +\end_inset + + is the sum across all subsets +\begin_inset Formula $\{x_{1},\dots,x_{m}\}\in\{1,\dots,N\}$ +\end_inset + + of +\begin_inset Formula $m$ +\end_inset + + elements, + +\begin_inset Formula $x_{1}<\dots dev: +\end_layout + +\begin_layout Plain Layout + + print( +\begin_inset Quotes eld +\end_inset + +FAIL +\begin_inset Quotes erd +\end_inset + +, + digs, + sb) +\end_layout + +\begin_layout Plain Layout + + return False +\end_layout + +\begin_layout Plain Layout + + return True +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\begin_layout Plain Layout + +for x in range(123456782019372800000, + 123456790000000000000): +\end_layout + +\begin_layout Plain Layout + + if israndom(str(x)[1:]): +\end_layout + +\begin_layout Plain Layout + + print(str(x)[1:]) +\end_layout + +\end_inset + + +\end_layout + +\end_body +\end_document diff --git a/vol2/3.6.lyx b/vol2/3.6.lyx new file mode 100644 index 0000000..8eaaa14 --- /dev/null +++ b/vol2/3.6.lyx @@ -0,0 +1,496 @@ +#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 +rexerc2[15] +\end_layout + +\end_inset + +some people have been afraid that computers will someday take over the world; + but they are reassured by the statement that a machine cannot do anything really new, + since it is only obeying the commands of its master, + the programmer. + Lady Lovelace wrote in 1844, + +\begin_inset Quotes eld +\end_inset + +The Analytical Engine has no pretensions to +\emph on +originate +\emph default + anything. + It can do +\emph on +whatever we know how to order it +\emph default + to perform. +\begin_inset Quotes erd +\end_inset + + Her statement has been elaborated further by many philosophers. + Discuss this topic, + with random number generators in mind. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +While it is true that a machine cannot do anything that a programmer doesn't tell it to do, + there are a number of caveats here. + First is that the programmer, + or their boss, + may not have other people's best interests in mind. + Another one is that what the programmer tells the machine to do is not the same thing as what they +\emph on +expects +\emph default + them to do; + the software may have bugs, + although the bugs are unlikely to make the computer take over the world. + Finally, + if a random number generator is being used, + the programmer is telling the machine to do one of a number of actions, + chosen with some given distribution, + without telling it which one to choose. + These actions are typically limited to a given scope, + and the programmer still controls the family of actions that the machine may take. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc11[M25] +\end_layout + +\end_inset + +Assuming that floating point arithmetic on numbers of type +\family typewriter +double +\family default + is properly rounded in the sense of Section 4.2.2 (hence exact when the values are suitably restricted), + convert the C routines +\emph on +ran_array +\emph default + and +\emph on +ran_start +\emph default + to similar programs that deliver double-precision random fractions in the range +\begin_inset Formula $[0..1)$ +\end_inset + +, + instead of 30-bit integers. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Technically this does the work: +\begin_inset listings +lstparams "language=C,numbers=left,basicstyle={\small\sffamily},breaklines=true" +inline false +status open + +\begin_layout Plain Layout + +#include +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\begin_layout Plain Layout + +static double ran_u[KK]; +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\begin_layout Plain Layout + +void ranf_array(double out[], + size_t n) +\end_layout + +\begin_layout Plain Layout + +{ +\end_layout + +\begin_layout Plain Layout + + size_t i, + j; +\end_layout + +\begin_layout Plain Layout + + assert(n >= KK); +\end_layout + +\begin_layout Plain Layout + + for (j = 0; + j < KK; + j++) +\end_layout + +\begin_layout Plain Layout + + out[j] = ran_u[j]; +\end_layout + +\begin_layout Plain Layout + + for (; + j < n; + j++) +\end_layout + +\begin_layout Plain Layout + + out[j] = fmod(1. + + out[j-KK] - out[j-LL], + 1.); +\end_layout + +\begin_layout Plain Layout + + for (i = 0; + i < LL; + i++, + j++) +\end_layout + +\begin_layout Plain Layout + + ran_u[i] = fmod(1. + + out[j-KK] - out[j-LL], + 1.); +\end_layout + +\begin_layout Plain Layout + + for (; + i < KK; + i++, + j++) +\end_layout + +\begin_layout Plain Layout + + ran_u[i] = fmod(1. + + out[j-KK] - ran_x[j-LL], + 1.); +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\begin_layout Plain Layout + +void ranf_start(long seed) +\end_layout + +\begin_layout Plain Layout + +{ +\end_layout + +\begin_layout Plain Layout + + ranf_start(seed); +\end_layout + +\begin_layout Plain Layout + + for (size_t i = 0; + i < KK; + i++) +\end_layout + +\begin_layout Plain Layout + + ran_u[i] = (double)ran_x[i] / MM; +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc12[M21] +\end_layout + +\end_inset + +What random number generator would be suitable for a minicomputer that does arithmetic only on integers in the range +\begin_inset Formula $[-32768..32767]$ +\end_inset + +? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +We could use one of the generators with very large moduli from exercise 3.2.1.1–14. + We could also use running generators like the one in the text +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc15[25] +\end_layout + +\end_inset + +Write C code that makes it convenient to generate the random integers obtained from +\emph on +ran_array +\emph default + by discarding all but the first 100 of every 1009 elements, + as recommended in the text. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset listings +lstparams "language=C,numbers=left,basicstyle={\normalsize\sffamily},breaklines=true" +inline false +status open + +\begin_layout Plain Layout + +long next() +\end_layout + +\begin_layout Plain Layout + +{ +\end_layout + +\begin_layout Plain Layout + + static long buf[1009], + next = 100; +\end_layout + +\begin_layout Plain Layout + + if (next == 100) { +\end_layout + +\begin_layout Plain Layout + + ran_array(buf, + sizeof(buf) / sizeof(buf[0])); +\end_layout + +\begin_layout Plain Layout + + next = 0; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + return buf[next++]; +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\end_inset + + +\end_layout + +\end_body +\end_document diff --git a/vol2/4.1.lyx b/vol2/4.1.lyx new file mode 100644 index 0000000..b68ec0b --- /dev/null +++ b/vol2/4.1.lyx @@ -0,0 +1,1922 @@ +#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 +rexerc2[24] +\end_layout + +\end_inset + +Consider the following four number systems: +\end_layout + +\begin_layout Enumerate +binary (signed magnitude); +\end_layout + +\begin_layout Enumerate +negabinary (radix +\begin_inset Formula $-2$ +\end_inset + +); +\end_layout + +\begin_layout Enumerate +balanced ternary; + and +\end_layout + +\begin_layout Enumerate +radix +\begin_inset Formula $b=\frac{1}{10}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Use each of these four number systems to express each of the following three numbers: +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $-49$ +\end_inset + +; +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $-3\frac{1}{7}$ +\end_inset + + (show the repeating cycle); +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $\pi$ +\end_inset + + (to a few significant figures). +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Enumerate +\begin_inset Formula $-49\to-110001$ +\end_inset + +. + Multiplying by 2, + +\begin_inset Formula $\frac{1}{7}\to\frac{2}{7}\to\frac{4}{7}\to1+\frac{1}{7}$ +\end_inset + +, + so +\begin_inset Formula $-3\frac{1}{7}\to-11.\overbrace{001}$ +\end_inset + +. + Finally, + +\begin_inset Formula $\pi\to11.00100100001111...$ +\end_inset + + +\end_layout + +\begin_layout Enumerate +The trick is to express the number in binary and, + for the odd positions (the ones where +\begin_inset Formula $(-2)^{k}$ +\end_inset + + is negative), + add 1 to the part of the number on the right, + because we are subtracting +\begin_inset Formula $2^{k}$ +\end_inset + + instead of adding so we compensate for that. + For negative numbers, + we represent them in two's complement before this change, + effectively adding +\begin_inset Formula $2^{M}$ +\end_inset + + for some large +\begin_inset Formula $M$ +\end_inset + +, + and after it we drop that upper bit to subtract +\begin_inset Formula $2^{M}$ +\end_inset + +. + Thus +\begin_inset Formula $-49\to...111001111\to11010011$ +\end_inset + +, + +\begin_inset Formula $-3\frac{1}{7}\to...1100.\overbrace{110110}\to1101.\overbrace{001011}$ +\end_inset + +, + +\begin_inset Formula $\pi\to111.01100100010000...$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +We proceed as in the text: + +\begin_inset Formula +\begin{align*} +-49 & \to-1211\to...11102200\to\overline{1}11\overline{1}\overline{1};\\ +-3\frac{1}{7} & \to-10.\overbrace{010212}\to\dots1101.\overbrace{100122}\to\overline{1}0.\overbrace{0\overline{1}\overline{1}011};\\ +\pi & \to10.010211012\dots\to...1121.122022201\dots\to10.011\overline{1}111\overline{1}0\dots. +\end{align*} + +\end_inset + + +\end_layout + +\begin_layout Enumerate +This is like the decimal system but backwards, + so +\begin_inset Formula $-49\to-9.4$ +\end_inset + +, + +\begin_inset Formula $-3\frac{1}{7}\to-\overbrace{758241}3$ +\end_inset + +, + +\begin_inset Formula $\pi\to...51413$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc5[00] +\end_layout + +\end_inset + +Explain why a negative integer in nines' complement notation has a representation in ten's complement notation that is always one greater, + if the representations are regarded as positive. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +Ten's complement of a negative number +\begin_inset Formula $s$ +\end_inset + + is +\begin_inset Formula $10^{M}+s$ +\end_inset + +, + for a suitably large integer +\begin_inset Formula $M$ +\end_inset + +, + while nines' complement is +\begin_inset Formula $(10^{M}-1)+s$ +\end_inset + +, + so the ten's complement is one greater. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +exerc8[M10] +\end_layout + +\end_inset + +Prove Eq. + (5). +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +The part at the left is +\begin_inset Formula $\sum_{j}a_{j}b^{j}$ +\end_inset + +, + while the part at the right is +\begin_inset Formula $\sum_{j}A_{j}b^{kj}$ +\end_inset + +, + but +\begin_inset Formula $A_{j}=\sum_{i=0}^{k-1}a_{kj+i}b^{i}$ +\end_inset + +, + so this is +\begin_inset Formula +\[ +\sum_{j}A_{j}b^{kj}=\sum_{j}\sum_{i=0}^{k-1}(a_{kj+i}b^{i})b^{kj}=\sum_{j}\sum_{i=0}^{k-1}(a_{kj+i}b^{kj+i})=\sum_{j}a_{j}b^{j}. +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc9[15] +\end_layout + +\end_inset + +Change the following +\emph on +octal +\emph default + numbers to +\emph on +hexadecimal +\emph default + notation, + using the hexadecimal digits +\family typewriter +0 +\family default +, + +\family typewriter +1 +\family default +, + ..., + +\family typewriter +9 +\family default +, + +\family typewriter +A +\family default +, + +\family typewriter +B +\family default +, + +\family typewriter +C +\family default +, + +\family typewriter +D +\family default +, + +\family typewriter +E +\family default +, + +\family typewriter +F +\family default +: + 12; + 5655; + 2550276; + 76545336; + 3726755. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +We use Eq. + (5) with base 2. +\end_layout + +\begin_layout Standard +\align center +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\begin_layout Plain Layout +Octal +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Binary +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Hexadecimal +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +12 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1 010 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +A +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +5655 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +101 110 101 101 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +BAD +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +2550276 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +10 101 101 000 010 111 110 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +AD0BE +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +76545336 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +111 110 101 100 101 011 011 110 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +FACADE +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +3726755 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +11 111 010 110 111 101 101 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +FADED +\end_layout + +\end_inset + + + + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Note Comment +status open + +\begin_layout Plain Layout +Is this what academics do when they get bored? +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc13[M21] +\end_layout + +\end_inset + +In the decimal system there are some numbers with two infinite decimal expansions; + for example, + +\begin_inset Formula $2.3599999...=2.3600000...$ +\end_inset + +. + Does the +\emph on +negadecimal +\emph default + (base +\begin_inset Formula $-10$ +\end_inset + +) system have unique expansions, + or are there real numbers with two different infinite expansions in this base also? +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +answer +\end_layout + +\end_inset + +There are real numbers with two different infinite expansions: + +\begin_inset Formula +\[ +\tfrac{1}{11}=0.090909...=(0.090909...)_{-10}=(1.909090...)_{-10}. +\] + +\end_inset + +Effectively, + +\begin_inset Formula $(0.090909...)_{-10}=\sum_{k\geq1}9\cdot(-10)^{-2k}=9\sum_{k\geq1}100^{-k}=9\frac{\frac{1}{100}}{\frac{99}{100}}=\frac{1}{11}$ +\end_inset + +, + but +\begin_inset Formula $(1.909090...)_{-10}=1+\sum_{k\geq1}9\cdot(-10)^{-2k+1}=1-90\sum_{k\geq1}100^{-k}=1-90\frac{1}{99}=1-\frac{10}{11}=\frac{1}{11}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +rexerc19[23] +\end_layout + +\end_inset + +(David W. + Matula.) Let +\begin_inset Formula $D$ +\end_inset + + be a set of +\begin_inset Formula $b$ +\end_inset + + integers, + containing exactly one solution to the congruence +\begin_inset Formula $x\equiv j\pmod b$ +\end_inset + + for +\begin_inset Formula $0\leq j0$ +\end_inset + +, + then all numbers in +\begin_inset Formula $D$ +\end_inset + + are negative, + but the integers between +\begin_inset Formula $l$ +\end_inset + + and +\begin_inset Formula $u$ +\end_inset + + are positive so they couldn't be represented in the given form, +\begin_inset Formula $\#$ +\end_inset + + and a similar thing would happen if +\begin_inset Formula $u<0$ +\end_inset + +. + Now, + in the algorithm above, + +\begin_inset Formula $q-k=\lfloor\frac{m}{b}\rfloor-k=\frac{m-r}{b}-\frac{x-r}{b}=\frac{m-x}{b}$ +\end_inset + +. + With this, + if +\begin_inset Formula $m>u$ +\end_inset + +, + then +\begin_inset Formula $m(b-1)>-\min D$ +\end_inset + +, + but and therefore +\begin_inset Formula +\[ +m-(q-k)=m-\frac{m-x}{b}=\frac{m(b-1)+x}{b}>\frac{-\min D+\min D}{b}=0, +\] + +\end_inset + +so +\begin_inset Formula $q-km-\frac{\max D}{b}\geq m+l, +\] + +\end_inset + +so +\begin_inset Formula $q-k\geq l$ +\end_inset + +. + This means that, + on each step, + +\begin_inset Formula $m$ +\end_inset + + is smaller by at least 1, + but it doesn't become smaller than +\begin_inset Formula $l$ +\end_inset + +, + so it eventually reaches the interval +\begin_inset Formula $[l,u]$ +\end_inset + + in at most +\begin_inset Formula $|m-u|$ +\end_inset + + steps. + And if +\begin_inset Formula $mm$ +\end_inset + +, + and +\begin_inset Formula +\[ +m+(q-k)=\frac{m(b+1)-x}{b}0$ +\end_inset + +, + we take +\begin_inset Formula $k\in\mathbb{N}$ +\end_inset + + such that +\begin_inset Formula $|2^{k}-n|$ +\end_inset + + is minimum, + write a 1 at position +\begin_inset Formula $k$ +\end_inset + +, + and then write +\begin_inset Formula $n-2^{k}$ +\end_inset + + on the +\begin_inset Formula $k$ +\end_inset + + positions to the right. + If +\begin_inset Formula $n<0$ +\end_inset + +, + we do the same except that first we write +\begin_inset Formula $\overline{1}$ +\end_inset + + instead of 1. +\end_layout + +\begin_layout Standard +Now we prove that this in fact results in the representation fewest number of nonzero digits. + We only need to prove it for positive +\begin_inset Formula $n$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Now, + if +\begin_inset Formula $n=2^{k}$ +\end_inset + + or +\begin_inset Formula $3\cdot2^{k}$ +\end_inset + + for some +\begin_inset Formula $k\in\mathbb{N}$ +\end_inset + +, + the statement is trivial. + Otherwise, + if +\begin_inset Formula $2^{k}2^{k-1}$ +\end_inset + +, + +\begin_inset Formula $t$ +\end_inset + + would need to have its most significant digit in position +\begin_inset Formula $k$ +\end_inset + + or +\begin_inset Formula $k-1$ +\end_inset + +, + but any representation of +\begin_inset Formula $t$ +\end_inset + + that starts at position +\begin_inset Formula $k$ +\end_inset + + can be converted into one of +\begin_inset Formula $2^{k}-n$ +\end_inset + + by removing the 1 at that position, + and any one starting at position +\begin_inset Formula $k-1$ +\end_inset + + can be converted into one of +\begin_inset Formula $2^{k}-n$ +\end_inset + + by swapping the sign in that position, + so in general +\begin_inset Formula $\sigma(t)=\sigma(2^{k+1}-n)\geq\sigma(2^{k}-n)=\sigma(n-2^{k})$ +\end_inset + +. +\end_layout + +\begin_layout Standard +A similar argument shows that, + if +\begin_inset Formula $n>3\cdot2^{k-1}$ +\end_inset + +, + then +\begin_inset Formula $\sigma(n-2^{k})\geq\sigma(2^{k+1}-n)$ +\end_inset + +. +\end_layout + +\end_body +\end_document diff --git a/vol2/index.lyx b/vol2/index.lyx new file mode 100644 index 0000000..816a76b --- /dev/null +++ b/vol2/index.lyx @@ -0,0 +1,1394 @@ +#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} + +\makeatletter +\newcommand{\biggg}{\bBigg@\thr@@} +\newcommand{\Biggg}{\bBigg@{3.5}} +\makeatother +\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 true +\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 10 +\spacing single +\use_hyperref true +\pdf_bookmarks true +\pdf_bookmarksnumbered false +\pdf_bookmarksopen false +\pdf_bookmarksopenlevel 1 +\pdf_breaklinks false +\pdf_pdfborder false +\pdf_colorlinks false +\pdf_backref false +\pdf_pdfusetitle true +\papersize custom +\use_geometry true +\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 +\paperwidth 198mm +\paperheight 297mm +\leftmargin 23mm +\topmargin 33mm +\rightmargin 43mm +\bottommargin 66mm +\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 2 +\paperpagestyle fancy +\tablestyle default +\listings_params "basicstyle={\ttfamily}" +\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 Title +Exercises on +\emph on +The Art Of Computer Programming +\emph default + +\begin_inset Newline newline +\end_inset + + +\size larger +Volume 2: + Seminumerical Algorithms +\begin_inset Newline newline +\end_inset + +Third Edition +\end_layout + +\begin_layout Author +Juan Marín Noguera +\end_layout + +\begin_layout Standard +\begin_inset CommandInset toc +LatexCommand tableofcontents + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +Equivalent page size can be obtained with the following layouts (in mm): +\end_layout + +\begin_layout Plain Layout +\begin_inset Tabular + + + + + + + + + + + +\begin_inset Text + +\begin_layout Plain Layout +Height +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Width +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Top +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Bottom +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Inner +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Outer +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Recommended headers +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +297 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +198 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +33 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +66 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +23 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +43 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Fancy +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +210 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +140 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +4 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +8 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +3 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +5 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Empty +\end_layout + +\end_inset + + + + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +The first one follows Tschichold's canon except for +\begin_inset Formula $\unit[1]{mm}$ +\end_inset + + given to the inner margin from the outer one to account for a minimal folding. + The golden ratio resulted in way too narrow pages on A5 paper. +\end_layout + +\begin_layout Plain Layout +Proposed notation for in-progress: +\end_layout + +\begin_layout Plain Layout +\begin_inset listings +inline false +status open + +\begin_layout Plain Layout + +atom = ( +\begin_inset Quotes eld +\end_inset + +A +\begin_inset Quotes erd +\end_inset + +| +\begin_inset Quotes erd +\end_inset + +R +\begin_inset Quotes erd +\end_inset + +) ?( +\begin_inset Quotes eld +\end_inset + +B +\begin_inset Quotes erd +\end_inset + +| +\begin_inset Quotes erd +\end_inset + +M +\begin_inset Quotes erd +\end_inset + +) (( +\begin_inset Quotes eld +\end_inset + +0 +\begin_inset Quotes erd +\end_inset + +.. +\begin_inset Quotes erd +\end_inset + +4 +\begin_inset Quotes erd +\end_inset + +) ( +\begin_inset Quotes eld +\end_inset + +0 +\begin_inset Quotes erd +\end_inset + +.. +\begin_inset Quotes erd +\end_inset + +9 +\begin_inset Quotes erd +\end_inset + +) / +\begin_inset Quotes eld +\end_inset + +@ +\begin_inset Quotes erd +\end_inset + +) / 1DIGIT *DIGIT / *1(1DIGIT *DIGIT) +\begin_inset Quotes eld +\end_inset + +.. +\begin_inset Quotes erd +\end_inset + + *1(1DIGIT *DIGIT) +\end_layout + +\begin_layout Plain Layout + +base = atom / +\begin_inset Quotes eld +\end_inset + +( +\begin_inset Quotes eld +\end_inset + + progress +\begin_inset Quotes eld +\end_inset + +) +\begin_inset Quotes erd +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +intersection = atom / intersection +\begin_inset Quotes eld +\end_inset + +* +\begin_inset Quotes erd +\end_inset + + atom +\end_layout + +\begin_layout Plain Layout + +progress = intersection / progress ( +\begin_inset Quotes eld +\end_inset + ++ +\begin_inset Quotes erd +\end_inset + +/ +\begin_inset Quotes erd +\end_inset + +- +\begin_inset Quotes erd +\end_inset + +) intersection +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +An +\family typewriter +atom +\family default + represents all/recommended exercises, + optionally excluding M or HM/excluding HM, + and up to the given difficulty level/all difficulty levels, + or else a single exercise with the given number, + or a range of exercises (both ends inclusive). + Then +\family typewriter +* +\family default + is used for intersection, + +\family typewriter ++ +\family default + for union, + and +\family typewriter +- +\family default + for set difference. +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +setcounter{chapter}{2} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Chapter +Random Numbers +\end_layout + +\begin_layout Section +Introduction +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.1.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25+16 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Generating Uniform Random Numbers +\end_layout + +\begin_layout Subsection +The Linear Congruential Method +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.2.1.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Choice of modulus +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.2.1.1.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Choice of multiplier +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.2.1.2.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Potency +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.2.1.3.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Other Methods +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.2.2.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Statistical Tests +\end_layout + +\begin_layout Subsection +General Test Procedures for Studying Random Data +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.3.1.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Empirical Tests +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.3.2.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Theoretical Tests +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.3.3.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +The Spectral Test +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.3.4.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Other Types of Random Quantities +\end_layout + +\begin_layout Subsection +Numerical Distributions +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.4.1.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Random Sampling and Shuffling +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.4.2.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25-16 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +What Is a Random Sequence? +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.5.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Summary +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "3.6.lyx" +literal "false" + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\family typewriter +A10+R25 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Chapter +Arithmetic +\end_layout + +\begin_layout Section +Positional Number Systems +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "4.1.lyx" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Section +Floating Point Arithmetic +\end_layout + +\begin_layout Subsection +Single-Precision Calculations +\end_layout + +\begin_layout Subsection +Accuracy of Floating Point Arithmetic +\end_layout + +\begin_layout Subsection +Double-Precision Calculations +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +7+0; + 5 (0:28) -> 3d, + -1/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Distribution of Floating Point Numbers +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +10+2; + 5, + 13, + 17 (0:58) -> 5d +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Multiple-Precision Arithmetic +\end_layout + +\begin_layout Subsection +The Classical Algorithms +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +16+4; + 6, + 9, + 11, + 14, + 16, + 19, + 21, + 22, + 30, + 37, + 43 (2:58) -> 12d, + -2/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Modular Arithmetic +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +8+1; + 5, + 7, + 12, + 13 (1:13) -> 4d +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +How Fast Can We Multiply? +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +22+3; + 16, + 19 (0:56) -> 10d, + -2/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Radix Conversion +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +9+2; + 1, + 3, + 12, + 13, + 19 (2:22) -> 8d, + -2/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Rational Arithmetic +\end_layout + +\begin_layout Subsection +Fractions +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +3+1; + 5, + 6, + 8 (0:42) -> 2d, + -2/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +The Greatest Common Divisor +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +19+4; + 8, + 10, + 14, + 16, + 17, + 18, + 23, + 40 (3:19) -> 13d, + -1/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Analysis of Euclid's Algorithm +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +17+6; + 1, + 17, + 39, + 50 (1:42) -> 9d, + -2/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Factoring into Primes +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +32+6; + 1, + 8, + 18, + 19, + 24, + 26, + 32, + 35 (3:17) -> 17d +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Polynomial Arithmetic +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +2+0; + 1, + 4, + 5 (0:31) -> 2d, + -1/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Division of Polynomials +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +15+4; + 1, + 3, + 7, + 8, + 12, + 16, + 18 (2:08) -> 9d, + -1/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Factorization of Polynomials +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +17+5; + 1, + 2, + 10, + 12, + 18, + 22, + 34, + 40 (3:22) -> 13d, + -2/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Evaluation of Powers +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +21+4; + 3, + 5, + 9, + 10, + 12, + 24, + 26, + 36, + 39, + 40 (3:37) -> 14d, + -2/3 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Evaluation of Polynomials +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +29+10; + 2, + 19, + 20, + 24, + 26, + 29, + 33, + 35, + 44, + 45, + 49, + 51, + 70 (5:24) -> 20d +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Manipulation of Power Series +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +8+5; + 1, + 4, + 5, + 6, + 8, + 11, + 17 (1:59) -> 7d, + -1/3 +\end_layout + +\end_inset + + +\end_layout + +\end_body +\end_document -- cgit v1.2.3