randomnumbersin c_bygeorgemarsaglia_etc.htm

QPSK环境下的仿真性能分析

use in C. (See the thread "Random numbers for C: Some
suggestions" in previous postings.) The improved code
is listed below.

A question of copyright has also been raised.  Unlike
DIEHARD, there is no copyright on the code below. You
are free to use it in any way you want, but you may
wish to acknowledge the source, as a courtesy.

To avoid being cited by the style police, some have
suggested using typedef rather than #define in order
to replace unsigned long by UL.

Others have pointed out that one cannot be certain of
the way that a compiler will evaluate terms in a sum,
so using ++c in a term is dangerous.  They have
offered a version using the comma operator, which
ensures that the table index is incremented properly.
See LFIB4 and SWB below.

In my earlier work, done in Fortran, I had implemented
two 16-bit multiply-with-carry generators, say z and w,
as 32-bit integers, with the carry in the top 16 bits,
the output in the bottom 16.  They were combined by
(z<<16)+w.  (In Fortran, ishft(z,16)+w.) Such a
combination seemed to pass all tests. In the above-
mentioned post,  I used (z<<16)+(w&65525), and that
does not pass all tests.  So (z<<16)+w seems
preferable; it is used below, providing a MWC that
seems to pass all tests.

 The generators MWC, KISS, LFIB4 and SWB seem to pass all tests.
By themselves, CONG and SHR3 do not, but using
CONG+SHR3 provides one of the fastest combinations that satisfy
the DIEHARD battery of tests.

Of course, one cannot have absolute confidence in any
generator. The choices LFIB4 and SWB have immense
periods, are very fast, and pass all tests in DIEHARD,
but I am hesitant to rely on them alone---primarily
because they come from such simple mod 2^32 arithmetic:
four adds in LFIB4 or one subtract-with-borrow in SWB.

The code below provides  a variety of in-line generators that
seem promising by themselves, and even more so in combination.
With them,  one may feel fairly confident  that combinations
will produce results  consistent with the underlying probability theory
in your applications.


All combinations seem to support the supplemented quote
from my 1984 Keynote Address:

       A random number generator is like sex;
       When it's good, it's wonderful,
       And when it's bad, it's still pretty good.

       And when it's bad, try a twosome or threesome.

The C code follows; you may want to snip and save from
here--------------------------------------------------:

#define znew  (z=36969*(z&65535)+(z>>16))
#define wnew  (w=18000*(w&65535)+(w>>16))
#define MWC   ( (znew<<16)+wnew )
#define SHR3  (jsr=(jsr=(jsr=jsr^(jsr<<17))^(jsr>>13))^(jsr<<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],t[++c])
#define SWB   (t[c+237]=(x=t[c+15])-(y=t[c]+(x<y)),t[++c])
#define UNI   (KISS*2.328306e-10)
#define VNI   ((long) KISS)*4.656613e-10
typedef unsigned long UL;

/*  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<256;i++)  t[i]=KISS;        }

/* Any one of KISS, MWC, LFIB4, SWB, SHR3, or CONG  can be used in
   an expression to provide a random 32-bit integer, while UNI
   provides a real in (0,1) and VNI a real in (-1,1).   */




<HR><A NAME = "[e-mail]"></A>
Subject: Re: Random numbers for C: Improvements.
Date: 15 Jan 1999 14:02:47 -0500
From: [e-mail] (Dmitri Zaykin)
Message-ID: &LT;[e-mail]>
References: <A HREF = "#[e-mail]">&LT;[e-mail]></A>
Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis
Lines: 11

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

> #define LFIB4 (t[c]=t[c]+t[c+58]+t[c+119]+t[c+178],t[++c])
> #define SWB   (t[c+237]=(x=t[c+15])-(y=t[c]+(x&LT;y)),t[++c])

Shouldn't these be

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

Dmitri

<HR><A NAME = "[e-mail]"></A>
Subject: Re: Random numbers for C: Improvements.
Date: 15 Jan 99 20:16:13 GMT
From: [e-mail] (Radford Neal)
Message-ID: &LT;[e-mail]>
References: <A HREF = "#[e-mail]">&LT;[e-mail]></A>
Newsgroups: sci.math,sci.math.num-analysis,sci.stat.math
Lines: 28

>George Marsaglia &LT;[e-mail]> writes:
>
>> #define LFIB4 (t[c]=t[c]+t[c+58]+t[c+119]+t[c+178],t[++c])
>> #define SWB   (t[c+237]=(x=t[c+15])-(y=t[c]+(x&LT;y)),t[++c])
>

In article &LT;[e-mail]>,
Dmitri Zaykin &LT;[e-mail]> wrote:

>Shouldn't these be
>
>#define LFIB4 (t[c]=t[c]+t[c+58]+t[c+119]+t[c+179], ++c)
>#define SWB   (t[c+237]=(x=t[c+15])-(y=t[c+1]+(x&LT;y)), ++c)
>

This doesn't work either.  I believe that it is undefined whether the
comparison x&LT;y uses the new or the old value of x.  The SHR3 macro
in the original source also suffers from this flaw.

I think one needs to face up to an unpleasant truth:  The #define 
facility of C was poorly designed, and is incapable in general of
supporting the definition of "in-line" procedures.  It is far better
to simply write ordinary C procedures, and accept the fairly small
procedure call overhead.

   Radford Neal



<HR><A NAME = "QfQn2.10695$[e-mail]"></A>
Subject: Re: Random numbers for C: Improvements.
Date: Fri, 15 Jan 1999 17:34:36 -0600
From: "Jeff Stout" &LT;[e-mail]>
Message-ID: &LT;QfQn2.10695$[e-mail]>
References: <A HREF = "#[e-mail]">&LT;[e-mail]></A>
Newsgroups: sci.math,sci.math.num-analysis,sci.stat.math
Lines: 27


Radford Neal wrote in message
&LT;[e-mail]>...
>
>
>I think one needs to face up to an unpleasant truth:  The #define
>facility of C was poorly designed, and is incapable in general of
>supporting the definition of "in-line" procedures.  It is far better
>to simply write ordinary C procedures, and accept the fairly small
>procedure call overhead.
>
>   Radford Neal
>
>

This is not a poor design of the macro facility of C, but a built in
limitation of the C language itself.  The preprocessor is just doing
a stupid text substituation, its the C compiler that is ambigous about
the interpretation

The C macro language can support "in-line" procedures and a lot
of other junk only true software wienies would ever use.

Jeff Stout



<HR><A NAME = "[e-mail]"></A>
Subject: Re: Random numbers for C: Improvements.
Date: 16 Jan 99 04:43:12 GMT
From: [e-mail] (Radford Neal)
Message-ID: &LT;[e-mail]>
References: <A HREF = "#QfQn2.10695$[e-mail]">&LT;QfQn2.10695$[e-mail]></A>
Newsgroups: sci.math,sci.math.num-analysis,sci.stat.math
Lines: 88

>Radford Neal wrote in message
>&LT;[e-mail]>...
>>
>>I think one needs to face up to an unpleasant truth:  The #define
>>facility of C was poorly designed, and is incapable in general of
>>supporting the definition of "in-line" procedures.  It is far better
>>to simply write ordinary C procedures, and accept the fairly small
>>procedure call overhead.

In article &LT;QfQn2.10695$[e-mail]>,
Jeff Stout &LT;[e-mail]> wrote:
>This is not a poor design of the macro facility of C, but a built in
>limitation of the C language itself.  The preprocessor is just doing
>a stupid text substituation, its the C compiler that is ambigous about
>the interpretation
>
>The C macro language can support "in-line" procedures and a lot
>of other junk only true software wienies would ever use.

In saying that the #define facility of C was poorly designed, I of
course meant that it does not do what is needed to write good programs.
The fact that it does stupid text substitation is a big part of this.

In the case under discussion, the only reason (I hope!) that obscure
and semantically undefined constructs were being used was in order to
try to define an in-line procedure using this inadequate facility.

Unfortunately, although one can indeed create lots of junk using the
C pre-processor, one cannot, in general, use it to create in-line
procedures.  One can't write a macro equivalent to the following,
for instance:

  int first_zero (int *a)
  { int i;
    for (i = 0; a[i]!=0; i++) ;
    return i;
  }

Furthermore, in many cases where one CAN write in-line procedures
using C macros, 99% of the people who try to do so get it wrong.  For
example, the following procedure CAN be written as a macro:

  void badexample(int a)
  { 
    while (f(a)==0) ;
    g(a);
  }

but NOT as follows:

  #define badexample(a) while (f(a)==0) ; g(a);

nor as follows:

  #define badexample(a) { while (f(a)==0) ; g(a); }

The following gets closer:

  #define badexample(a) do { while (f(a)==0) ; g(a); } while (0)

Note: NO semicolon at the end.  The necessity of this trick is left
as an exercise for the reader.

Really, though, one needs to define the macro as follows:

  #define badexample(a) do { int fy7653_4xq = a; \
                             while (f(fy7653_4xq)==0) ; \
                             g(fy7653_4xq); \
                        } while (0)

