Efficient implementation of Bailey and Borwein pseudo-random number generator based on normal numbers

摘要

This paper describes an implementation of a Linear Congruential Generator (LCG) based on the binary representation of the normal number 2_(,3), and of a combined generator based on that LCG. The base LCG with the modulus 3~(33) provides a quality sequence with the period ≈3.7?10 ~(15), which passes all but two statistical tests from BigCrush test suite. We improved on the original implementation by adapting Barrett's modular reduction method, which resulted in four-fold increase in efficiency. The combined generator has the period of ≈10~(23) and passes all tests from BigCrush suite.