Fast and Small Nonlinear Pseudorandom Number Generators for Computer Simulation

Authors

Abstract

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.

Keywords

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

Subject

Pseudorandom Number Generators

Conference

International Conference on Parallel Processing and Applied Mathematics, January 2011

PDF File