Re: Which is faster? ziggurat or Monty Python (or maybe something else?)
Thanks for the enlightenment, George.
I misinterpreted what was said in Numerical Recipes, where it starts
by
referring to the Box-Muller method, then gives your algorithm without
any
intermediate referral. Hence I had always thought of this method as
being B-M.
Hey, I learnt something new, can I go home now?
;-)
Regards
Ian
George Marsaglia [EMAIL PROTECTED] wrote in message
t8Mc8.49030$[EMAIL PROTECTED]">news:t8Mc8.49030$[EMAIL PROTECTED]...
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?)
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 = 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?)
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?)
Generated on custom silicon (surprise). Box-Muller does not work for real time requirements. Ian Glen Barnett [EMAIL PROTECTED] wrote in message [EMAIL PROTECTED]">news:[EMAIL PROTECTED]... Ian Buckner wrote: We generate pairs of properly distributed Gaussian variables at down to 10nsec intervals, essential in the application. Speed can be an issue, particularly in real time situations. Generated on what? (On a fast enough machine, even clunky old Box-Muller can probably give you that rate.) How generated? Glen = 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?)
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 = 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?)
In article [EMAIL PROTECTED], Radford Neal [EMAIL PROTECTED] wrote: 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 Acceptance-rejection, or the usually faster acceptance-replacement, methods are, strictly speaking, not real time. However, they may be much faster 99.99% of the time. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 [EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558 = 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?)
Ian Buckner [EMAIL PROTECTED] wrote in message [EMAIL PROTECTED]">news:[EMAIL PROTECTED]... Glen Barnett [EMAIL PROTECTED] wrote in message [EMAIL PROTECTED]">news:[EMAIL PROTECTED]... Ian Buckner wrote: We generate pairs of properly distributed Gaussian variables at down to 10nsec intervals, essential in the application. Speed can be an issue, particularly in real time situations. Generated on what? (On a fast enough machine, even clunky old Box-Muller can probably give you that rate.) Generated on custom silicon (surprise). Box-Muller does not work for real time requirements. Of course it does, if the machine is fast enough that you're getting them at the rate you need. And the reason you're getting them fast is you have a fast machine - which is not much help if the machine is a given. Glen = 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?)
Herman Rubin [EMAIL PROTECTED] wrote in message a4u99j$[EMAIL PROTECTED]">news:a4u99j$[EMAIL PROTECTED]... In article [EMAIL PROTECTED], Radford Neal [EMAIL PROTECTED] wrote: 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 Acceptance-rejection, or the usually faster acceptance-replacement, methods are, strictly speaking, not real time. However, they may be much faster 99.99% of the time. In that circumstance, could one not generate more values than required each call (say an extra one, assuming there's time), and store the extras up for the rare case where it's looking like it will take too long? You could take enough that the probability you exhaust them is smaller than say the probability a cosmic ray will flip a crucial bit in your hardware. You'd need a few generated at the start, of course. Glen = 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?)
We generate pairs of properly distributed Gaussian variables at down to 10nsec intervals, essential in the application. Speed can be an issue, particularly in real time situations. Ian Glen Barnett [EMAIL PROTECTED] wrote in message a4plof$p3s$[EMAIL PROTECTED]">news:a4plof$p3s$[EMAIL PROTECTED]... 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. This will be mainly a function of the randomness of the uniform generator. If we assume the same uniform generator for both, and assuming it's a pretty good one (our current one is reasonable, though I want to go back and update it soon), there shouldn't be a huge difference in the apparent randomness of the resulting gaussians. 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? When you need millions of them (as we do; a run of 10,000 simulations could need as many as 500 million gaussians, and we sometimes want to do more than 10,000), and you also want your program to be interactive (in the sense that the user doesn't have to wander off and have coffee just to do one simulation run), knowing that one algorithm is, say, 30% faster is kind of important. Particularly if the user may want to do hundreds of simulations... A whole minute extra on a simulation run is a big difference, if the user is doing simulations all day. Glen = 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?)
At 09:50 AM 2/18/02 +, Ian Buckner wrote: We generate pairs of properly distributed Gaussian variables at down to 10nsec intervals, essential in the application. Speed can be an issue, particularly in real time situations. Ian wow ... how our perspectives have changed! back in grad school, we had some cdc mainframe over in the next building and, we would go over and stick our stack of cards through the slot .. and then come back the NEXT DAY ... to pick them up ... we just hoped we hadn't put a , or other bad character someplace and would have to wait another day Dennis Roberts, 208 Cedar Bldg., University Park PA 16802 Emailto: [EMAIL PROTECTED] WWW: http://roberts.ed.psu.edu/users/droberts/drober~1.htm AC 8148632401 = 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?)
Ian Buckner wrote: We generate pairs of properly distributed Gaussian variables at down to 10nsec intervals, essential in the application. Speed can be an issue, particularly in real time situations. Generated on what? (On a fast enough machine, even clunky old Box-Muller can probably give you that rate.) How generated? Glen = 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?)
Alan Miller [EMAIL PROTECTED] wrote in message OC2b8.28457$[EMAIL PROTECTED]">news:OC2b8.28457$[EMAIL PROTECTED]... First - the reference to George's paper on the ziggurat, and the code: The Journal of Statistical Software (2000) at: http://www.jstatsoft.org/v05/i08 That I already have, thanks. Glen = 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?)
Bob Wheeler [EMAIL PROTECTED] wrote in message [EMAIL PROTECTED]">news:[EMAIL PROTECTED]... Marsaglia's ziggurat and MCW1019 generators are available in the R package SuppDists. The gcc compiler was used. Thanks Bob. Glen = 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?)
George Marsaglia [EMAIL PROTECTED] wrote in message 0l7b8.42092$[EMAIL PROTECTED]">news:0l7b8.42092$[EMAIL PROTECTED]... (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. Thanks for the information. Could you give a rough idea about the relativities? roughly 5% slower? 10%? 30%? I realise it's machine-dependent, but I'm only after a rough picture. Some may think that Alan Miller's somewhat vague reference to a source for the ziggurat article suggests disdain. I didn't get that impression. (I don't have a web page, so the above can be considered my way to play Ozymandius.) I wish you did! Glen = 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. This will be mainly a function of the randomness of the uniform generator. If we assume the same uniform generator for both, and assuming it's a pretty good one (our current one is reasonable, though I want to go back and update it soon), there shouldn't be a huge difference in the apparent randomness of the resulting gaussians. 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? When you need millions of them (as we do; a run of 10,000 simulations could need as many as 500 million gaussians, and we sometimes want to do more than 10,000), and you also want your program to be interactive (in the sense that the user doesn't have to wander off and have coffee just to do one simulation run), knowing that one algorithm is, say, 30% faster is kind of important. Particularly if the user may want to do hundreds of simulations... A whole minute extra on a simulation run is a big difference, if the user is doing simulations all day. Glen = 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?)
Marsaglia's ziggurat and MCW1019 generators are available in the R package SuppDists. The gcc compiler was used. George Marsaglia wrote: 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.) -- Bob Wheeler --- (Reply to: [EMAIL PROTECTED]) ECHIP, Inc. = 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?)
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? Glen wrote: 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? I don't yet have the CACM article on the Monty Python for the gaussian case, presumably it has some timing information. But maybe I don't even need to look if the ziggurat approach is faster. I haven't seen anything which directly discusses how they compare. Glen = 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/ =
Re: Which is faster? ziggurat or Monty Python (or maybe something else?)
George Marsaglia wrote in message 0l7b8.42092$[EMAIL PROTECTED]... .. chunk deleted 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. No disdain intended, George; I just didn't have the reference handy, and couldn't remember the name of the journal. I did give the correct reference later. I notice that you have another article in the latest issue of the journal - on tests of random numbers. Keep up the good work. George Marsaglia Cheers -- Alan Miller (Honorary Research Fellow, CSIRO Mathematical Information Sciences) http://www.ozemail.com.au/~milleraj http://users.bigpond.net.au/amiller/ = Instructions for joining and leaving this list, remarks about the problem of INAPPROPRIATE MESSAGES, and archives are available at http://jse.stat.ncsu.edu/ =
Which is faster? ziggurat or Monty Python (or maybe something else?)
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? I don't yet have the CACM article on the Monty Python for the gaussian case, presumably it has some timing information. But maybe I don't even need to look if the ziggurat approach is faster. I haven't seen anything which directly discusses how they compare. Glen = 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 wrote in message ... 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? I don't yet have the CACM article on the Monty Python for the gaussian case, presumably it has some timing information. But maybe I don't even need to look if the ziggurat approach is faster. I haven't seen anything which directly discusses how they compare. Glen First - the reference to George's paper on the ziggurat, and the code: The Journal of Statistical Software (2000) at: http://www.jstatsoft.org/v05/i08 Surprisingly, there is no reference to the Marsaglia Tsang paper in TOMS in 1998, even though 7 of the 10 references are to Marsaglia someone. If G T have done speed comparisons, which you would expect, with the Monty Python method, they are not in the ziggurat paper, though there are other speed comparisons. -- Alan Miller (Honorary Research Fellow, CSIRO Mathematical Information Sciences) http://www.ozemail.com.au/~milleraj http://users.bigpond.net.au/amiller/ = Instructions for joining and leaving this list, remarks about the problem of INAPPROPRIATE MESSAGES, and archives are available at http://jse.stat.ncsu.edu/ =
