Lawrence Berkeley National Laboratory
A Pseudo-Random Number Generator Based on Normal Numbers
- Author(s): Bailey, David H.
- et al.
In a recent paper, Richard Crandall and the present author established that each of a certain class of explicitly given real constants, uncountably infinite in number, is b-normal, for an integer b that appears in the formula defining the constant. A b-normal constant is one where every string of m digits appears in the base-b expansion of the constant with limiting frequency b^ -m . This paper shows how this result can be used to fashion an efficient and effective pseudo-random number generator, which generates successive strings of binary digits from one of the constants in this class. The resulting generator, which tests slightly faster than a conventional linear congruential generator, avoids difficulties with large power-of-two data access strides that may occur when using conventional generators. It is also well suited for parallel processing--each processor can quickly and independently compute its starting value, with the collective sequence generated by all processors being the same as that generated by a single processor.