📄 node117.html
字号:
<html><!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>10.1 Sequential Random Numbers</TITLE>
</HEAD>
<BODY>
<meta name="description" value="10.1 Sequential Random Numbers">
<meta name="keywords" value="book">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
<BR> <HR><a href="msgs0.htm#2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#2"><img ALIGN=MIDDLE src="asm_color_tiny.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/asm_color_tiny.gif" alt="[DBPP]"></a> <A NAME=tex2html3393 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html"><IMG ALIGN=MIDDLE ALT="previous" SRC="previous_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/previous_motif.gif"></A> <A NAME=tex2html3401 HREF="node118.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node118.html"><IMG ALIGN=MIDDLE ALT="next" SRC="next_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/next_motif.gif"></A> <A NAME=tex2html3399 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html"><IMG ALIGN=MIDDLE ALT="up" SRC="up_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/up_motif.gif"></A> <A NAME=tex2html3403 HREF="node1.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node1.html"><IMG ALIGN=MIDDLE ALT="contents" SRC="contents_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/contents_motif.gif"></A> <A NAME=tex2html3404 HREF="node133.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node133.html"><IMG ALIGN=MIDDLE ALT="index" SRC="index_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/index_motif.gif"></A> <a href="msgs0.htm#3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#3"><img ALIGN=MIDDLE src="search_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/search_motif.gif" alt="[Search]"></a> <BR>
<B> Next:</B> <A NAME=tex2html3402 HREF="node118.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node118.html">10.2 Parallel Random Numbers</A>
<B>Up:</B> <A NAME=tex2html3400 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html">10 Random Numbers</A>
<B> Previous:</B> <A NAME=tex2html3394 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html">10 Random Numbers</A>
<BR><HR><P>
<H1><A NAME=SECTION04210000000000000000>10.1 Sequential Random Numbers</A></H1>
<P>
<A NAME=secrandone> </A>
<P>
<A NAME=14603> </A>
Although the casinos at Monte Carlo are, one hopes, based on random
phenomena, true random numbers are rarely used in computing. Not only
would such numbers be difficult to generate reliably, but also the lack of
reproducibility would make the validation of programs that use them
extremely difficult. Instead, computers invariably use <em>
pseudo-random
</em> numbers: finite sequences generated by a
deterministic process but indistinguishable, by some set of
statistical tests, from a random sequence. (In the following, we use
the term random to mean pseudo-random.) The statistical
methods used to validate random sequences are an important
topic of research, but beyond the scope of this book. See the chapter
notes for further reading on this subject.
<P>
Methods for generating a <em> sequence
</em> of random numbers have
been extensively studied and are well understood. A function called a
<em> generator
</em> is defined that, when applied to a number, yields
the next number in the sequence. For example, the <em> linear
<A NAME=14607> </A>
congruential
</em> generators considered in this chapter have
the general form
<P><A NAME=eqrand> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1067.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1067.gif"><P>
where <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1068.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1068.gif"> is the <em> k</em>
th element of the sequence and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1069.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1069.gif">,
<em> a</em>
, <em> c</em>
, and <em> m</em>
define the generator. Random numbers in the
range [0,1] are then obtained by dividing <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1070.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1070.gif"> by <em> m</em>
.
<P>
As numbers are taken from a finite set (for example, integers between
1 and <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1071.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1071.gif">), any generator will eventually repeat itself. The
<A NAME=14619> </A>
length of the repeated cycle is called the <em> period
</em> of the
generator. A good generator is one with a long period and no
discernible correlation between elements of the sequence.
<P>
The parameters <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1072.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1072.gif">, <em> a</em>
, <em> c</em>
, and <em> m</em>
in the linear
congruential generator are chosen to make the sequence look as random
as possible. Common choices for these values are
<P><A NAME=eqrand1> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1073.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1073.gif"><P>
This generator has period <em> m-1</em>
, that is, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1074.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1074.gif"> for <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1075.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1075.gif">. Other common choices are
<P><A NAME=eqrand2> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1076.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1076.gif"><P>
in which case the period of the generator is <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1077.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1077.gif">. A
typical choice for <em> m</em>
in this case is the word size of the
machine on which we are executing. See the references in the chapter
notes for sources of appropriate values for <em> a</em>
, <em> c</em>
, and
<em> m</em>
.
<P>
A fundamental property of Equation <A HREF="node117.html#eqrand" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node117.html#eqrand">10.1</A> is that if <em> c=0</em>
,
then
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1078.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1078.gif"><P>
That is, the <em> (k+n)</em>
th element of the sequence is related to the
<em> k</em>
th in the same way as is the <em> (k+1)</em>
th, albeit with a
different value for <em> a</em>
. We shall exploit this property when
developing parallel generators.
<P>
<BR> <HR><a href="msgs0.htm#2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#2"><img ALIGN=MIDDLE src="asm_color_tiny.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/asm_color_tiny.gif" alt="[DBPP]"></a> <A NAME=tex2html3393 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html"><IMG ALIGN=MIDDLE ALT="previous" SRC="previous_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/previous_motif.gif"></A> <A NAME=tex2html3401 HREF="node118.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node118.html"><IMG ALIGN=MIDDLE ALT="next" SRC="next_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/next_motif.gif"></A> <A NAME=tex2html3399 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html"><IMG ALIGN=MIDDLE ALT="up" SRC="up_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/up_motif.gif"></A> <A NAME=tex2html3403 HREF="node1.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node1.html"><IMG ALIGN=MIDDLE ALT="contents" SRC="contents_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/contents_motif.gif"></A> <A NAME=tex2html3404 HREF="node133.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node133.html"><IMG ALIGN=MIDDLE ALT="index" SRC="index_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/index_motif.gif"></A> <a href="msgs0.htm#3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#3"><img ALIGN=MIDDLE src="search_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/search_motif.gif" alt="[Search]"></a> <BR>
<B> Next:</B> <A NAME=tex2html3402 HREF="node118.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node118.html">10.2 Parallel Random Numbers</A>
<B>Up:</B> <A NAME=tex2html3400 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html">10 Random Numbers</A>
<B> Previous:</B> <A NAME=tex2html3394 HREF="node116.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node116.html">10 Random Numbers</A>
<BR><HR><P>
<P><ADDRESS>
<I>© Copyright 1995 by <A href="msgs0.htm#6" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#6">Ian Foster</a></I>
</ADDRESS>
</BODY>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -