diff options
Diffstat (limited to 'vol2/3.6.lyx')
| -rw-r--r-- | vol2/3.6.lyx | 496 |
1 files changed, 496 insertions, 0 deletions
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 <math.h> +\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 |