Quasi-random numbers are sometimes preferred to pseudo-random numbers because they are more uniformly distributed over the interval (0,1). The availability of open-source low discrepancy sequence generators over the Internet, however, is very scarce, especially when compared with the rather large number of applications which claim to make use of such techniques.
Among quasi-random numbers, the Halton sequence is perhaps the easiest to translate into computer language: basically, a number gets converted to binary form, "reflected", and brought back to base 10; dimensionality can be achieved by using a radix other than 2, chosen among prime numbers. The following Java code was written with the objective of clarity in mind, rather than speed, and it can be easily converted into a variety of other languages, C++ in primis.
Download: HaltonSequence.zip
/*
* @(#)HaltonSequence.java 1.0 30 November 2002
*
* (C) Copyright Carlo Vicentini, 2002 - All Rights Reserved
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
public class HaltonSequence {
/**
* Assert whether the argument is a prime number.
* @param number the number to be checked
*/
private static final boolean isPrime(int number) {
boolean isIt = true;
for(int i = 2; i < number; i++) {
if(number % i == 0) {
isIt = false;
break;
}
}
if(number == 2) {
isIt = false;
}
return isIt;
}
/**
* Find the nth prime number.
* @param index the ordinal position in the sequence
*/
private static final int findPrime(int index) throws Exception {
if(index < 1) {
Exception exception = new Exception("The argument must be non-negative.");
throw exception;
}
int prime = 1;
int found = 1;
while(found != index) {
prime += 2;
if(isPrime(prime) == true) {
found++;
}
}
return prime;
}
/**
* Returns the nth number in the sequence, taken from a specified dimension.
* @param index the ordinal position in the sequence
* @param dimension the dimension
*/
public static final double getNumber(int index, int dimension) throws Exception {
int base = findPrime(dimension);
if(base == 1) {
base++; //The first dimension uses base 2.
}
double remainder;
double output = 0.0;
double fraction = 1.0 / (double)base;
int N1 = 0;
int copyOfIndex = index;
if(base >= 2 & index >= 1) {
while(copyOfIndex > 0) {
N1 = (copyOfIndex / base);
remainder = copyOfIndex % base;
output += fraction * remainder;
copyOfIndex = (int)(copyOfIndex / base);
fraction /= (double)base;
}
return output;
}
else {
Exception exception = new Exception("Error generating Halton sequence.");
throw exception;
}
}
}