Re: Which is faster? ziggurat or Monty Python (or maybe something else?)
Ian Buckner [EMAIL PROTECTED] wrote in message
[EMAIL PROTECTED]">news:[EMAIL PROTECTED]...
The Box-Muller algorithm rejects roughly 22.5% of the
generated points. I'm not aware of any bound on the number
of consecutive rejections, other than a statistical one, hence
my statement. I would welcome correction if this is not the case.
Regards
Ian
Radford Neal [EMAIL PROTECTED] wrote in message
[EMAIL PROTECTED]">news:[EMAIL PROTECTED]...
Box-Muller does not work for real time requirements.
This isn't true, of course. A real time application is one where
one must guarantee that an operation takes no more than some
specified
maximum time. The Box-Muller method for generating normal random
variates does not involve any operations that could take arbitrary
amounts of time, and so is suitable for real-time applications.
This assumes that the time needed for Box-Muller is small enough,
which will surely often be true. If the time allowed is very small,
then of course one might need to use some other method.
Rejection sampling methods would not be suitable for real-time
applications, since there is no bound on how many points may be
rejected before one is accepted, and hence no bound on the time
required to generate a random normal variate.
Radford Neal
=
What is usually called the Box-Muller method is
the transformation of normal variates to polar coordinates
that we all owe to Laplace for showing us how to evaluate
\int_0^\infty e^{-x^2}. To get a pair of independent
standard normal variates x,y, use two [0,1) uniform variates
U1,U2 and put
x = sqrt(-2*ln(U1))*cos(2pi*U2)
y = sqrt(-2*ln(U1))*sin(2pi*U2).
This is a fixed-time procedure.
The random-time procedure, often mistakenly
called Box-Muller, was developed in 1956
by Marsaglia:
Generate uniform (-1,1) variates V1,V2 until
S = V1^2 + V2^2 1
then return
x = V1*sqrt(-2ln(S)/S)
y = V2*sqrt(-2ln(S)/S).
George Marsaglia
=
Instructions for joining and leaving this list, remarks about the
problem of INAPPROPRIATE MESSAGES, and archives are available at
http://jse.stat.ncsu.edu/
=
Re: Which is faster? ziggurat or Monty Python (or maybe something else?)
Glen [EMAIL PROTECTED] wrote in message [EMAIL PROTECTED]">news:[EMAIL PROTECTED]... Alan Miller [EMAIL PROTECTED] wrote in message news:K1Fa8.25709$[EMAIL PROTECTED]... The fastest way to generate random normals and exponentials is to use George Marsaglia's ziggurat algorithm. I've seen both ziggurat and Monty Python approaches claimed as being about the fastest or close to the fastest among reasonably general algorithms (not restricted to a single distribution), and they are both nice and easy to understand and reasonably easy to code. But in the case of gaussian distributions, which is faster? Glen = (3-year old) Timings, in nanoseconds, using Microsoft Visual C++ and gcc under DOS on a 400MHz PC. Comparisons are with methods by Leva and by Ahrens-Dieter, both said to be fast, using the same the same uniform RNG. MSgcc Leva 307384 Ahrens-Dieter161193 RNOR55 65 (Ziggurat) REXP 77 40 (Ziggurat) The Monty Python method is not quite as fast as as the Ziggurat. Some may think that Alan Miller's somewhat vague reference to a source for the ziggurat article suggests disdain. The source is Journal of Statistical Software Vol 5, Issue 8, available on the Web. Potential articles for this journal seem as fully refereed and seriously considered as are those in more conventional (but glacial) journals, at least based on my experience, and I have published papers in over forty different math/stat/CS/IEEE journals, seven medical, two physics and one law journal as well several general purpose journals. George Marsaglia (I don't have a web page, so the above can be considered my way to play Ozymandius.) = Instructions for joining and leaving this list, remarks about the problem of INAPPROPRIATE MESSAGES, and archives are available at http://jse.stat.ncsu.edu/ =
Re: Which is faster? ziggurat or Monty Python (or maybe something else?)
Art Kendall [EMAIL PROTECTED] wrote in message [EMAIL PROTECTED]">news:[EMAIL PROTECTED]... I tend to be more concerned with the apparent randomness of the results than with the speed of the algorithm. As a thought experiment, what is the cumulative time difference in a run using the fastest vs the slowest algorithm? A whole minute? A second? A fractional second? I agree; the time to generate normal variates used in most simulations is a small part of the overall running time. More important are convenience and fit to the true distribution. As for the latter, most methods are functions of the presumed uniform [0,1) variates U1,U2,... used in the generating process, and their fit to the underlying distribution is a direct consequence of the suitability of the U's. There have been few reported problems, except perhaps when integers from congruential RNGs are floated then used via polar coordinates to provide pairs of normal variates in the plane. The lattice structure of pairs of points from the congruential RNG may cause patterns in the resulting normal points in the plane. Most problems with integer RNG's arise from from their suitability as iid uniform---usually 32-bit---integers. After they are floated to [0,1), problems are much less frequent. Speed can be an important factor for exponential variates---for example, when using them to generate a large set of ordered uniform [0,1) variates or when providing points in a Poisson process. As long as methods are easy to use, (via libraries, downloads, etc.), and seem to produce the required distributions well within the limits of single precision, then one may as well make a choice based on elegance and speed, criteria for which there are wide variations and challenges for improvement. Assessing the two can be likened to pairs skating and the downhill. George Marsaglia = Instructions for joining and leaving this list, remarks about the problem of INAPPROPRIATE MESSAGES, and archives are available at http://jse.stat.ncsu.edu/ =
