RANDOM_DATA
Generation of random data

RANDOM_DATA is a FORTRAN90 library which uses a random number generator (RNG) to sample points for various probability distributions, spatial dimensions, and geometries, including the M-dimensional cube, ellipsoid, simplex and sphere.

Most of these routines assume that there is an available source of pseudorandom numbers, distributed uniformly in the unit interval [0,1]. In this package, that role is played by the routine R8_UNIFORM_01, which allows us some portability. We can get the same results in C, FORTRAN or MATLAB, for instance. In general, however, it would be more efficient to use the language-specific random number generator for this purpose.

If we have a source of pseudorandom values in [0,1], it's trivial to generate pseudorandom points in any line segment; it's easy to take pairs of pseudorandom values to sample a square, or triples to sample a cube. It's easy to see how to deal with square region that is translated from the origin, or scaled by different amounts in either axis, or given a rigid rotation. The same simple transformations can be applied to higher dimensional cubes, without giving us any concern.

For all these simple shapes, which are just generalizations of a square, we can easily see how to generate sample points that we can guarantee will lie inside the region; in most cases, we can also guarantee that these points will tend to be uniformly distributed, that is, every subregion can expect to contain a number of points proportional to its share of the total area.

However, we will not achieve uniform distribution in the simple case of a rectangle of nonequal sides [0,A] x [0,B], if we naively scale the random values (u1,u2) to (A*u1,B*u2). In that case, the expected point density of a wide, short region will differ from that of a narrow tall region. The absence of uniformity is most obvious if the points are plotted.

If you realize that uniformity is desirable, and easily lost, it is possible to adjust the approach so that rectangles are properly handled.

But rectangles are much too simple. We are interested in circles, triangles, and other shapes. Once the geometry of the region becomes more "interesting", there are two common ways to continue.

In the acceptance-rejection method, uniform points are generated in a superregion that encloses the region. Then, points that do not lie within the region are rejected. More points are generated until enough have been accepted to satisfy the needs. If a circle was the region of interest, for instance, we could surround it with a box, generate points in the box, and throw away those points that don't actually lie in the circle. The resulting set of samples will be a uniform sampling of the circle.

In the direct mapping method, a formula or mapping is determined so that each time a set of values is taken from the pseudorandom number generator, it is guaranteed to correspond to a point in the region. For the circle problem, we can use one uniform random number to choose an angle between 0 and 2 PI, the other to choose a radius. (The radius must be chosen in an appropriate way to guarantee uniformity, however.) Thus, every time we input two uniform random values, we get a pair (R,T) that corresponds to a point in the circle.

The acceptance-rejection method can be simple to program, and can handle arbitrary regions. The direct mapping method is less sensitive to variations in the aspect ratio of a region and other irregularities. However, direct mappings are only known for certain common mathematical shapes.

Points may also be generated according to a nonuniform density. This creates an additional complication in programming. However, there are some cases in which it is possible to use direct mapping to turn a stream of scalar uniform random values into a set of multivariate data that is governed by a normal distribution.

Another way to generate points replaces the uniform pseudorandom number generator by a quasirandom number generator. The main difference is that successive elements of a quasirandom sequence may be highly correlated (bad for certain Monte Carlo applications) but will tend to cover the region in a much more regular way than pseudorandom numbers. Any process that uses uniform random numbers to carry out sampling can easily be modified to do the same sampling with a quasirandom sequence like the Halton sequence, for instance.

The library includes a routine that can write the resulting data points to a file.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

RANDOM_DATA is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

ASA183, a FORTRAN90 library which implements the Wichman-Hill pseudorandom number generator.

DISCRETE_PDF_SAMPLE_2D, a FORTRAN90 program which demonstrates how to construct a Probability Density Function (PDF) from a table of sample data, and then to use that PDF to create new samples.

RBOX, a C program which produces random data from a number of regions.

RSITES, a C++ program which produces random data in an M-dimensional box.

SIMPLEX_COORDINATES, a FORTRAN90 library which computes the Cartesian coordinates of the vertices of a regular simplex in M dimensions.

TETRAHEDRON_SAMPLES, a dataset directory which contains examples of sets of sample points from the unit tetrahedron.

TRIANGLE_GRID, a FORTRAN90 library which computes a triangular grid of points.

TRIANGLE_HISTOGRAM, a FORTRAN90 program which computes histograms of data on the unit triangle.

TRIANGLE_MONTE_CARLO, a FORTRAN90 program which uses the Monte Carlo method to estimate integrals over a triangle.

TRIANGLE_SAMPLES, a dataset directory which contains examples of sets of sample points from the unit triangle.

UNIFORM, a FORTRAN90 library which samples the uniform random distribution.

XYZ_DISPLAY, a MATLAB program which reads XYZ information defining points in 3D, and displays an image in the MATLAB graphics window.

XYZ_DISPLAY_OPENGL, a C++ program which reads XYZ information defining points in 3D, and displays an image using OpenGL.

Reference:

1. Milton Abramowitz, Irene Stegun,
   Handbook of Mathematical Functions,
   National Bureau of Standards, 1964,
   ISBN: 0-486-61272-4,
   LC: QA47.A34.
2. James Arvo,
   Stratified sampling of spherical triangles,
   Computer Graphics Proceedings, Annual Conference Series,
   ACM SIGGRAPH '95, pages 437-438, 1995.
3. Gerard Bashein, Paul Detmer,
   Centroid of a Polygon,
   in Graphics Gems IV,
   edited by Paul Heckbert,
   AP Professional, 1994,
   ISBN: 0123361559,
   LC: T385.G6974.
4. Paul Bratley, Bennett Fox, Linus Schrage,
   A Guide to Simulation,
   Second Edition,
   Springer, 1987,
   ISBN: 0387964673,
   LC: QA76.9.C65.B73.
5. Russell Cheng,
   Random Variate Generation,
   in Handbook of Simulation,
   edited by Jerry Banks,
   Wiley, 1998,
   ISBN: 0471134031,
   LC: T57.62.H37.
6. Jack Dongarra, Jim Bunch, Cleve Moler, Pete Stewart,
   LINPACK User's Guide,
   SIAM, 1979,
   ISBN13: 978-0-898711-72-1,
   LC: QA214.L56.
7. John Halton,
   On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals,
   Numerische Mathematik,
   Volume 2, Number 1, December 1960, pages 84-90.
8. John Halton, GB Smith,
   Algorithm 247: Radical-Inverse Quasi-Random Point Sequence,
   Communications of the ACM,
   Volume 7, Number 12, December 1964, pages 701-702.
9. John Hammersley,
   Monte Carlo methods for solving multivariable problems,
   Proceedings of the New York Academy of Science,
   Volume 86, 1960, pages 844-874.
10. Ladislav Kocis, William Whiten,
    Computational Investigations of Low-Discrepancy Sequences,
    ACM Transactions on Mathematical Software,
    Volume 23, Number 2, June 1997, pages 266-294.
11. Pierre LEcuyer,
    Random Number Generation,
    in Handbook of Simulation,
    edited by Jerry Banks,
    Wiley, 1998,
    ISBN: 0471134031,
    LC: T57.62.H37.
12. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.
13. Claudio Rocchini, Paolo Cignoni,
    Generating Random Points in a Tetrahedron,
    Journal of Graphics Tools,
    Volume 5, Number 4, 2000, pages 9-12.
14. Reuven Rubinstein,
    Monte Carlo Optimization, Simulation and Sensitivity of Queueing Networks,
    Krieger, 1992,
    ISBN: 0894647644,
    LC: QA298.R79.
15. Peter Shirley,
    Nonuniform Random Point Sets Via Warping,
    in Graphics Gems III,
    edited by David Kirk,
    Academic Press, 1992,
    ISBN: 0124096735,
    LC: T385.G6973
16. Greg Turk,
    Generating Random Points in a Triangle,
    in Graphics Gems I,
    edited by Andrew Glassner,
    AP Professional, 1990,
    ISBN: 0122861663,
    LC: T385.G697
17. Daniel Zwillinger, editor,
    CRC Standard Mathematical Tables and Formulae,
    30th Edition,
    CRC Press, 1996,
    ISBN: 0-8493-2479-3,
    LC: QA47.M315.

Source Code:

• random_data.f90, the source code.

Examples and Tests:

• random_data_test.f90, the sample calling program.
• random_data_test.txt, output from the sample calling program.

The sample calling program generates sets of points:

• bad_in_tetrahedron.txt, points in the unit tetrahedron, not uniformly chosen.
• bad_in_triangle.txt, points in the unit triangle, not uniformly chosen.
• brownian.txt, Brownian motion.
• brownian.png
• grid_in_cube01.txt, grid points in the unit hypercube, with CENTER = 1.
• grid_in_cube01.png
• halton_in_circle01_accept.txt, Halton points in the unit circle by acceptance/rejection.
• halton_in_circle01_accept.png
• halton_in_circle01_map.txt, Halton points in the unit circle by direct mapping.
• halton_in_circle01_map.png
• halton_in_cube01.txt, Halton points in the unit hypercube.
• halton_in_cube01.png
• hammersley_in_cube01.txt, Hammersley points in the unit hypercube.
• hammersley_in_cube01.png
• normal.txt, normal points, with strong correlation between the two coordinates.
• normal.png
• normal_circular.txt, circular normal points.
• normal_circular.png
• normal_simple.txt, normal points in which there is no correlation between the X and Y coordinates.
• normal_simple.png
• polygon_vertices.txt, the vertices of a polygon to be filled by random points.
• polygon_vertices.png,
• uniform_in_annulus.txt, uniform random points in an annulus, mappint.
• uniform_in_annulus.png,
• uniform_in_annulus_accept.txt, uniform random points in an annulus, acceptance/rejection.
• uniform_in_annulus_accept.png,
• uniform_in_annulus_sector.txt, uniform random points in an annulus sector, mapping.
• uniform_in_annulus_sector.png,
• uniform_in_cube01.txt, uniform random points in the unit hypercube.
• uniform_in_cube01.png,
• uniform_in_circle01_map.txt, uniform random points in the unit circle.
• uniform_in_circle01_map.png,
• uniform_in_ellipsoid_map.txt, uniform random points in an ellipsoid.
• uniform_in_ellipsoid_map.png,
• uniform_in_parallelogram_map.txt, uniform random points in a parallelogram.
• uniform_in_parallelogram_map.png,
• uniform_in_polygon_map.txt, uniform random points in a polygon (a star, in this case).
• uniform_in_polygon_map.png,
• uniform_in_sector_map.txt, uniform random points in a circular sector.
• uniform_in_sector_map.png,
• uniform_in_simplex01_map.txt, uniform random points in the unit simplex.
• uniform_in_simplex01_map.png,
• uniform_in_sphere01_map.txt, uniform random points in the unit sphere.
• uniform_in_sphere01_map.png,
• uniform_in_tetrahedron.txt, uniform random points in an arbitrary tetrahedron.
• uniform_in_triangle_map1.txt, uniform random points in an arbitrary triangle, Turk method 1.
• uniform_in_triangle_map1.png,
• uniform_in_triangle_map2.txt, uniform random points in an arbitrary triangle, Turk method 2.
• uniform_in_triangle_map2.png,
• uniform_in_triangle01_map.txt, uniform random points in the unit triangle.
• uniform_in_triangle01_map.png,
• uniform_on_cube01.txt, uniform random points on the unit cube.
• uniform_on_ellipsoid_map.txt, uniform random points on an ellipsoid.
• uniform_on_ellipsoid_map.png,
• uniform_on_hemisphere01_phong.txt, uniform random points on a hemisphere, Phong distribution.
• uniform_on_simplex01_map.txt, uniform random points on the unit simplex.
• uniform_on_simplex01_map.png,
• uniform_on_sphere01_map.txt, uniform random points on the unit sphere in 2D.
• uniform_on_sphere01_map.png,
• uniform_on_sphere01_patch_tp.txt, uniform random points on an TP (theta,phi) "patch" of the unit sphere in 3D.
• uniform_on_sphere01_patch_tp.png
• uniform_on_sphere01_patch_xyz.txt, uniform random points on an XYZ "patch" of the unit sphere in 3D.
• uniform_on_sphere01_patch_xyz.png
• uniform_on_sphere01_triangle_xyz.txt, uniform random points on a spherical triangle of the unit sphere in 3D using XYZ coordinates.
• uniform_walk.txt, points on a uniform random walk.
• uniform_walk.png,

List of Routines:

• ARC_COSINE computes the arc cosine function, with argument truncation.
• BAD_IN_SIMPLEX01 is a "bad" (nonuniform) sampling of the unit simplex.
• BROWNIAN creates Brownian motion points.
• DPO_FA factors a DPO matrix.
• DPO_SL solves a DPO system factored by DPO_FA.
• DIRECTION_UNIFORM_ND generates a random direction vector.
• GET_UNIT returns a free FORTRAN unit number.
• GRID_IN_CUBE01 generates grid points in the unit hypercube.
• GRID_SIDE finds the smallest grid containing at least N points.
• HALHAM_LEAP_CHECK checks LEAP for a Halton or Hammersley sequence.
• HALHAM_N_CHECK checks N for a Halton or Hammersley sequence.
• HALHAM_DIM_NUM_CHECK checks DIM_NUM for a Halton or Hammersley sequence.
• HALHAM_SEED_CHECK checks SEED for a Halton or Hammersley sequence.
• HALHAM_STEP_CHECK checks STEP for a Halton or Hammersley sequence.
• HALTON_BASE_CHECK checks BASE for a Halton sequence.
• HALTON_IN_CIRCLE01_ACCEPT accepts Halton points in the unit circle.
• HALTON_IN_CIRCLE01_MAP maps Halton points into the unit circle.
• HALTON_IN_CUBE01 generates Halton points in the unit hypercube.
• HAMMERSLEY_BASE_CHECK is TRUE if BASE is legal.
• HAMMERSLEY_IN_CUBE01 generates Hammersley points in the unit hypercube.
• I4_FACTORIAL computes the factorial N!
• I4_MODP returns the nonnegative remainder of integer division.
• I4_TO_HALTON computes one element of a leaped Halton subsequence.
• I4_TO_HALTON_SEQUENCE computes N elements of a leaped Halton subsequence.
• I4_TO_HAMMERSLEY computes one element of a leaped Hammersley subsequence.
• I4_TO_HAMMERSLEY_SEQUENCE: N elements of a leaped Hammersley subsequence.
• I4_UNIFORM_AB returns a scaled pseudorandom I4 between A and B.
• I4VEC_TRANSPOSE_PRINT prints an I4VEC "transposed".
• KSUB_RANDOM2 selects a random subset of size K from a set of size N.
• NORMAL creates normally distributed points.
• NORMAL_CIRCULAR creates circularly normal points.
• NORMAL_MULTIVARIATE samples a multivariate normal distribution.
• NORMAL_SIMPLE creates normally distributed points.
• POLYGON_CENTROID_2D computes the centroid of a polygon in 2D.
• PRIME returns any of the first PRIME_MAX prime numbers.
• R8_NORMAL_01 returns a unit pseudonormal R8.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• R8MAT_NORMAL_01 returns a unit pseudonormal R8MAT.
• R8MAT_PRINT prints a R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8MAT_UNIFORM_01 returns a unit pseudorandom R8MAT.
• R8MAT_WRITE writes an R8MAT file.
• R8VEC_NORM returns the L2 norm of an R8VEC.
• R8VEC_NORMAL_01 returns a unit pseudonormal R8VEC.
• R8VEC_PRINT prints a R8VEC.
• R8VEC_UNIFORM_01 returns a unit pseudorandom R8VEC.
• SCALE_FROM_SIMPLEX01 rescales data from a unit to non-unit simplex.
• SCALE_TO_BALL01 translates and rescales data to fit within the unit ball.
• SCALE_TO_BLOCK01 translates and rescales data to fit in the unit block.
• SCALE_TO_CUBE01 translates and rescales data to the unit hypercube.
• STRI_ANGLES_TO_AREA computes the area of a spherical triangle.
• STRI_SIDES_TO_ANGLES computes spherical triangle angles.
• STRI_VERTICES_TO_SIDES_3D computes spherical triangle sides.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TRIANGLE_AREA_2D computes the area of a triangle in 2D.
• TUPLE_NEXT_FAST computes the next element of a tuple space, "fast".
• UNIFORM_IN_ANNULUS samples a circular annulus.
• UNIFORM_IN_ANNULUS_ACCEPT accepts points in an annulus.
• UNIFORM_IN_ANNULUS_SECTOR samples an annular sector in 2D.
• UNIFORM_IN_CIRCLE01_MAP maps uniform points into the unit circle.
• UNIFORM_IN_CUBE01 creates uniform points in the unit hypercube.
• UNIFORM_IN_ELLIPSOID_MAP maps uniform points into an ellipsoid.
• UNIFORM_IN_PARALLELOGRAM_MAP maps uniform points into a parallelogram.
• UNIFORM_IN_POLYGON_MAP maps uniform points into a polygon.
• UNIFORM_IN_SECTOR_MAP maps uniform points into a circular sector.
• UNIFORM_IN_SIMPLEX01_MAP maps uniform points into the unit simplex.
• UNIFORM_IN_SPHERE01_MAP maps uniform points into the unit sphere.
• UNIFORM_IN_TETRAHEDRON returns uniform points in a tetrahedron.
• UNIFORM_IN_TRIANGLE_MAP1 maps uniform points into a triangle.
• UNIFORM_IN_TRIANGLE_MAP2 maps uniform points into a triangle.
• UNIFORM_IN_TRIANGLE01_MAP maps uniform points into the unit triangle.
• UNIFORM_ON_CUBE returns random points on the surface of a cube.
• UNIFORM_ON_CUBE01 returns random points on the surface of the unit cube.
• UNIFORM_ON_ELLIPSOID_MAP maps uniform points onto an ellipsoid.
• UNIFORM_ON_HEMISPHERE01_PHONG maps uniform points onto the unit hemisphere.
• UNIFORM_ON_SIMPLEX01_MAP maps uniform points onto the unit simplex.
• UNIFORM_ON_SPHERE01_MAP maps uniform points onto the unit sphere.
• UNIFORM_ON_SPHERE01_PATCH_TP maps uniform points onto a spherical TP patch.
• UNIFORM_ON_SPHERE01_PATCH_XYZ maps uniform points to a spherical XYZ patch.
• UNIFORM_ON_SPHERE01_TRIANGLE_XYZ: sample spherical triangle, XYZ coordinates.
• UNIFORM_ON_TRIANGLE maps uniform points onto the boundary of a triangle.
• UNIFORM_ON_TRIANGLE01: uniform points on the boundary of the unit triangle.
• UNIFORM_WALK generates points on a uniform random walk.

You can go up one level to the FORTRAN90 source codes.