Recent Articles

Box-Muller transform

A Box-Muller transform is a method of generating pairs of independent normally distributed random numbers, given a source of uniformly distributed random numbers. There are two kinds:

1. Given r and φ independently uniformly distributed in (0,1], compute:

   <math>z_0 = \cos(2 \pi \varphi) \cdot \sqrt{-2 \ln r}<math>

   and

   <math>z_1 = \sin(2 \pi \varphi) \cdot \sqrt{-2 \ln r}<math>

    

2. Given x and y independently uniformly distributed in [−1,1], set R = x² + y². If R = 0 or R > 1, throw them away and try another pair (x, y). Then, for these filtered points, compute:

   <math>z_0 = x \cdot \sqrt{\frac{-2 \ln R}{R}}<math>

   and

   <math>z_1 = y \cdot \sqrt{\frac{-2 \ln R}{R}}<math>

The first method uniformly distributes numbers within a unit circle with polar coordinates (r,2πφ), while in the second method all points left after this filtering process will be uniformly distributed within a unit circle using cartesian coordinates (x,y), with R as the square of the distance from the origin.

The second method is typically faster because it uses only one transcendental function instead of at least two, even though it throws away 1-π/4 ≈ 21.46% of the total input uniformly distributed random number pairs generated, i.e. throws away 4/π−1 ≈ 0.2732 uniformly distributed random number pairs per Gaussian random number pair generated, requiring 4/π ≈ 1.2732 input random numbers per output random number.