Fast and Small Nonlinear Pseudorandom Number Generators for Computer Simulation



In this paper we present Tyche, a nonlinear pseudorandom number generator designed for computer simulation. Tyche has a small $128$-bit state and an expected period length of $2^{127}$. Unlike most nonlinear generators, Tyche is consistently fast across architectures, due to its very simple iteration function derived from ChaCha, one of today's fastest stream ciphers.

Tyche is especially amenable for the highly parallel environments we find today, in particular for Graphics Processing Units (GPUs), where it enables a very large number of uncorrelated parallel streams running independently. For example, $2^{16}$ parallel independent streams are expected to generate about $2^{96}$ pseudorandom numbers each, without overlaps.

Additionally, we determine bounds for the period length and parallelism of our generators, and evaluate their statistical quality and performance. We compare Tyche and the variant Tyche-i to the XORWOW and TEA$_8$ generators in CPUs and GPUs. Our comparisons show that Tyche and Tyche-i simultaneously achieve high performance and excellent statistical properties, particularly when compared to other nonlinear generators.


ChaCha, GPU, PRNG, random number generation, SIMD, Tyche, Tyche-i


Pseudorandom Number Generators


International Conference on Parallel Processing and Applied Mathematics, January 2011

PDF File

Cited by

Year 2015 : 1 citations

 L'Ecuyer, Pierre. "Random number generation with multiple streams for sequential and parallel computing." 2015 Winter Simulation Conference. 2015.

Year 2014 : 4 citations

 P. L'Ecuyer, B. Oreshkin, and R. Simard, ``Random Numbers for Parallel Computers: Requirements and Methods,'' Submitted to Mathematics and Computers in Simulation, 2014.

 S Schultz, Configurable Testbeds for Cloud Data Management Systems, Msc thesis, 2014.

 “PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation”, Melissa E. O'Neill, submitted to ACM Transactions on Mathematical Software.

 S Neves, F Araujo, Engineering Nonlinear Pseudorandom Number Generators, Parallel Processing and Applied Mathematics, 2014