New Multiply-with-Carry Random Number Generators

Abstract

We propose a new set of very fast and reliable random number generators based on a multiple linear congruence with carry. This type of recurrence is very fast because using a carry in the recurrence permits one to use arithmetic modulo a power of 2 without compromising the quality. It has been studied already in the past, but not yet fully exploited to develop fast and reliable generators based on a mathematical analysis of their multivariate structure. We have done that. Our new generators can produce up to two billion uniform random numbers per second on a laptop with 64-bit CPU.