Halton Sequence | Hacker News Reader

Halton Sequence

en.wikipedia.org

47 pointsibobev9 comments

I don't know why this caught HN's attention today, but I first found out about the Halton sequence a number of years ago when I needed a random seeming, regularly distributed and stable set of 2D points to sample an image, and the Halton sequence fit the bill precisely.

After implementing and benchmarking it I found my code was spending more time calculating the sample points than I'd like. When trying to speed that up I found this paper: https://www.sciencedirect.com/science/article/pii/0898122193...

Later when learning Rust I ported that faster approach to Rust: https://crates.io/crates/halton

And when I wrote a Rust library to bind Rust to Ruby, I created a Rubygem of the same as a testbed: https://rubygems.org/gems/halton

A few years ago I also put together a fun D&D game using the Halton sequence to place items/encounters on a map.

https://extremelearning.com.au/unreasonable-effectiveness-of...

Also related is the occurrence of the golden ratio in nature:

https://www.wolframscience.com/nks/p411--growth-of-plants-an...

I love the halton sequence. Super useful in many situations.

I'm surprised Wikipedia describes it as "an example of a quasi-random number".

To me, the Halton Sequence answers the question:

In a given n-dimensional area, where is the most space left?

So if you want to fill an area in an optimal way (each point is placed in the middle of the largest empty area) you can do:

    10 I = 0
    20 POSITION = HALTON(I)
    30 DRAW_A_POINT(POSITION)
    40 I++
    50 GOTO 20

This is not only useful for graphical applications. But also to explore a search space for example. As long as you keep trying the next point in the halton sequence, your next try is always as far away from all previous tries as possible.

The Halton sequence doesn't always choose the place where there's the most space left, except in the 1D case. If you plot 2D Halton sequence samples, you'll see the occasional sample placed fairly close to another, even when there's available space nearby. (Not that it doesn't do a decent job of generally filling in the empty areas.) Individually, it always selects a point where the 1D axial projections go in one the largest gap, but that doesn't mean that they're always exactly in the middle, nor that they jointly are in the largest space.

An even simpler way than Halton for the 1D case, is to use the golden ratio. For that, you place sample j at (phi * j) mod 1.0, where phi is the golden ratio. (Or another way to think of it is to keep stepping forward from the last sample by phi with wrapping.) That really does always place each sample into the largest gap between all prior samples. You can use any irrational number as a multiplier and it will eventually sample the entire [0,1) space. But the golden ratio is optimal. See Kronecker sequences for the generalization to higher dimensions. (E.g., https://jcgt.org/published/0011/01/04/)

For higher dimensional sampling that really does try to place points in the middle of empty areas, have a look at Mitchel's "best candidate" algorithm (https://dl.acm.org/doi/10.1145/122718.122736).

That basically goes something like this:

    to place point j:
        randomly choose j * m points (i.e., the candidates; m is a constant)
        find the one farthest from all prior placed points
        select and place that as point j

It's slow and expensive, but it's designed precisely to try to find a large empty area and put a point in it, just as you mentioned. It's pretty general too, so you can do variations like computing the distances with toroidal wrapping, using non-Euclidean distance metrics, using any dimensional space you like, etc. It's also pretty common not to scale the number of candidates with j and just choose a constant number.

See also, Sobol sequences: https://en.wikipedia.org/wiki/Sobol_sequence

I used both in the Monte Carlo calculations for my PhD thesis back around 1990. Much better convergence than generic quasi-random numbers.

> Equivalently, the nth number of this sequence is the number n written in binary representation, inverted, and written after the decimal point

Shouldn't that be called the binary point? I would expect a decimal point to exist only in decimal notation...

Yep. More generally, "radix point."

Is there a rule of thumb for when to use Halton sequence, versus Poisson distributions, versus Sobol sequences, versus <insert 10,000 other random sequence algorithms) for Monte Carlo scenarios... or even general "I need to generate a random set of XY or XYZ points in space"?

Hell, I even see people use voronoi patterns to position points, which seems like overkill. Is it purely by choice/fascination?

It seems rather choose-your-own-poison, but wondering if there are any shorthand use-this-for-thats.

See also Weyl sequences for generating samples from a discrete uniform distribution.

https://en.wikipedia.org/wiki/Weyl_sequence

Reply on news.ycombinator.com