🚀 go-pugleaf

In article <1992Jul27.103659.11820@kth.se>, md87-mpe@hemul.nada.kth.se
(Magnus Pettersson) writes:
 
|> .... There is also a description on how to make two independent and 
|> U(0,1)-distributed random numbers into two independent N(0,1)-distributed
|> randomnumbers, with a method called "the Box-Mueller Method". That method is
|> first described in 
|> 
|> 3. G.E.P.Box and M.E.Mueller
|>    A Note on the Generation  of Random Normal Deviates
|>    Ann.Math.Stat. (1958) 29, 610-611

Don't use this method in single precision - it has a very serious
flaw.  While it is OK in double precision, there are faster and simpler
methods available (e.g. the Polar Method as described in Knuth).  The
reference for the flaw is by H.R. Neave round about 1970.


Nick Maclaren
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street,
Cambridge CB2 3QG, England.
Email:  nmm@cl.cam.ac.uk
Tel.:   +44 223 334761
Fax:    +44 223 334679

In article <1992Jul27.124120.29511@cl.cam.ac.uk> nmm@cl.cam.ac.uk (Nick Maclaren) writes:
>|> ...
>|> 3. G.E.P.Box and M.E.Mueller
>|>    A Note on the Generation  of Random Normal Deviates
>|>    Ann.Math.Stat. (1958) 29, 610-611
>
>Don't use this method in single precision - it has a very serious
>flaw.  While it is OK in double precision, there are faster and simpler
>methods available (e.g. the Polar Method as described in Knuth).  The
>reference for the flaw is by H.R. Neave round about 1970.
>
See H.R. Neave (1973), "On using the Box-Muller transformation with
multiplicative congruential pseudo-random number generators",
Applied Statistics 22:92-97.

In general, if you're interested in the tail-behaviour of some distribution,
be particularly careful about the method you choose for simulation.

                -- Ewart Shaw
-- 
J.E.H.Shaw,  Department of Statistics,  |  JANET:  strgh@uk.ac.warwick.cu
             University of Warwick,     |  BITNET: strgh%uk.ac.warwick.cu@UKACRL
             Coventry  CV4 7AL,  U.K.   |  PHONE:  +44 203 523069
yacc - the piece of code that understandeth all parsing

In article <1992Jul27.103659.11820@kth.se> md87-mpe@hemul.nada.kth.se (Magnus Pettersson) writes:
 [regarding a reference to a classic (and somewhat dangerous)
 algorithm for generating gaussian random variates]

>3. G.E.P.Box and M.E.Mueller

For everyone's information, that's Mervin Muller -- no e, no umlaut.

Ron Thisted
Department of Statistics/The University of Chicago
thisted@galton.uchicago.edu

In article <1992Jul27.132508.217@ginger.hnrc.tufts.edu> jerry@ginger.hnrc.tufts.edu (Jerry Dallal) writes:
>In article <1992Jul27.124120.29511@cl.cam.ac.uk>, nmm@cl.cam.ac.uk (Nick Maclaren) writes:
>> In article <1992Jul27.103659.11820@kth.se>, md87-mpe@hemul.nada.kth.se
>> (Magnus Pettersson) writes:
>>  
 [regarding the Box-Muller method of generating normal deviates]
>> 
>> Don't use this method in single precision - it has a very serious
>> flaw.  While it is OK in double precision, there are faster and simpler
>> methods available (e.g. the Polar Method as described in Knuth).  The
>> reference for the flaw is by H.R. Neave round about 1970.

>...There is nothing wrong with the Box-Muller method.  It is
>theoretically sound... [description of method and other comments
>omitted]

>I don't have the article in front of me but I recall that (as explained in a
>followup letter) Neave's argument was flawed.  The problem was with a
>uniform random number generator that used too small a modulus and didn't "kick
>over" fast enough.  

