randomnumbersin c_bygeorgemarsaglia_etc.htm

QPSK环境下的仿真性能分析

>    Its period is 2^31*(2^256-1), about 2^287, and
>    it seems to pass all tests---in particular,
>    those of the kind for which 2-lag generators
>    using +,-,xor seem to fail.  For even more
>    confidence in its suitability,  LFIB4 can be
>    combined with KISS, with a resulting period of
>    about 2^410: just use (KISS+LFIB4) in any C
>    expression.                               */
>
> /* SWB is a subtract-with-borrow generator that I
>    developed to give a simple method for producing
>    extremely long periods:
>    x(n)=x(n-222)-x(n-237)-borrow mod 2^32.
>    The 'borrow' is 0 unless set to 1 if computing
>    x(n-1) caused overflow in 32-bit integer
>    arithmetic. This generator has a very long
>    period, 2^7098(2^480-1), about 2^7578. It seems
>    to pass all tests of randomness, but,
>    suspicious of a generator so simple and fast
>    (62 nanosecs at 300MHz), I would suggest
>    combining SWB with KISS, MWC, SHR3, or CONG. */
>
> /* Finally, because many simulations call for
>    uniform random variables in 0<v<1 or -1<v<1, I
>    use #define statements that permit inclusion of
>    such variates directly in expressions:  using
>    UNI will provide a uniform random real (float)
>    in (0,1), while VNI will provide one in (-1,1).  */
>
> /* All of these: MWC, SHR3, CONG, KISS, LFIB4,
>    SWB, UNI and VNI, permit direct insertion of
>    the desired random quantity into an expression,
>    avoiding the time and space costs of a function
>    call. I call these in-line-define functions.
>    To use them, static variables z,w,jsr and
>    jcong should be assigned seed values other than
>    their initial values.  If LFIB4 or SWB are
>    used, the static table t[256] must be
>    initialized.  A sample procedure follows. */
>
> /* A note on timing:  It is difficult to provide
>    exact time costs for inclusion of one of these
>    in-line-define functions in an expression.
>    Times may differ widely for different
>    compilers, as the C operations may be deeply
>    nested and tricky. I suggest these rough
>    comparisons, based on averaging ten runs of a
>    routine that is essentially a long loop:
>    for(i=1;i<10000000;i++) L=KISS; then with KISS
>    replaced with SHR3, CONG,... or KISS+SWB, etc.
>    The times on my home PC, a Pentium 300MHz, in
>    nanoseconds: LFIB4=64; CONG=90; SWB=100;
>    SHR3=110; KISS=209; KISS+LFIB4=252; KISS+SWB=310.     */




<HR><A NAME = "[e-mail]"></A>
Subject: Re: Random numbers in C: Some suggestions.
Date: Tue, 12 Jan 1999 13:56:41 -0500
From: George Marsaglia &LT;[e-mail]>
Message-ID: &LT;[e-mail]>
References: <A HREF = "#[e-mail]">&LT;[e-mail]></A>
Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physics
Lines: 59



Charles Bond wrote:

> Thanks for the post. I want to comment on the SWB routine. I've been
> using
> a similar routine in high speed simulations for years. ...

&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
     Many years?  It hasn't been very many years
      since I invented the subtract-with-borrow method,
      and developed theory for establishing the periods.
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

>   . I believe Knuth briefly discussed the method with guarded
> approval -- constrained by the concern that there was no real theory
> behind it. Do you know if any theoretical work has been done since
> Knuth's book to justify SWB?

> &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
>    This business of providing 'theoretical support' for
>   RNG's tends to be overdone---perhaps
>   because of the influence of Knuth. His marvelous
>   expository and poweful mathematical skills have
>   justifiably made him the leading authority.
>   Many people do not understand that such theory
>   is based on the simple fact that congruential
>   random numbers "fall mainly in the planes",
>   that is,  points whose coordinates are succesive
>   elements from the sequence lie on a lattice
>   with a huge unit-cell volume, (m^(n-1) in n-dimensions),
>   compared to the  unit-cell volume of 1 for truly random
>   integers.  So the "lattice test", as I called it,
>   applies to congruential generators, although the ideas have
>   been extended to the near-lattice-like patterns of
>   certain other kinds of generators.  But there seem
>   to be no such lattice-like patterns for many other
>   kinds of generators, and even if there were, it
>   is an easy matter to destroy such  patterns by
>   combining with generators having disparate mathematical
>   structures.
>
>   The quote from my Keynote Address at the 1984
>   Computer Science and Statistics: Symposium on the
>   Interface,  still applies:
>
>   "A random number generator is like sex:
>      When it's good, its wonderful;
>      And when it's bad, it's still pretty good."
>
>   Add to that, in line with my recommendations
>   on combination generators;
>
>     "And if it's bad, try a twosome or threesome."
>
> George Marsaglia




