A Pseudo-Random Number Generator Based on Normal Numbers

[摘要] 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 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{sup -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.

[发布日期] 2004-12-31 [发布机构] Lawrence Berkeley National Laboratory

[关键词] Pseudo-Random Number Generation Normal Numbers;Randomness;Mathematics Pseudo-Random Number Generation Normal Numbers;Computer Codes;99 General And Miscellaneous//Mathematics, Computing, And Information Science