HALTON
The Halton Quasirandom Sequence

HALTON is a C++ library which computes elements of a Halton quasirandom sequence.

HALTON includes routines to make it easy to manipulate this computation, to compute the next N entries, to compute a particular entry, to restart the sequence at a particular point, or to compute NDIM-dimensional versions of the sequence.

For the most straightforward use, try either

• I4_TO_HALTON, for one element of a sequence;
• I4_TO_HALTON_SEQUENCE, for N elements of a sequence;

For more convenience, there are two related routines with almost no input arguments:

• HALTON, for one element of a sequence;
• HALTON_SEQUENCE, for N elements of a sequence;

The NDIM-dimensional Halton sequence is really NDIM separate sequences, each generated by a particular base.

Routines in this library select elements of a "leaped" subsequence of the Halton sequence. The subsequence elements are indexed by a quantity called STEP, which starts at 0. The STEP-th subsequence element is simply the Halton sequence element with index

        SEED(1:NDIM) + STEP * LEAP(1:NDIM).
      

The arguments that the user may set include:

• NDIM, the spatial dimension,
  default: NDIM = 1,
  required: 1 <= NDIM;
• STEP, the subsequence index.
  default: STEP = 0,
  required: 0 <= STEP.
• SEED(1:NDIM), the Halton sequence index corresponding to STEP = 0.
  default: SEED(1:NDIM) = (0, 0, ... 0),
  required: 0 <= SEED(1:NDIM);
• LEAP(1:NDIM), the succesive jumps in the Halton sequence.
  default: LEAP(1:NDIM) = (1, 1, ..., 1).
  required: 1 <= LEAP(1:NDIM).
• BASE(1:NDIM), the Halton bases.
  default: BASE(1:NDIM) = (2, 3, 5, 7, 11... ),
  required: 1 < BASE(1:NDIM).

The NDIM-dimensional Halton sequence is derived from the 1-dimensional van der Corput sequence. Each dimension simply uses a different prime number as the base of the calculation.

The NDIM-dimensional Halton sequence is related to the NDIM+1 dimensional Hammersley sequence of length NMAX. An NDIM+1 dimensional Hammersley sequence of length NMAX becomes an NDIM-dimensional Halton sequence by deleting the first dimension. An NDIM dimensional Halton sequence of NMAX points becomes an NDIM+1 dimensional Hammersley sequence of length NMAX by prefixing a first coordinate, and setting the value of this first coordinate to I/NMAX for the I-th entry of the sequence.

While the Hammersley sequence has better dispersion properties in technical measures such as the discrepancy, it suffers from the problem that you must know, beforehand, the number of points you are going to generate. Thus, if you have computed a Hammersley sequence of length 100, and you want to compute a Hammersley sequence of length 200, you must discard your current values and start over. By contrast, you can compute 100 points of a Halton sequence, and then 100 more, and this will be the same as computing the first 200 points of the Halton sequence in one calculation.

In low dimensions, the multidimensional Halton sequence quickly "fills up" the space in a well-distributed pattern. However, for higher dimensions (such as NDIM = 40) for instance, the initial elements of the Halton sequence can be very poorly distributed; it is only when N, the number of sequence elements, is large enough relative to the spatial dimension, that the sequence is properly behaved. Remedies for this problem were suggested by Kocis and Whiten.

As an example of the use of Halton sequences, we also use them to compute "random" points on or in the unit circle in 2D, and the unit sphere in 3D.

Licensing:

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

Related Data and Programs:

CVT is a C++ library of routines for computing points in a Centroidal Voronoi Tessellation.

FAURE is a C++ library of routines for computing Faure sequences.

GRID is a C++ library of routines for computing points on a grid.

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

HALTON_DATASET is a corresponding interactive C++ program to create a Halton sequence and write it to a file.

HAMMERSLEY is a C++ library of routines for computing Hammersley sequences.

HEX_GRID is a C++ library of routines for computing sets of points in a 2D hexagonal grid.

IHS is a C++ library of routines for computing improved Latin Hypercube datasets.

LATIN_CENTER is a C++ library of routines for computing Latin square data choosing the center value.

LATIN_EDGE is a C++ library of routines for computing Latin square data choosing the edge value.

LATIN_RANDOM is a C++ library of routines for computing Latin square data choosing a random value in the square.

LCVT is a C++ library which computes a latinized Centroidal Voronoi Tessellation.

NIEDERREITER2 is a C++ library of routines for computing Niederreiter sequences with base 2.

SOBOL is a C++ library of routines for computing Sobol sequences.

TOMS647 is a FORTRAN90 version of ACM TOMS algorithm 647, for evaluating Faure, Halton and Sobol sequences.

UNIFORM is a C++ library which computes uniform random values.

VAN_DER_CORPUT is a C++ library of routines for computing van der Corput sequences.

Reference:

1. John Halton,
   On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals,
   Numerische Mathematik,
   Volume 2, 1960, pages 84-90.
2. John Halton, GB Smith,
   Algorithm 247: Radical-Inverse Quasi-Random Point Sequence,
   Communications of the ACM,
   Volume 7, 1964, pages 701-702.
3. Ladislav Kocis, William Whiten,
   Computational Investigations of Low-Discrepancy Sequences,
   ACM Transactions on Mathematical Software,
   Volume 23, Number 2, 1997, pages 266-294.

Source Code:

• halton.C, the source code.
• halton.H, the include file.
• halton.csh, commands to compile the source code.

Examples and Tests:

• halton_prb.C, a sample problem.
• halton_prb.csh, commands to compile, link and run the sample problem.
• halton_prb_output.txt, sample problem output.
• halton_02_00010.txt, a sample dataset created by the program.
• halton_02_00010.png, a PNG image of the dataset.
• halton_02_00100.txt, a sample dataset created by the program.
• halton_02_00100.png, a PNG image of the dataset.

List of Routines:

• ARC_COSINE computes the arc cosine function, with argument truncation.
• ATAN4 computes the inverse tangent of the ratio Y / X.
• DIGIT_TO_CH returns the base 10 digit character corresponding to a digit.
• GET_SEED returns a random seed for the random number generator.
• HALHAM_DIM_NUM_CHECK checks DIM_NUM for a Halton or Hammersley sequence.
• HALHAM_LEAP_CHECK checks LEAP for a Halton or Hammersley sequence.
• HALHAM_N_CHECK checks N 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.
• HALHAM_WRITE writes a Halton or Hammersley dataset to a file.
• HALTON computes the next element in a leaped Halton subsequence.
• HALTON_BASE_CHECK checks BASE for a Halton sequence.
• HALTON_BASE_GET gets the base vector for a leaped Halton subsequence.
• HALTON_BASE_SET sets the base vector for a leaped Halton subsequence.
• HALTON_LEAP_GET gets the leap vector for a leaped Halton subsequence.
• HALTON_LEAP_SET sets the leap vector for a leaped Halton subsequence.
• HALTON_DIM_NUM_GET gets the spatial dimension for a leaped Halton subsequence.
• HALTON_DIM_NUM_SET sets the spatial dimension for a leaped Halton subsequence.
• HALTON_SEED_GET gets the seed vector for a leaped Halton subsequence.
• HALTON_SEED_SET sets the seed vector for a leaped Halton subsequence.
• HALTON_SEQUENCE computes N elements in an DIM_NUM-dimensional Halton sequence.
• HALTON_STEP_GET gets the step for the leaped Halton subsequence.
• HALTON_STEP_SET sets the step for a leaped Halton subsequence.
• I4_LOG_10 returns the whole part of the logarithm base 10 of an I4.
• I4_MIN returns the smaller of two I4's.
• 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_S converts an integer to a string.
• I4VEC_TRANSPOSE_PRINT prints an I4VEC "transposed".
• PRIME returns any of the first PRIME_MAX prime numbers.
• R8_EPSILON returns the R8 roundoff unit.
• R8VEC_DOT_PRODUCT returns the dot product of two R8VEC's.
• R8VEC_NORM_L2 returns the L2 norm of an R8VEC.
• S_LEN_TRIM returns the length of a string to the last nonblank.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TIMESTRING returns the current YMDHMS date as a string.
• U1_TO_SPHERE_UNIT_2D maps a point in the unit interval onto the circle in 2D.
• U2_TO_BALL_UNIT_2D maps points from the unit box to the unit ball in 2D.
• U2_TO_SPHERE_UNIT_3D maps a point in the unit box to the unit sphere in 3D.
• U3_TO_BALL_UNIT_3D maps points from the unit box to the unit ball in 3D.

You can go up one level to the C++ source codes.