<HR><A NAME = "[e-mail]"></A>
Subject: Re: Random numbers in C: Some suggestions.
Date: Tue, 12 Jan 1999 16:09:29 -0800
From: Charles Bond &LT;[e-mail]>
Message-ID: &LT;[e-mail]>
References: <A HREF = "#[e-mail]">&LT;[e-mail]></A>
Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physics
Lines: 69

For the record, I did not mean to imply that Knuth's subtractive
generator was *the same* as your subtract with borrow, only that
it was *similar* (high speed, no multiplications). I gladly acknowledge
your claim on it. But you seem a little skeptical of it yourself, and I
was just curious.

Regards,

C. Bond

George Marsaglia wrote:

> Charles Bond wrote:
>
> > Thanks for the post. I want to comment on the SWB routine. I've been
> > using
> > a similar routine in high speed simulations for years. ...
>
> &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
>      Many years?  It hasn't been very many years
>       since I invented the subtract-with-borrow method,
>       and developed theory for establishing the periods.
> &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
>
> >   . I believe Knuth briefly discussed the method with guarded
> > approval -- constrained by the concern that there was no real theory
> > behind it. Do you know if any theoretical work has been done since
> > Knuth's book to justify SWB?
>
> > &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
> >    This business of providing 'theoretical support' for
> >   RNG's tends to be overdone---perhaps
> >   because of the influence of Knuth. His marvelous
> >   expository and poweful mathematical skills have
> >   justifiably made him the leading authority.
> >   Many people do not understand that such theory
> >   is based on the simple fact that congruential
> >   random numbers "fall mainly in the planes",
> >   that is,  points whose coordinates are succesive
> >   elements from the sequence lie on a lattice
> >   with a huge unit-cell volume, (m^(n-1) in n-dimensions),
> >   compared to the  unit-cell volume of 1 for truly random
> >   integers.  So the "lattice test", as I called it,
> >   applies to congruential generators, although the ideas have
> >   been extended to the near-lattice-like patterns of
> >   certain other kinds of generators.  But there seem
> >   to be no such lattice-like patterns for many other
> >   kinds of generators, and even if there were, it
> >   is an easy matter to destroy such  patterns by
> >   combining with generators having disparate mathematical
> >   structures.
> >
> >   The quote from my Keynote Address at the 1984
> >   Computer Science and Statistics: Symposium on the
> >   Interface,  still applies:
> >
> >   "A random number generator is like sex:
> >      When it's good, its wonderful;
> >      And when it's bad, it's still pretty good."
> >
> >   Add to that, in line with my recommendations
> >   on combination generators;
> >
> >     "And if it's bad, try a twosome or threesome."
> >
> > George Marsaglia




<HR><A NAME = "[e-mail]"></A>
Subject: Re: Random numbers in C: Some suggestions.
Date: Tue, 12 Jan 1999 15:54:10 -0800
From: Mike Oliver &LT;[e-mail]>
Message-ID: &LT;[e-mail]>
References: <A HREF = "#[e-mail]">&LT;[e-mail]></A>
Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physics
Lines: 17

George Marsaglia wrote:

> [...] and experience has shown that
> lagged Fibonacci generators using xor provide
> unsatisfactory 'randomness' unless the lags are
> very long, and even for those with very long lags,
> (and even for those using + or - rather than xor),

Could you give us a pointer to information about
why these RNGs are unsatisfactory and what sort
of test they tend to fail?

-- 
Disclaimer:  I could be wrong -- but I'm not.  (Eagles, "Victim of Love")

