What's the significance of 4294967087 as an argument limit to Racket's (random) function?

Question

When generating random integers in Racket using the random function, Racket requires the argument to be a number between 1 and 4294967087. I was just wondering, where does that 4294967087 number come from, and why is it the maximum random number that Racket can generate?

It's close, but not exactly equal, to the maximum value of an unsigned 32-bit integer (4294967295). I assume there must be some reason why such a specific number was chosen?

Pelton

Answer 1

It is the largest safe prime that is still smaller than 2³²-1. It is part of the original implementation of the MRG32k3a algorithm by Pierre L'Ecuyer.

The significance of this number is explained in his paper "Good Parameter Sets for Combined Multiple Recursive Random Number Generators", which is available on the papers website of L'Ecuyer (as a postscript file), and as a PDF at http://pubsonline.informs.org/doi/abs/10.1287/opre.47.1.159 . The reference implementation of the MRG32k3a algorithm is also available there: http://www.iro.umontreal.ca/~lecuyer/myftp/papers/combmrg2.c

In this paper, L'Ecuyer analyzed multiple recursive random number generators and did exhaustive searches for parameter sets that caused the generators to have desirable properties: Long period, good distribution of numbers, efficient implementation...

The value in question (which is referred to as 2³¹-209 in the paper) is part of a parameter set of the MRG32k3a algorithm that has these properties.

_{(but admittedly, I didn't do the maths...)}

Stouthearted

For comparison: github.com/racket/srfi/blob/master/srfi-lib/srfi/27/… – Dunkirk

Answer 2

It is the largest safe prime less than 2^32. They use this number because that gives their pseudo-random number generator the largest possible period.

A safe prime number p is a prime for which (p - 1)/2 also is prime. This other prime is called a Sophie Germain prime.

Schoenfelder