HAMMERSLEY
The Hammersley Quasirandom Sequence

HAMMERSLEY is a MATLAB library which computes elements of a Hammersley quasirandom sequence.

HAMMERSLEY 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_NUM-dimensional versions of the sequence.

For the most straightforward use, try either

• I4_TO_HAMMERSLEY, for one element of a sequence;
• I4_TO_HAMMERSLEY_SEQUENCE, for N elements of a sequence;

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

• HAMMERSLEY, for one element of a sequence;
• HAMMERSLEY_SEQUENCE, for N elements of a sequence;

Routines in this library select elements of a "leaped" subsequence of the Hammersley sequence. The subsequence elements are indexed by a quantity called STEP, which starts at 0. The STEP-th subsequence element is simply the Hammersley 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 Hammersley 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 Hammersley sequence.
  default: LEAP(1:DIM_NUM) = (1, 1, ..., 1).
  required: 1 <= LEAP(1:DIM_NUM).
• BASE(1:DIM_NUM), the Hammersley bases.
  default: BASE(1:DIM_NUM) = (2, 3, 5, 7, 11... ),
  or (-N, 2, 3, 5, 7, 11,...) if N is known;
  required: 1 < BASE(I) for any van der Corput dimension I, or BASE(I) < 0 to generate the fractional sequence J/|BASE(I)|.

In the standard DIM_NUM-dimensional Hammersley sequence, it is assumed that N, the number of values to be generated, is known beforehand. The first dimension of entries in the sequence will have the form J/N for J from 1 to N. The remaining dimensions are computed using the 1-dimensional van der Corput sequence, using successive primes as bases.

In a generalized Hammersley sequence, each coordinate is allowed to be a fractional or van der Corput sequence. For any fractional sequence, the denominator is arbitrary. However, it is extremely desirable that the values in all coordinates stay between 0 and 1. This happens automatically for any van der Corput sequence, but for fractional sequences, this criterion is enforced using an appropriate modulus function. The consequence is that if you specify a small "base" for a fractional sequence, your sequence will soon wrap around and you will get repeated values.

If you drop the first dimension of the standard DIM_NUM-dimensional Hammersley sequence, you get the standard Halton sequence of dimension DIM_NUM-1.

The standard Hammersley sequence has slightly better dispersion properties than the standard Halton sequence. However, 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 N = 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 Hammersley sequence quickly "fills up" the space in a well-distributed pattern. However, for higher dimensions (such as DIM_NUM = 40) for instance, the initial elements of the Hammersley 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.

Licensing:

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

Languages:

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

Related Data and Programs:

CVT, a MATLAB library which computes elements of a Centroidal Voronoi Tessellation.

FAURE, a MATLAB library which computes elements of a Faure quasirandom sequence.

GRID, a MATLAB library which computes elements of a grid sequence.

HALTON, a MATLAB library which computes elements of a Halton quasirandom sequence.

HAMMERSLEY_DATASET, a MATLAB program which creates a Hammersley sequence and writes it to a file.

HEX_GRID, a MATLAB library which computes elements of a hexagonal grid dataset.

IHS, a MATLAB library which computes elements of an improved distributed Latin hypercube dataset.

LATIN_CENTER, a MATLAB library which computes elements of a Latin Hypercube dataset, choosing center points.

LATIN_EDGE, a MATLAB library which computes elements of a Latin Hypercube dataset, choosing edge points.

LATIN_RANDOM, a MATLAB library 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 library which computes a latinized Centroidal Voronoi Tessellation.

NIEDERREITER2, a MATLAB library which computes elements of a Niederreiter quasirandom sequence using base 2.

NORMAL, a MATLAB library which computes elements of a sequence of pseudorandom normally distributed values.

SOBOL, a MATLAB library which computes elements of a Sobol quasirandom sequence.

UNIFORM, a MATLAB library which computes elements of a uniform pseudorandom sequence.

VAN_DER_CORPUT, a MATLAB library which computes elements of a 1D van der Corput sequence.

Reference:

1. John Hammersley,
   Monte Carlo methods for solving multivariable problems,
   Proceedings of the New York Academy of Science,
   Volume 86, 1960, pages 844-874.
2. 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:

• 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.
• hammersley.m, computes the next element of the Hammersley sequence in the current base.
• hammersley_base_check.m, checks BASE for a Hammersley sequence.
• hammersley_base_get.m, returns the current base.
• hammersley_base_set.m, sets the current base.
• hammersley_dim_num_get.m, returns the current dimension.
• hammersley_dim_num_set.m, sets the current dimension.
• hammersley_leap_get.m, returns the leap vector.
• hammersley_leap_set.m, sets the leap vector.
• hammersley_seed_get.m, returns the current seed.
• hammersley_seed_set.m, sets the current seed.
• hammersley_sequence.m, computes the next N elements of the Hammersley sequence, starting at the current seed, in the current base.
• hammersley_step_get.m, returns the step of the leaped Hammersley subsequence.
• hammersley_step_set.m, sets the step of the leaped Hammersley subsequence.
• i4_to_hammersley.m, computes the SEED-th element of the Hammersley sequence with the given BASE vector.
• i4_to_hammersley_sequence.m, computes the next N elements, starting at SEED, of the Hammersley 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.
• r8_epsilon.m, returns the R8 roundoff unit.
• 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:

• hammersley_test.m, runs all the tests.
• hammersley_test_output.txt, the output file.
• hammersley_test01.m, tests I4_TO_HAMMERSLEY_SEQUENCE.
• hammersley_test02.m, tests I4_TO_HAMMERSLEY_SEQUENCE.
• hammersley_test03.m, tests I4_TO_HAMMERSLEY_SEQUENCE.
• hammersley_test04.m, tests I4_TO_HAMMERSLEY_SEQUENCE.
• hammersley_test05.m, tests I4_TO_HAMMERSLEY_SEQUENCE.
• hammersley_test06.m, tests HAMMERSLEY_SEQUENCE.
• hammersley_test07.m, tests HAMMERSLEY_WRITE.
• hammersley_test08.m, tests I4_TO_HAMMERSLEY_SEQUENCE.
• hammersley_04_00010.txt, a Hammersley dataset written to a file by one of the tests.

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