# Halton sequence principle and code implement

Halton Sequence is a random sequence that is used to generate a random number of evenly distributed. The most commonly used place is the Monte Carlo algorithm. Because I was studying the MapReduce algorithm recently, I learned about Halton Sequence when looking at PI’s calculation implementation, but I was surprised to find that Google couldn’t find much introduction. I don’t know if anyone has used it anymore. Anyway, Hadoop calculated PI, so I know it.

Halton Sequence is often used to select uniform random points in space. But in fact, I understand that it is not a random selection algorithm, because it emphasizes the average, which is to make the selected points accurately and evenly distributed in the space through a certain algorithm.

## algorithm The

Halton algorithm is not difficult, that is, select a quality number as the base, and then cut the division to form some unique and uniform points. The coordinates of each point are between 0 ~ 1.

For example, on a one -dimensional axis, take 2 as the base. Then first cut the division (0,1) to get 1/2; then cut the division of (0,1/2) and (1/2,1), get 1/4 and 3/4; then (0,1/4), (1/4, 1/2), (1/2, 3/4), and (3/4,1) to cut points … the final number of the number is::

12143418583878116916,…

The same reason, the number obtained by the 3 as the base is:

1323194979295989127,…

## implementation The principle of

algorithm is not difficult, but the implementation of programming is not so simple. At least I observed for a long time and did not find how this group should be achieved quickly, and the pseudo code on the wiki was too rough, I couldn’t understand it. After checking it for a long time, I found a simple explanation, pondered it, and now shared it:

To take the nn number:

• first turns n to the number of B in -order, where B is the specified base.
• and then turn the conversion numbers to the decimal point, and convert it into a decimal.
• Finally, turn this B into a decimal number.

For example, with 2 as the base, take the sixth number, first transform to the number of two -proof to 110. Then turn 110 to the decimal point and become 0.011, which is the binary number. Then transform the binary 0.011 into decimal, that is, 0.5*0 + 0.25*1 + 0.125*1 = 0.375. So the sixth number is 0.375.

here is actually very clear. We merge the first and second steps, and::

Number N number = harmony {B in advance * Each person’s in -depth secondary side}

For example, the 6th number of 2 as a base above (110):

= 1 * 1/2^2 + 1 * 1/2^1 + 0*1/2^0.

## code

Below is the Java code implementation of the two -dimensional Halton Sequence. The base number can be specified by yourself:

``````<span style="font-family:Courier New;font-size:14px;">public class HaltonSequence {
static int digit = 40;
private int[] bases= new int;
private double[] baseDigit = new double;
private double[][] background = new double[digit];
private long index;

HaltonSequence(int[] base) {
bases = base.clone();
index = 0;

for(int i=0; i<bases.length; i++) {
double b = 1.0/bases[i];
baseDigit[i] = b;
for(int j=0; j<digit; j++) {
background[i][j] = j == 0 ? b : background[i][j-1]*b;
}
}
}

double[] getNext() {
index++;

double[] result = {0,0};

for(int i=0; i<bases.length; i++) {
long num = index;
int j = 0;
while(num != 0) {
result[i] += num % bases[i] * background[i][j++];
num /= bases[i];
}
}

return result;
}

public static void main(String[] args) {
int[] base = {2,5};
HaltonSequence test = new HaltonSequence(base);
for(int x = 0; x < 100; x++){
double[] t = test.getNext();
System.out.println(t + "\t" + t);
}

}
}</span>``````

source