🚀 go-pugleaf

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