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::

¹⁄₂, ¹⁄₄, ³⁄₄, ¹⁄₈, ⁵⁄₈, ³⁄₈, ⁷⁄₈, ¹⁄₁₆, ⁹⁄₁₆,…

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

¹⁄₃, ²⁄₃, ¹⁄₉, ⁴⁄₉, ⁷⁄₉, ²⁄₉, ⁵⁄₉, ⁸⁄₉, ¹⁄₂₇,…

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[2];
	private double[] baseDigit = new double[2];
	private double[][] background = new double[2][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[0] + "\t" + t[1]);
		}
		
	}
}</span>