HALTON_ADVANCED
The Halton Quasi Monte Carlo (QMC) Sequence
HALTON_ADVANCED
is a MATLAB library which
computes elements of a Halton Quasi Monte Carlo (QMC) sequence.
HALTON_ADVANCED 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
DIM_NUMdimensional 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;
Both of these routines require explicit input values for all
parameters.
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;
These routines allow the user to either rely on the default
values of parameters, or to change a few of them by calling
appropriate routines.
The DIM_NUMdimensional Halton sequence is really DIM_NUM 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 STEPth subsequence
element is simply the Halton sequence element with index
SEED(1:DIM_NUM) + STEP * LEAP(1:DIM_NUM).
The arguments that the user may set include:

DIM_NUM, the spatial dimension,
default: DIM_NUM = 1,
required: 1 <= DIM_NUM;

STEP, the subsequence index.
default: STEP = 0,
required: 0 <= STEP.

SEED(1:DIM_NUM), the Halton sequence index corresponding
to STEP = 0.
default: SEED(1:DIM_NUM) = (0, 0, ... 0),
required: 0 <= SEED(1:DIM_NUM);

LEAP(1:DIM_NUM), the succesive jumps in the Halton sequence.
default: LEAP(1:DIM_NUM) = (1, 1, ..., 1).
required: 1 <= LEAP(1:DIM_NUM).

