peteroupc.github.io

A Note on the Bays–Durham Shuffle

The Bays–Durham shuffle extends a pseudorandom number generator’s (PRNG) maximum cycle length by giving it a bigger state. Generally, for a size of tablesize, this maximum is at most the factorial of tablesize, which is about the number of ways to arrange a list of size tablesize.

The following describes the Bays–Durham shuffle with a size of tablesize. (C++’s shuffle_order_engine implements something similar to the shuffle described below.) For PRNGs that output 32- or 64-bit integers 0 or greater, a tablesize of 256, 512, or 1024 is suggested.

The following variant of the Bays–Durham shuffle was used in the Kybos PRNG by J. Baagøe: