Subject: Summary of Random Number Generators

From: [email-masked] (Dave Young)
Date: Mon, 27 Mar 95 14:36:33 -0500

Hello,

	The following is a summary of the replies to my question
about random number generators.

****************************************************************
The original question.

Hello,

	I am starting to do Quantum Monte Carlo calculations and
I am interested in the performance of random number generators.

	There have been a number of tests developed, the most trusted
seem to be those in "Seminumerical Algorithms" by Knuth.  And there
are a number of supplemental random number generators, such as the
ran3 generator in "Numerical Recipies".  It has also been demonstrated
that in the past the random number generators built into various 
programming languages were not to be trusted.

	My question is - Do the random number generators built into
the current generation of compilers pass statistical tests?

	I have tested the built in random number generators in
Borland C++ and GNU C++ and so far they have passed all tests
(working out of Knuth).  I would like to know if it is only C++ that
has a reliable random number generator implemented or if all
compilers are now reliable, or if it is only certain vendors even within
the C++ language?

	The reason that I would like to use built in random number
generators is that Knuth indicates that code written directly in 
assembly language can accomplish the task faster than code written in
standard source code.  The GNU C++ built in random number generator
is a factor of 2 faster than the ran3 generator using all available
compiler optimization.

****************************************************************
From: TOPPER ROBERT <[email-masked]>

My best advice is to beware of using random number
generators as black-boxes, especially in the context
of Monte Carlo integrations and simulations. 

When using random number generators in Monte Carlo, you
have to not only worry about whether the samples are
uniform on the plane and uncorrelated in hyperdimensions
but also about the period of the random number sequence
(all random number generators, as you know, have a period
for a given seed -
and if your program requires a # of random numbers which
is on the order of the period of the algorithm, better
watch out).  What's more, RNGs which perform perfectly
well against a battery of statistical tests have been
known to fail when used, for example, in 3D Ising lattice
calculations...there is a good bit of literature on this
subject.

I personally wouldn't use any random number generator in 
my Monte Carlo work unless I knew exactly what the algorithm
was, had a reference for it, and had subjected it to my personal
battery of tests, which includes statistical tests ala Knuth
and application tests (path-integral and classical Monte Carlo
computations). At least then, if there is a bug in the
algorithm I know who to blame for all those wasted cycles...

Finally, in every Monte Carlo calculation I have ever carried out,
the limiting factor has not been the speed of the random number
generator, but the evaluation of the potential energy. But then
I've never done QMC calculations, so I don't know what the 
"rate-determining step" is for such calcs. Because of this,
I tend to err on the side of slow, but solid random number generation.

hope this helps, best to all-
rqt

************************************************************************

From: "Trevor Creamer" <[email-masked]>

Dave,
      What you want to do is use the most reliable (statistically) random
number generator available. I haven't done any Quantum Monte Carlo, but I've a
lot of experience using MC to study peptides and polyelectrolytes. The fraction
of time in a simulation spent generating the random numbers is miniscule
compared to the time spent calculating the energies. It is essential that you
use a reliable generator, much more important than using the fastest generator.
You probably want to spend your time optimising your energy calculation code -
this is where the bulk of simulation time is spent.
Cheers,
        Trevor

****************************************************************

From: [email-masked] (Hinsen Konrad)

	   My question is - Do the random number generators built into
   the current generation of compilers pass statistical tests?

In general, I doubt that. Random number generators are usually provided
for games and other less demanding applications. The exception is
the set of generators in the GNU C++ library. Others might also be
good, but I would always check them first.

   (working out of Knuth).  I would like to know if it is only C++ that
   has a reliable random number generator implemented or if all
   compilers are now reliable, or if it is only certain vendors even within
   the C++ language?

I would assume the latter...

	   The reason that I would like to use built in random number
   generators is that Knuth indicates that code written directly in 
   assembly language can accomplish the task faster than code written in
   standard source code.  The GNU C++ built in random number generator
   is a factor of 2 faster than the ran3 generator using all available
   compiler optimization.