Well, actually, the problem is an *interaction* between multiplicative
linear congruential uniform random number generators (modulo 2^^k) and
the Box-Muller transformation.  The Neave interaction occurs with all
such uniform generators, but the problem is most pronounced when the
multiplier is small relative to the modulus.  However, this is a
*sufficient* but not necessary condition for the problem to occur, a
fact ignored in the followups to Neave's paper.  As a simple example,
if  a  is a "bad" multiplier, exactly the same problem will occur if
the random number stream is "played in reverse order", that is, if the
multiplier is replaced by  a^{-1} mod m, where  m  is the modulus of
the generator.  But a^{-1} can be quite large relative to  m, and is
generally not easy to compute (without Macsyma or Maple or
Mathematica).  And, as Nick Maclaren points out, the Marsaglia
modification -- based on exactly the same theorem -- is usually
faster, cheaper, and as easy to program.

This is an example of a rare phenomenon that I am particularly
interested in, namely, the situation where two natural algorithms,
each of which is at least adequate, can fail miserably in some way
when combined.

Ron Thisted
Department of Statistics/The University of Chicago
thisted@galton.uchicago.edu

In article <1992Jul27.124120.29511@cl.cam.ac.uk>, nmm@cl.cam.ac.uk (Nick Maclaren) writes:
> In article <1992Jul27.103659.11820@kth.se>, md87-mpe@hemul.nada.kth.se
> (Magnus Pettersson) writes:
>  
> |> 3. G.E.P.Box and M.E.Mueller
> |>    A Note on the Generation  of Random Normal Deviates
> |>    Ann.Math.Stat. (1958) 29, 610-611
> 
> Don't use this method in single precision - it has a very serious
> flaw.  While it is OK in double precision, there are faster and simpler
> methods available (e.g. the Polar Method as described in Knuth).  The
> reference for the flaw is by H.R. Neave round about 1970.
> 
> 
> Nick Maclaren
> University of Cambridge Computer Laboratory,
> New Museums Site, Pembroke Street,
> Cambridge CB2 3QG, England.


Wait! . . .  Stop! . . . Hold on a moment! . . .

There is nothing wrong with the Box-Muller method.  It is theoretically sound
and changing from single precision to double precision isn't going to affect
anything.  (For that matter, it isn't going to effect anything, either!)

The Box-Muller transformation is based on the simple fact of distribution
functions that if U and V are iid U(0,1), then 

                       sqrt(-2 log U) sin (2 pi V)
                       sqrt(-2 log U) cos (2 pi V)

are iid N(0,1).

I don't have the article in front of me but I recall that (as explained in a
followup letter) Neave's argument was flawed.  The problem was with a
uniform random number generator that used too small a modulus and didn't "kick
over" fast enough.  

I agree with Mclaren that the Neave article was published in the 70's.  I
can add that it appeared in Applied Statistics.  The followup letter appear
within the next year or two.  I'll leave it to someone else to look up the
exact references.  

(As a practical matter, I prefer to use the inverse of the standard normal
distribution to generate my random numbers.  I know it is computationally
intensive, but it relieves you from having to worry (as much)
about the joint distribution of values in your pseudo-random number stream.)

In article <1992Jul27.152841.10170@midway.uchicago.edu> thisted@galton.uchicago.edu (Ronald A. Thisted) writes:

	[umlaut for Muller removed]

Why don't we make RNG a FAQ for sci.math.stat?

Later,
Andrew Mullhaupt

In article <1126@kepler1.rentec.com>, andrew@rentec.com (Andrew
Mullhaupt) writes:
 
|> Why don't we make RNG a FAQ for sci.math.stat?

It's not making it a FAQ that's the problem - it's finding a GAA (Generally
Agreed Answer)!

Some of my recent replies are based on work that has been published in 1992,
and I frequently hear from other workers about important results that I had
missed (often in the most bizarre journals).  The area may not be large, but
it is awfully confused.


Nick Maclaren
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street,
Cambridge CB2 3QG, England.
Email:  nmm@cl.cam.ac.uk
Tel.:   +44 223 334761
Fax:    +44 223 334679

In article <1992Jul29.092934.23335@cl.cam.ac.uk>, nmm@cl.cam.ac.uk (Nick Maclaren) writes:
> 
> It's not making it a FAQ that's the problem - it's finding a GAA (Generally
> Agreed Answer)!
> 

I suspect one of the most FAQs is what generator to use.  Can we not establish
a short list of GAAs?  I nominate the Wichmann-Hill generator with the
McLeod modification.  (I hold off on posting the code until I hear whether 
this is a GAA!)