path: root/3.6.lyx

#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