BASE(1:DIM_NUM), the Halton bases.
default: BASE(1:DIM_NUM) = (2, 3, 5, 7, 11... ),
required: 1 < BASE(1:DIM_NUM).
The DIM_NUMdimensional Halton sequence is derived from the 1dimensional
van der Corput sequence. Each dimension simply uses a different
prime number as the base of the calculation.
The DIM_NUMdimensional Halton sequence is related to the DIM_NUM+1 dimensional
Hammersley sequence
of length NMAX. An DIM_NUM+1 dimensional Hammersley
sequence of length NMAX becomes an DIM_NUMdimensional Halton sequence by
deleting the first dimension. An DIM_NUM dimensional Halton sequence of NMAX
points becomes an DIM_NUM+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 Ith 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 welldistributed pattern. However,
for higher dimensions (such as DIM_NUM = 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 the unit circle in 2D,
and on 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.
Languages:
HALTON_ADVANCED is available in
a C++ version and
a FORTRAN90 version and
a MATLAB version.
Related Data and Programs:
CVT,
a MATLAB program which
computes elements of a Centroidal Voronoi Tessellation.
FAURE,
a MATLAB program which
computes elements of a Faure sequence.
HALTON,
a MATLAB library which
computes elements of a Halton Quasi Monte Carlo (QMC) sequence,
using a simple interface.
HALTON_DATASET,
a MATLAB program which
creates a
Halton sequence and write it to a file.
HAMMERSLEY,
a MATLAB program which
computes elements of a Hammersley sequence.
HEX_GRID,
a MATLAB program which
computes elements of a hexagonal grid dataset.
IHS,
a MATLAB program which
computes elements of
an improved distributed Latin hypercube dataset.
LATIN_CENTER,
a MATLAB program which
computes elements of a
Latin Hypercube dataset, choosing center points.
LATIN_EDGE,
a MATLAB program which
computes elements of a Latin Hypercube dataset, choosing edge points.
LATIN_RANDOM,
a MATLAB program which
computes elements of a Latin Hypercube dataset, choosing
points at random.
LATTICE_RULE,
a MATLAB library which
approximates multidimensional integrals using lattice rules.
LCVT,
a MATLAB program which
computes a latinized Centroidal Voronoi Tessellation.
NIEDERREITER2,
a MATLAB program which
computes elements of a Niederreiter sequence
using base 2.
SOBOL,
a MATLAB program which
computes elements of a Sobol sequence.
TOMS647,
a FORTRAN90 library which
is a version of ACM TOMS algorithm 647,
for evaluating Faure, Halton and Sobol sequences.
UNIFORM,
a MATLAB program which
computes elements of a uniform pseudorandom sequence.
VAN_DER_CORPUT,
a MATLAB program which
computes elements of a (1 dimensional)
van der Corput sequence.
Reference:

John Halton,
On the efficiency of certain quasirandom sequences of points
in evaluating multidimensional integrals,
Numerische Mathematik,
Volume 2, 1960, pages 8490.

John Halton, GB Smith,
Algorithm 247: RadicalInverse QuasiRandom Point Sequence,
Communications of the ACM,
Volume 7, 1964, pages 701702.

Ladislav Kocis, William Whiten,
Computational Investigations of LowDiscrepancy Sequences,
ACM Transactions on Mathematical Software,
Volume 23, Number 2, 1997, pages 266294.
Source Code:

arc_cosine.m,
computes the arc cosine function, with argument truncation.

atan4.m,
computes the inverse tangent of the ratio Y / X.

get_seed.m,
returns a random seed for the random number generator.

halham_dim_num_check.m,
checks DIM_NUM for a Halton or Hammersley sequence.

halham_leap_check.m,
checks LEAP for a Halton or Hammersley sequence.

halham_n_check.m,
checks N for a Halton or Hammersley sequence.

halham_seed_check.m,
checks SEED for a Halton or Hammersley sequence.

halham_step_check.m,
checks STEP for a Halton or Hammersley sequence.

halham_write.m,
writes a Halton or Hammersley sequence to a file.

halton.m,
computes the next element of the
Halton sequence in the current base.

halton_base_check.m,
checks BASE for a Halton sequence.

halton_base_get.m,
returns the current base.

halton_base_set.m,
sets the current base.

halton_dim_num_get.m,
returns the current dimension.

halton_dim_num_set.m,
sets the current dimension.

halton_leap_get.m,
returns the leap vector.

halton_leap_set.m,
sets the leap vector.

halton_seed_get.m,
returns the current seed.

halton_seed_set.m,
sets the current seed.

halton_sequence.m,
computes the next N elements of the Halton sequence,
starting at the current seed, in the current base.

halton_step_get.m,
returns the step of the leaped Halton subsequence.

halton_step_set.m,
sets the step of the leaped Halton subsequence.

i4_to_halton.m,
computes the SEEDth element of the
Halton sequence with the given BASE vector.

i4_to_halton_sequence.m,
computes the next N elements, starting at SEED, of the
Halton sequence with the given BASE vector.

i4vec_transpose_print.m,
prints an integer vector "transposed".

prime.m,
returns any of the first PRIME_MAX prime numbers.

s_len_trim.m,
returns the length of a string to the last nonblank.

timestamp.m,
prints the current YMDHMS date as a timestamp.

u1_to_sphere_unit_2d.m,
maps a point in the unit interval onto the unit sphere in 2D.

u2_to_ball_unit_2d.m,
maps a point in the unit box to the unit ball in 2D.

u2_to_sphere_unit_3d.m,
maps a point in the unit box onto the unit sphere in 3D.

u3_to_ball_unit_3d.m,
maps a point in the unit box to the unit ball in 3D.
Examples and Tests:

halton_advanced_test.m, runs all the tests.

halton_advanced_test_output.txt, output from the tests.

halton_test01.m, tests HALTON and HALTON_SEED_SET.

halton_test0125.m, tests I4_TO_HALTON.

halton_test0126.m, tests I4_TO_HALTON.

halton_test02.m, tests HALTON_SEQUENCE.

halton_test025.m, tests I4_TO_HALTON_SEQUENCE.

halton_test03.m, tests HALTON_SEQUENCE,
HALTON_SEED_GET and HALTON_SEED_GET.

halton_test04.m, tests HALTON, HALTON_BASE_GET,
and HALTON_BASE_SET.

halton_test045.m, tests HALTON_SEQUENCE.

halton_test05.m, tests HALTON.

halton_test06.m, tests HALTON_SEQUENCE.

halton_test07.m, tests HALTON_SEQUENCE, HALTON_SEED_GET,
HALTON_SEED_SET.

halton_test08.m, tests HALTON_SEQUENCE, HALTON_BASE_GET,
HALTON_BASE_SET.

halton_test09.m, tests U1_TO_SPHERE_UNIT_2D.

halton_test10.m, tests U2_TO_BALL_UNIT_2D.

halton_test11.m, tests U2_TO_SPHERE_UNIT_3D.

halton_test12.m, tests U3_TO_BALL_UNIT_3D.

halton_test13.m, tests HALTON_WRITE.

halton_02_00010.txt, a sample Halton dataset created
by HALHAM_WRITE.

halton_02_00010.png,
a PNG image of
the dataset.

halton_02_00100.txt, a sample Halton dataset created
by HALHAM_WRITE.

halton_02_00100.png,
a PNG image of
the dataset.
You can go up one level to
the MATLAB source codes.
Last revised on 20 October 2006.