Nevertheless the GNU C++ random generators are written entirely in
C++ (remember that GNU C++ is meant to be a portable compiler).

****************************************************************

From: [email-masked] (Dr. Tom Pierce)

Previously, Dave Young wrote:
> 	I am starting to do Quantum Monte Carlo calculations and
> I am interested in the performance of random number generators.
> 
> 	There have been a number of tests developed, the most trusted
> seem to be those in "Seminumerical Algorithms" by Knuth.  And there
> are a number of supplemental random number generators, such as the
> ran3 generator in "Numerical Recipies".  It has also been demonstrated
> 
> 	My question is - Do the random number generators built into
> the current generation of compilers pass statistical tests?
> 

A simple answer is "No". 

I think this topic is a permanent flame-war in sci.math.stat. 

The current publications of interest are 
"Monte Carlo Simulations: Hidden errors from "Good" Random number generators"
Phys. Rev. Letters 69(23), pp 3382 1992
  Specifically this article says ".. a specific algorithm must be tested
  together with the random number generator being used REGARDLESS of the
  tests which the generator has passed."

"Latest Development in Random Numbers", CERN Computer Newsletter 213, July-Sept.
pp 5-7, 1993.

and
"Ultra, The greatest random number generator that ever was or ever will be", by
Arif Zaman ([email-masked]) and George Marsaglia ([email-masked]), 1992.

My painful experience with compiler random number generators is that
one is far better off using a known and tested generator.            

****************************************************************

From: Gislason Jason <[email-masked]>

I have used the random number generators found in "Numerical Recipes"
and I have found them to work very well.  Personally, I would not
trust the generators built into compilers.  You just don't know
how good it works unless you or someone else has tested it.
Jason Gislason

****************************************************************
From: [email-masked] (Brian Hammond)

For QMC calculations the "quality" of pseudo-random numbers depends on the
algorithm used. Most modern Fortran- or C-library pseudo-random number
generators are good enough, particularly if you are doing branching
in which you are using a random number of pseudo-random numbers. 
Also you must consider how to create Gaussian distributed random 
numbers if your algorithm calls for them. I have seen presentations
where the overall cycle length of the underlying pseudo-random number
generator is quite noticeable due to creating Gaussian numbers by
adding 12 uniformly distributed numbers. 

So, in general use a pseudo-random number generator with a long
cycle length and use Box-Muller if you want Gaussian pseudo-random numbers.

-Brian

****************************************************************
From: [email-masked]

Hello Dave,

I always use the following random number generator. I might not be the
fastest one, but it is portable and therefore gives the same results
on all platforms. It is a linear congruential one. Additive random number
generators, like those given in Knuth's book should be a lot faster!

I hope tis helps!

Markus

<<<<<<<<<<<<<<<<<<<<<<<<<<<<random.h>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

#include <sys/types.h>
#include <sys/time.h>

/****************************************************************/
/*  Rand computes a psuedo-random                               */
/*  double value between 0 and 1, excluding 1.  Randint         */
/*  gives an integer value between low and high inclusive.      */
/****************************************************************/

#define Randomize() (Seed = time((time_t)0))

#define Randint(low,high) ( (int) ((low) + ((high)-(low)+1) * Rand()))

#define Flip(P) ((P == 1.0) ? 1 : (Rand() <= P) )

extern double Rand(void);

<<<<<<<<<<<<<<<<<<<<<<<<<<<<random.c>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

int      Seed = 707559297;

/**********************************************************************/
/* Rand                                                               */
/*--------------------------------------------------------------------*/
/* Minimal standard random number generator as defined in:            */ 
/* "Random Number Generators: Good ones are hard to find",            */ 
/* Communications of the ACM, 31(1988)1192.                           */ 
/**********************************************************************/

#define A 16807
#define M 2147483647
#define Q 127773
#define R 2836

double
Rand(void)
{
   int hi, lo, test;

   hi = Seed / Q;
   lo = Seed % Q;
 
   test = A * lo - R * hi;
   if (test > 0)
      Seed = test;
   else
      Seed = test + M;
 
   return((double)Seed / (double)M);
}

****************************************************************
From: [email-masked] (Dario Bressanini)

Dear Dave,

If I may add something to what Brian Hammond wrote,
if you are going to do Quantum Monte Carlo for Electronic structure,
the time you spend computing the value of the trial wavefunction
is much more than the time you spend to generate random deviates
I am working on QMC since 1991 and the only thing i can say is:
don't use a system provided generator: they usually have a too short cycle.
Happy Quantum Monte Carlo computing.

dario bressanini       [email-masked]

****************************************************************

From: Kari Kankaala <[email-masked]>

	Dear Dave,

	Your posting was forwarded to me by a colleague. Our group has been
	recently playing much with pseudorandomnumber generation, testing
	a variety of generators etc (e.g. Phys. Rev. Lett, 73, 2513 (1994),
	Phys. Rev. E, 48, R4211 (1993), see also Nature, 372, Dec 1, 1994,
	p. 403). 

	I'll try to comment your questions briefly below.

>
>	I am starting to do Quantum Monte Carlo calculations and
>I am interested in the performance of random number generators.

	Our interest in the work on PRNGs was due to the fact that
	we mainly weork on classical MC simulations of Stat Mech
	Systems (surfaces, polymers, complex systems in general).

>
>	There have been a number of tests developed, the most trusted
>seem to be those in "Seminumerical Algorithms" by Knuth.  And there
>are a number of supplemental random number generators, such as the
>ran3 generator in "Numerical Recipies".  It has also been demonstrated
>that in the past the random number generators built into various 
>programming languages were not to be trusted.
>
	Do not touch RAN3. It is one of the worst we tested.

>	My question is - Do the random number generators built into
>the current generation of compilers pass statistical tests?
>
	Generally, do not use any built in generators unless you
	have demonstrated data that these generators are "good".
	Cray has a decent generator in Fortran library but e.g.
	Convex has a extremely poor one available.

>	I have tested the built in random number generators in
>Borland C++ and GNU C++ and so far they have passed all tests
>(working out of Knuth).  I would like to know if it is only C++ that
>has a reliable random number generator implemented or if all
>compilers are now reliable, or if it is only certain vendors even within
>the C++ language?

	The language does not matter. It is a question of converting the
	algorithm into a code correctly. It can be only correct or
	incorrect, nothing in between. This can be done in any language.
	If you have disrecpancies with two implementations of the same
	algortihm, it would suggest that one of them is wrong.
	Whether it is the C++,C, Fortran or wahtever version, has to be
	checked. 

	What comes to vendor supplied PRNGs, I would reiterate the
	earlier comment, that never use those unless someone has demonstarted
	to you, how reliable both the algorithm and the vendor implementation
	of them are.

>
>	The reason that I would like to use built in random number
>generators is that Knuth indicates that code written directly in 
>assembly language can accomplish the task faster than code written in
>standard source code.  The GNU C++ built in random number generator
>is a factor of 2 faster than the ran3 generator using all available
>compiler optimization.
>

	You can find good algorithms and references to them e.g. in 
	our papers. I can provide you with some codes if you need them.

	But basically relying on vendor supplied stuff, is like relying
	on a variety of black boxes and then claiming that your results are
	significant even if you do not know all the steps in between.

	Hope this scared you from using vendor supplied stuff :-)

	But putting pressure on vendors, would be a very good thing.
	Still, most vendors consider random number generation as a 
	some kind of sidetrack, and do not understand its meaning
	in modern modelling and simulation. 

	Questions? Comments? I'd be happy to reply.

	Regards,

	-kari kankaala

****************************************************************

	Thank you to everyone who replied.  I hope this helps
some others as much as it has helped me.

				Dave Young
				[email-masked]
				youngdc@msucem

--------------------------------------------------------------------------
	It can be easily shown that certain methods are not applicable
to solving the many particle Schrodinger equation.
	However, it has not been shown that it is impossible to find
an analytic solution.
	The only question remaining is "Who will have the honor?"
--------------------------------------------------------------------------