Finger for PGP public key, or visit <A HREF = "http://www.math.ucla.edu/~oliver.">http://www.math.ucla.edu/~oliver.</A>
1500 bits, fingerprint AE AE 4F F8 EA EA A6 FB  E9 36 5F 9E EA D0 F8 B9

<HR><A NAME = "[e-mail]"></A>
Subject: Re: Random numbers in C: Some suggestions.
Date: 13 Jan 1999 12:21:37 -0800
From: Eric Backus &LT;[e-mail]>
Message-ID: &LT;[e-mail]>
References: <A HREF = "#[e-mail]">&LT;[e-mail]></A>
Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physics
Lines: 65

George Marsaglia &LT;[e-mail]> writes:

> This posting ends with  17  lines of
> C code that provide eight different
> in-line random number generators, six for
> random 32-bit integers and two for uniform
> reals in (0,1) and (-1,1).
> Comments are interspersed with that
> code. Various combinations of the six in-line
> integer generators may put in C expressions to
> provide a wide variety of very fast, long period,
> well-tested RNG's. I invite comments, feedback,
> verifications and timings.

> #define UL unsigned long
> #define znew  ((z=36969*(z&65535)+(z>>16))&LT;&LT;16)
> #define wnew  ((w=18000*(w&65535)+(w>>16))&65535)
> #define MWC   (znew+wnew)
> #define SHR3  (jsr=(jsr=(jsr=jsr^(jsr&LT;&LT;17))^(jsr>>13))^(jsr&LT;&LT;5))
> #define CONG  (jcong=69069*jcong+1234567)
> #define KISS  ((MWC^CONG)+SHR3)
> #define LFIB4 (t[c]=t[c]+t[c+58]+t[c+119]+t[++c+178])
> #define SWB   (t[c+237]=(x=t[c+15])-(y=t[++c]+(x&LT;y)))
> #define UNI   (KISS*2.328306e-10)
> #define VNI   ((long) KISS)*4.656613e-10
> /*  Global static variables: */
>  static UL z=362436069, w=521288629, jsr=123456789, jcong=380116160;
>  static UL t[256];
>  static UL x=0,y=0; static unsigned char c=0;
> 
> /* Random seeds must be used to reset z,w,jsr,jcong and
> the table t[256]  Here is an example procedure, using KISS: */
> 
>  void settable(UL i1,UL i2,UL i3,UL i4)
>  { int i; z=i1;w=i2,jsr=i3; jcong=i4;
>  for(i=0;i&LT;256;i++)  t[i]=KISS;        }


Thank you for providing this extremely useful code.  (I'd like to make
use of it, however I see no copyright notice, can I assume you are
making it free for anyone to use?)


I have a small problem with the definition of LFIB4 and SWB.  In an
attempt to make these a single line of C code, they both use "++c" in
the same expression as they use "c".  A C compiler is free to
rearrange the order in which it calculates the intermediate terms of
these expressions, so the expressions can produce different results
depending on the compiler.

I might propose alternate expressions using the "," operator in
order to remove any ambiguity.  With a good compiler, these
expressions probably won't be any slower than your original ones:

#define LFIB4_ALT (t[c]=t[c]+t[c+58]+t[c+119]+t[c+179],t[c++])
#define SWB_ALT   (t[c+237]=(x=t[c+15])-(y=t[c+1]+(x&LT;y)),t[c++ +237])

However, these are uglier and harder to understand than your original
expressions, and of course I might have made a mistake in interpreting
where the c++ should go.  Any comments?

-- 
			Eric Backus &LT;[e-mail]>
			http://labejb.lsid.hp.com/
			[phone]

<HR><A NAME = "[e-mail]"></A>
Subject: Random numbers for C: Improvements.
Date: Fri, 15 Jan 1999 11:41:47 -0500
From: George Marsaglia &LT;[e-mail]>
Message-ID: &LT;[e-mail]>
References: <A HREF = "#[e-mail]">&LT;[e-mail]></A>
Newsgroups: sci.stat.math,sci.math,sci.math.numer-analysis
Lines: 93

As I hoped, several suggestions have led to
improvements in the code for RNG's I proposed for