page465.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 113 行
HTML
113 行
<HTML><HEAD><TITLE>Generating Random Numbers</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6525" HREF="page466.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6523" HREF="page464.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6517" HREF="page464.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6527" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014510000000000000000">Generating Random Numbers</A></H2><A NAME="secalgsrng"> </A><P>In this section we consider the problemof generating a sequence of <em>random numbers</em><A NAME=33742> </A>on a computer.Specifically, we desire an infinite sequenceof statistically independent random numbersuniformly distributed between zero and one.In practice,because the sequence is generated algorithmicallyusing finite-precision arithmetic,it is neither infinite nor truly random.Instead, we say that an algorithm is ``good enough''if the sequence it generates satisfies almost anystatistical test of randomness.Such a sequence is said to be <em>pseudorandom</em><A NAME=33744> </A>.<P>The most common algorithms for generating pseudorandom numbersare based on the <em>linear congruential</em><A NAME=33746> </A><A NAME=33747> </A>random number generator invented by Lehmer.Given a positive integer <I>m</I> called the <em>modulus</em><A NAME=33749> </A>and an initial <em>seed</em><A NAME=33751> </A> value <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68501" SRC="img1887.gif" > ( <IMG WIDTH=84 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68503" SRC="img1888.gif" >),Lehmer's algorithm computes a sequenceof integers between 0 and <I>m</I>-1.The elements of the sequence are given by<P><A NAME="eqnalgslcrng"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation33752" SRC="img1889.gif" ><P>where <I>a</I> and <I>c</I> are carefully chosen integerssuch that <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68511" SRC="img1890.gif" > and <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68513" SRC="img1891.gif" >.<P>For example, the parameters <I>a</I>=13, <I>c</I>=1, <I>m</I>=16, and <IMG WIDTH=50 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68521" SRC="img1892.gif" >produce the sequence<P> <IMG WIDTH=411 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath68489" SRC="img1893.gif" ><P>The first <I>m</I> elements of this sequence are distinctand appear to have been drawn at random from the set <IMG WIDTH=99 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68525" SRC="img1894.gif" >.However since <IMG WIDTH=66 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68527" SRC="img1895.gif" > the sequence is cyclicwith <em>period</em><A NAME=33757> </A> <I>m</I>.<P>Notice that the elements of the sequence alternate betweenodd and even integers.This follows directly from Equation <A HREF="page465.html#eqnalgslcrng"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and the factthat <I>m</I>=16 is a multiple of 2.Similar patterns arise when we consider the elementsas binary numbers:<P> <IMG WIDTH=434 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath68490" SRC="img1896.gif" ><P>The least significant two bits are cyclic with period fourand the least significant three bits are cycle with period eight!(These patterns arise because <I>m</I>=16 is also a multiple of 4 and 8).The existence of such patterns make the sequence <em>less random</em>.This suggests that the best choice for the modulus <I>m</I> is a prime number.<P>Not all parameter values result in a period of <I>m</I>.For example, changing the multiplier <I>a</I> to 11 produces the sequence<P> <IMG WIDTH=335 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath68491" SRC="img1897.gif" ><P>the period of which is only <I>m</I>/2.In general because each subsequent element of the sequenceis determined solely from its predecessorand because there are <I>m</I> possible values,the longest possible period is <I>m</I>.Such a generator is called a <em>full period</em> generator.<P>In practice the <em>increment</em><A NAME=33762> </A> <I>c</I> is often set to zero.In this case, Equation <A HREF="page465.html#eqnalgslcrng"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> becomes<P><A NAME="eqnalgsmcrng"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation33764" SRC="img1898.gif" ><P>This is called a <em>multiplicative linear congruential</em><A NAME=33769> </A><A NAME=33770> </A>random number generator.(For <IMG WIDTH=37 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68551" SRC="img1899.gif" > it is called a <em>mixed linear congruential</em><A NAME=33772> </A><A NAME=33773> </A> generator).<P>In order to prevent the sequence generated by Equation <A HREF="page465.html#eqnalgsmcrng"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>from collapsing to zero,the modulus <I>m</I> must be prime and <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68501" SRC="img1887.gif" > cannot be zero.For example, the parameters <I>a</I>=6, <I>m</I>=13, and <IMG WIDTH=49 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68561" SRC="img1900.gif" >produce the sequence<P> <IMG WIDTH=368 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath68492" SRC="img1901.gif" ><P>Notice that the first 12 elements of the sequence are distinct.Since a multiplicative congruential generator can never produce a zero,the maximum possible period is <I>m</I>-1.Therefore, this is a full period generator.<P>As the final step of the process,the elements of the sequence are <em>normalized</em><A NAME=33776> </A>by division by the modulus:<P> <IMG WIDTH=290 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath68493" SRC="img1902.gif" ><P>In so doing, we obtain a sequence of random numbersthat fall between zero and one.Specifically, a mixed congruential generator ( <IMG WIDTH=37 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68551" SRC="img1899.gif" >)produces numbers in the interval [0,1),whereas a multiplicative congruential generator (<I>c</I>=0)produces numbers in the interval (0,1).<P><BR> <HR><UL> <LI> <A NAME="tex2html6528" HREF="page466.html#SECTION0014511000000000000000">The Minimal Standard Random Number Generator</A><LI> <A NAME="tex2html6529" HREF="page467.html#SECTION0014512000000000000000">Implementation</A></UL><HR><A NAME="tex2html6525" HREF="page466.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6523" HREF="page464.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6517" HREF="page464.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6527" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?