Fast generation of Faure sequences with a b-ary Gray code
This page is related to Eric Thiémard's 1998 paper Economic generation of low-discrepancy sequences with a b-ary Gray code (133 Ko). In the course of the refering process, it appeared the core of this paper was not new. The key idea was already published in a book by S. Tezuka: Uniform Random Numbers: Theory and Practice, 1995, Kluwer Academic Publishers, Boston.
Abstract: A (t,m,s)-net in base b is a set of bm points distributed with high uniformity in the s-dimensional unit cube. Constructions of (t,m,s)-nets have been proposed among others by Sobol, Faure, and Niederreiter. It takes O(m2s) time to generate straightforwardly each point of such a net. Antonov and Saleev proposed a principle to generate each point of a (t,m,s)-net in base 2 in O(ms) time. We generalize this O(ms) method to the generation of (t,m,s)-nets in arbitrary base b. Our method is based on a b-ary Gray code. As an application, we present an implementation of a Faure sequence generator and compare its properties with other implementations of low-discrepancy sequence generators.
GrayFaure is a fast ANSI-C implementation of a Faure low-discrepancy sequence generator that can be freely downloaded from this page. The generated sequence is shuffled with a b-ary Gray code.
The package contains four files:
