🚀 go-pugleaf

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:
> >  
> > |> 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 [...]
> > 
> 
> Wait! . . .  Stop! . . . Hold on a moment! . . .
> 
> There is nothing wrong with the Box-Muller method.  It is
> theoretically sound [...]

Theory works beautifully when all of the assumptions hold.  One of the  
assumptions for the Box-Muller method is that you have i.i.d. uniform  
variables on the input side.  This happens to be false in most computing  
contexts -- most people use a sequence of pseudo-random numbers which are  
uncorrelated but hardly independent.

The most common source of pseudo-random numbers is the Linear Congruential  
Generator algorithm, or LCG for short.  A result by Marsaglia states that  
k-tuples from a LCG all fall on a bounded number of hyperplanes.  As a  
result, there is an interaction with the Box-Muller algorithm which causes  
all of the values produced to fall along a spiral.  For some very pretty  
pictures, check out the book "Stochastic Simulation" by Brian D. Ripley  
('87, J. Wiley & Sons).  Pages 55-58 should do a good job of convincing  
you that the results are definitely not independent normals.

There are a couple of morals to this story:
a) If you want to use Box-Muller, use something other than a LCG; and
b) Just because an algorithm is theoretically sound, don't assume you'll  
get usable results.

--paul
paul@music.sie.arizona.edu
(NeXT mail welcome!)