I would like to have a function f(x) that gives good pseudo-random numbers in uniform distribution according to value x. I am aware of linear congruential generators, however these work in iterations, i.e. I provide the initial seed and then I get a sequence of random values one by one. This is not what I want, because if a want to get let's say 200000th number in the sequence, I have to compute numbers 1 ... 199999. I need a function that is given by one simple formula that uses basic operations such as +, *, mod, etc. I am also aware of hash functions but I didn't find any that suits these needs. I might come up with some function myself, but I'd like to use something that's been tested to give decent pseudo-random values. Is there anything like that being used?
3 Answers
You might consider multiplicative congruential generators. These are linear congruentials without the additive constant: Xi+1 = aXi % c for suitable constants a and c. Expanding this out for a few iterations will convince you that Xk = akX0 % c, where X0 is your seed value. This can be calculated in O(log(k)) time using fast modular exponentiation. No need to calculate the first 199,999 to get the 200,000th value, you can find it in something proportional to about 18 steps.
Actually, for LCG with additive constant it works as well. There is a paper by F. Brown, "Random Number Generation with Arbitrary Stride", Trans. Am. Nucl. Soc. (Nov. 1994). Based on this paper there is reasonable LCG with decent quality and log2(N) skip-ahead feature, used by well-known Monte Carlo package MCNP5. C++ post is here https://github.com/Iwan-Zotow/LCG-PLE63/. Further development if this idea (RNG with logarithmic skip-ahead) is pretty decent family of generators at http://www.pcg-random.org/
You could use a simple encryption algorithm that can encrypt the numbers 1, 2, 3, ... Since encryption is reversible, each input number will have a unique output. The 200000th number in your sequence is encrypt(key, 200000). Use DES for 64 bit numbers, AES for 128 bit numbers and you can roll your own simple Feistel cipher for 32 bit or 16 bit numbers.