Here, fy7853_4xq is assumed to be sufficiently obscure that it is
unlikely to conflict with the name of a variable that occurs in a.

Not illustrated in this example, but commonly overlooked, is the
frequent necessity to enclose references to the parameters of the
macro in parentheses.

Failure to understand these arcane necessities will result in macros
that behave just like the procedure they are trying to mimic around
95% of the times they are called, and which produce completely obscure
bugs the other 5% of the time.

   Radford Neal

   




<HR><A NAME = "[e-mail]"></A>
Subject: Re: Random numbers for C: Improvements.
Date: 16 Jan 1999 16:14:45 -0500
From: [e-mail] (Dmitri Zaykin)
Message-ID: &LT;[e-mail]>
References: <A HREF = "#QfQn2.10695$[e-mail]">&LT;QfQn2.10695$[e-mail]></A>
Newsgroups: sci.math,sci.math.num-analysis,sci.stat.math
Lines: 15

"Jeff Stout" &LT;[e-mail]> writes:

> The C macro language can support "in-line" procedures and a lot
> of other junk only true software wienies would ever use.

It is probably true that the posted random number generators are
better implemented as regular functions. C compilers should attempt to
inline "short" functions into their callers when certain optimization
flags are enabled.

Also, the new C standard will support the "inline" keyword.  Some
compilers (e.g. gcc called without "-ansi" switch) already recognize
it.

Dmitri

<HR><A NAME = "[e-mail]"></A>
Subject: Re: Random numbers for C: Improvements.
Date: 16 Jan 1999 15:19:24 -0500
From: [e-mail] (Dmitri Zaykin)
Message-ID: &LT;[e-mail]>
References: <A HREF = "#[e-mail]">&LT;[e-mail]></A>
Newsgroups: sci.math,sci.math.num-analysis,sci.stat.math
Lines: 29