>    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&LT;v&LT;1 or -1&LT;v&LT;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&LT;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 = "369B9AE9.52C98810@stat.fsu.edu"></A>Subject: Re: Random numbers in C: Some suggestions.Date: Tue, 12 Jan 1999 13:56:41 -0500From: George Marsaglia &LT;geo@stat.fsu.edu>Message-ID: &LT;369B9AE9.52C98810@stat.fsu.edu>References: <A HREF = "#369B66AB.6CDED9F8@ix.netcom.com">&LT;369B66AB.6CDED9F8@ix.netcom.com></A>Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physicsLines: 59Charles 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 = "369BE439.92E0E011@ix.netcom.com"></A>Subject: Re: Random numbers in C: Some suggestions.Date: Tue, 12 Jan 1999 16:09:29 -0800From: Charles Bond &LT;cbond@ix.netcom.com>Message-ID: &LT;369BE439.92E0E011@ix.netcom.com>References: <A HREF = "#369B9AE9.52C98810@stat.fsu.edu">&LT;369B9AE9.52C98810@stat.fsu.edu></A>Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physicsLines: 69For the record, I did not mean to imply that Knuth's subtractivegenerator was *the same* as your subtract with borrow, only thatit was *similar* (high speed, no multiplications). I gladly acknowledgeyour claim on it. But you seem a little skeptical of it yourself, and Iwas just curious.Regards,C. BondGeorge 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 = "369BE0A2.CA197F7B@math.ucla.edu"></A>Subject: Re: Random numbers in C: Some suggestions.Date: Tue, 12 Jan 1999 15:54:10 -0800From: Mike Oliver &LT;oliver@math.ucla.edu>Message-ID: &LT;369BE0A2.CA197F7B@math.ucla.edu>References: <A HREF = "#369B5E30.65A55FD1@stat.fsu.edu">&LT;369B5E30.65A55FD1@stat.fsu.edu></A>Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physicsLines: 17George 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 aboutwhy these RNGs are unsatisfactory and what sortof 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 = "tun23mnctq.fsf@labejb.lsid.hp.com"></A>Subject: Re: Random numbers in C: Some suggestions.Date: 13 Jan 1999 12:21:37 -0800From: Eric Backus &LT;ericb@labejb.lsid.hp.com>Message-ID: &LT;tun23mnctq.fsf@labejb.lsid.hp.com>References: <A HREF = "#369B5E30.65A55FD1@stat.fsu.edu">&LT;369B5E30.65A55FD1@stat.fsu.edu></A>Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physicsLines: 65George Marsaglia &LT;geo@stat.fsu.edu> 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 makeuse of it, however I see no copyright notice, can I assume you aremaking it free for anyone to use?)I have a small problem with the definition of LFIB4 and SWB.  In anattempt to make these a single line of C code, they both use "++c" inthe same expression as they use "c".  A C compiler is free torearrange the order in which it calculates the intermediate terms ofthese expressions, so the expressions can produce different resultsdepending on the compiler.I might propose alternate expressions using the "," operator inorder to remove any ambiguity.  With a good compiler, theseexpressions 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 originalexpressions, and of course I might have made a mistake in interpretingwhere the c++ should go.  Any comments?-- 			Eric Backus &LT;eric_backus@hp.com>			http://labejb.lsid.hp.com/			(425) 335-2495<HR><A NAME = "369F6FCA.74C7C041@stat.fsu.edu"></A>Subject: Random numbers for C: Improvements.Date: Fri, 15 Jan 1999 11:41:47 -0500From: George Marsaglia &LT;geo@stat.fsu.edu>Message-ID: &LT;369F6FCA.74C7C041@stat.fsu.edu>References: <A HREF = "#369B5E30.65A55FD1@stat.fsu.edu">&LT;369B5E30.65A55FD1@stat.fsu.edu></A>Newsgroups: sci.stat.math,sci.math,sci.math.numer-analysisLines: 93As I hoped, several suggestions have led toimprovements in the code for RNG's I proposed for