📄 page466.html
字号:
<HTML><HEAD><TITLE>The Minimal Standard Random Number Generator</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="tex2html6538" HREF="page467.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6536" HREF="page465.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6530" HREF="page465.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6540" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0014511000000000000000">The Minimal Standard Random Number Generator</A></H3><P>A great deal of research has gone into the question of findingan appropriate set of parameters to use in Lehmer's algorithm.A good generator has the following characteristics:<UL><LI> It is a <em>full period</em> generator.<LI> The generated sequence passes statistical tests of <em>randomness</em>.<LI> The generator can be implemented efficiently using 32-bit integer arithmetic.</UL><P>The choice of modulus depends on the arithmetic precision usedto implement the algorithm.A signed 32-bit integer can represent values between <IMG WIDTH=31 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline68573" SRC="img1903.gif" > and <IMG WIDTH=47 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61955" SRC="img874.gif" >.Fortunately, the quantity <IMG WIDTH=158 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline68577" SRC="img1904.gif" >is a prime number!<A NAME="tex2html844" HREF="footnode.html#33980"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>Therefore, it is an excellent choice for the modulus <I>m</I>.<P>Because Equation <A HREF="page465.html#eqnalgsmcrng"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is slightly simpler than Equation <A HREF="page465.html#eqnalgslcrng"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,we choose to implement a multiplicative congruential generator (<I>c</I>=0).The choice of a suitable multiplier is more difficult.However, a popular choice is <IMG WIDTH=73 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline68585" SRC="img1906.gif" >because it satisfies all three criteria given above:It results in a full period random number generator;the generated sequence passes a wide variety of statistical testsfor randomness; andit is possible to compute Equation <A HREF="page465.html#eqnalgsmcrng"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>using 32-bit arithmetic without overflow.<P>The algorithm is derived as follows:First, let <IMG WIDTH=78 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68587" SRC="img1907.gif" > and <IMG WIDTH=90 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline68589" SRC="img1908.gif" >.<A NAME="tex2html845" HREF="footnode.html#33790"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>In this case, <IMG WIDTH=80 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68595" SRC="img1911.gif" >, <IMG WIDTH=64 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline68597" SRC="img1912.gif" >, and <I>r</I><I><</I><I>q</I>.<P>Next, we rewrite Equation <A HREF="page465.html#eqnalgsmcrng"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> as follows:<P> <IMG WIDTH=500 HEIGHT=63 ALIGN=BOTTOM ALT="eqnarray33792" SRC="img1913.gif" ><P>This somewhat complicated formula can be simplifiedif we let <IMG WIDTH=200 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68601" SRC="img1914.gif" >:<P> <IMG WIDTH=500 HEIGHT=64 ALIGN=BOTTOM ALT="eqnarray33795" SRC="img1915.gif" ><P><P>Finally, we make use of the fact that <I>m</I>=<I>aq</I>-<I>r</I> to get<P><A NAME="eqnalgsschrage"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation33798" SRC="img1916.gif" ><P><P>Equation <A HREF="page466.html#eqnalgsschrage"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> has several nice properties:Both <IMG WIDTH=86 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68605" SRC="img1917.gif" > and <IMG WIDTH=72 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68607" SRC="img1918.gif" >are positive integers between 0 and <I>m</I>-1.Therefore the difference <IMG WIDTH=169 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68613" SRC="img1919.gif" >can be represented using a signed 32-bit integer without overflow.Finally, <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68615" SRC="img1920.gif" > is either a zero or a one.Specifically, it is zero when the sum of the first two termsin Equation <A HREF="page466.html#eqnalgsschrage"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is positive and it is one when the sum is negative.As a result, it is not necessary to compute <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68615" SRC="img1920.gif" >--a simple test suffices to determine whether the third term is 0 or <I>m</I>.<P><HR><A NAME="tex2html6538" HREF="page467.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6536" HREF="page465.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6530" HREF="page465.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6540" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -