nonuniform random number generation

nonuniform random number generation

Post by beliavsk » Fri, 02 Dec 2005 07:11:31


A nonuniform random number generator (RNG) will typically call a
uniform RNG one or more times and do some manipulations to get deviates
from the desired distribution. How should one code a nonuniform RNG in
a modular way so that the underlying uniform RNG can easily be changed
without sacrificing speed? I have found that in some Monte Carlo
simulations using normal deviates, a big fraction of CPU time is spent
generating the deviates.

The normal RNG below by Alan Miller uses the Fortran intrinsic
RANDOM_NUMBER. One could easily add an integer argument that specifies
which uniform RNG to use, but I am worried that this could slow down
the random_normal function, which could be called millions of times in
a simulation.

Ideally, using a different uniform RNG would not require a recompile,
but that is doable if it gives faster results.

FUNCTION random_normal() RESULT (ran_norm)
IMPLICIT NONE
REAL :: ran_norm
REAL, PARAMETER :: s = 0.449871, t = -0.386595, a = 0.19600, b =
0.25472, &
half = 0.5, r1 = 0.27597, r2 = 0.27846
REAL :: u, v, x, y, q
DO
CALL RANDOM_NUMBER(u)
CALL RANDOM_NUMBER(v)
v = 1.7156 * (v - half)
x = u - s
y = ABS(v) - t
q = x**2 + y*(a*y - b*x)
IF (q < r1) EXIT
IF (q > r2) CYCLE
IF (v**2 < -4.0*LOG(u)*u**2) EXIT
END DO
ran_norm = v/u
END FUNCTION random_normal
 
 
 

nonuniform random number generation

Post by Gib Bogl » Fri, 02 Dec 2005 13:58:26


The fastest RNG I've found for Gaussian rvs is Ziggurat. Using this
made a significant difference to the execution speed of my Monte Carlo code.
------------ And now a word from our sponsor ------------------
Want to have instant messaging, and chat rooms, and discussion
groups for your local users or business, you need dbabble!
-- See http://www.yqcomputer.com/

 
 
 

nonuniform random number generation

Post by David Jone » Fri, 02 Dec 2005 19:24:09


One obvious approach is to go for two-stage procedure...
(i) Have "the" uniform-generating procedure store values in an
(large) array.
(ii) Have the second stage work with the uniforms from the array,
keepinf track of which have been used.

You could extend this by keeping noticing when the array of uniforms
has been used-up and then generating another array-full. Since the
decision on which generator to use need only made occasionally in this
approach, there shouldn't be much effect on performance. But the array
storage and access may have a bad effect.

David Jones