Evolution of Random Number Generators

4 hours ago by midjji

Recently noted that mt19937, mt19937_64 are much faster than the standard c++ random generator. They are also possibly better with regards to number distribution, but the performance difference is gigantic on clang. The standard 32 bit std::default_random_generator is almost 40x slower than the 64 bit mt19937_64 one across the board, from -o1 to -O3 march... etc.

As all of them are also faster than old school rand, its worth upgrading for the performance increase if nothing else.

3 hours ago by FabHK

I think both the PCG family and the xoroshiro family are faster still.

https://prng.di.unimi.it

https://www.pcg-random.org

ETA: https://github.com/lemire/testingRNG

an hour ago by ufo

Does anyone know what's the current consensus about PCG vs xoroshiro. I remember that the xoroshiro author had several complaints about PCG but I don't know ifhe is right or if he was just being salty.

3 hours ago by rurban

MT is pretty slow. There are fast variants (SFMT), but why use that when can have much better and much faster rngs?

https://rurban.github.io/dieharder/QUALITY.html

2 hours ago by ascar

I don't know about all the other RNGs in this benchmark, but MT prepares a dense/contiguous array of random numbers. The whole computation can be SIMDified (often even by the compiler), but extraction is (unless changed explicitly) a single copy of a double.

If RNG speed matters and you need a lot of random numbers in succession (and I assume these two assumptions correlate strongly) editing MT to directly pull 4 or even 8 random numbers at once (i.e. a `__m256 rand_m256()` interface) is a huge performance gain.

wyrand (the top spot of the linked benchmark), doesn't have this benefit. The computation can't be SIMDified and the extraction is always a single value.

So I would take these benchmark with a grain of salt and take a closer look at the specific situation for any application where RNG speed really matters.

2 hours ago by jhgb

Wouldn't a SIMDified implementation of other RNGs speed them up by a comparable factor, making MT relatively slower again?

2 hours ago by galangalalgol

Very useful! Thanks! Aren't there AES related intrinsics for some architectures that can be really fast for rng? How do they compare?

15 minutes ago by rainworld

https://github.com/google/randen#performance

8 hours ago by TekMol

I am looking for a simple random number generator that fills a given amount of slots.

Say it is initialized with "size=5" then it might output:

3,5,2,1,4

Is there something like this?

It does not need much statistical resemblence to randomness. Just look kind of random to the eye. And the code should be short. A few lines of Javascript or so.

Maybe one approach might be to just loop through the sequence (1,2,3,4,5) and xor the number with some other number? Maybe with 0101010...?

7 hours ago by Ayesh

Probably looking for this: https://en.m.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

5 hours ago by TekMol

This seems to use an external random number generator.

I want the code to be complete and reproducible. So gimmeTheNumberAtPosition(x) will always return the same for the same x.

Also, FYShuffle is much more complex than I would like the algo to be.

21 minutes ago by miked85

Are you saying you want a reproducible random number generator?

3 hours ago by undefined

[deleted]

2 hours ago by jhgb

Fisher-Yates is one of the simplest things out there IMO.

Isn't the Lehmer code the thing that you want? Then you can specify your permutation with an integer and extract the individual digits from it repeatedly.

3 hours ago by jimktrains2

If you seed your random number generator, then it is reproducible.

3 hours ago by jlouis

If size is a prime, repeated multiplication on a generator element (any element) will work if you compute `mod p`. But it's not going to have nice random properties for the most part. It's just a "permutation".

The reason it works is because the subgroup order generated by the element has to be divisible in the group order. There's only 1 and p. So unless it's trivial (i.e., the element 1), it's going to be p and thus it generates the whole group in p steps.

an hour ago by amitp

Yes, xor can be used as part of this — see the paper[1] and code[2]. The idea is that you're generating a random shuffle of a sequence, but you can do it in a way that doesn't require storing the entire shuffled sequence. You can ask "what's in position 4" and it will return "item 1".

[1]: http://pcgworkshop.com/archive/mawhorter2019anarchy.pdf [2]: https://github.com/solsword/anarchy

2 hours ago by ascar

If you want a simple pseudo random sequence of N that just looks random (pseudocode):

  int start = getRandomInt(seed) % N;
  double k = N / 1.618;
  k = k % 2 == 0 ? k - 1 : k; // k and N must be coprime
  int nextElement = k * start % N;
  start++;

This will jump wildly across your sequence and visit all elements (as k and N are chosen coprime). No need to store a full array. Is it statistically random? Of course not, e.g. you will never see two values close to each other right after another.