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 ? 2 , 3 , and of a combined generator based on that LCG. The base LCG with the modulus 333 3 33 provides a quality sequence with the period ?3.7?1015, which passes all but two statistical tests from BigCrush test suite. We improved on the original implementation by adapting Barretts modular reduction method, which resulted in four-fold increase in efficiency. The combined generator has the period of ?1023 and passes all tests from BigCrush suite. Program title: BCNRandom Catalogue identifier: AEPG_v1_0 Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEPG_v1_0.html Program obtainable from: CPC Program Library, Queens University, Belfast, N. Ireland Licensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.html No. of lines in distributed program, including test data, etc.: 1201 No. of bytes in distributed program, including test data, etc.: 13715 Distribution format: tar.gz Programming language: C. Computer: IBM PC; MacBook Pro. Operating system: Windows 7, Linux, Unix, OS X. RAM: 512KB Classification: 4.13. Nature of problem: This is a fast pseudorandom number generator based on normal numbers, with long period and good statistical properties. It passes all 106 BigCrush statistical tests and is faster than C standard library rand generator. Suitable for parallel execution by multiple threads and/or processes because of skip ahead property. Solution method: Linear Congruential Generators with specially chosen parameters are used. A customized fast modular reduction is employed. Running time: Generation rate is 100200 million numbers per second.
normal numbers linear congruential generator random number generation