4 years 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.
4 years ago by FabHK
I think both the PCG family and the xoroshiro family are faster still.
4 years 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.
4 years ago by aDfbrtVt
There's a bunch of analysis written by the PCG folks bashing Xoroshiro as well [1]. I think that for most normal use cases with randomized state, Xoroshiro is quite good. It only requires a single 64b add which is amazingly efficient.
[1] https://www.pcg-random.org/posts/xoshiro-repeat-flaws.html
4 years 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?
4 years 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.
4 years ago by jhgb
Wouldn't a SIMDified implementation of other RNGs speed them up by a comparable factor, making MT relatively slower again?
4 years 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?
4 years ago by rainworld
4 years ago by jedimastert
I'm reminded of Chris Wellon's "Prospecting for Hash Functions", where he randomly generates hash functions and then runs them through a couple of tests.
https://nullprogram.com/blog/2018/07/31/
Out of curiosity, is running the state through a hash a reasonable rand strategy?
4 years ago by an1sotropy
The PCG author (Melissa O'Neill of Harvey Mudd) has an interesting story of how PCG and its paper came about https://www.pcg-random.org/posts/history-of-the-pcg-paper.ht... Good to read in case you think that academic peer review is the only way to introduce new and useful methods to the world.
4 years 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...?
4 years ago by Ayesh
Probably looking for this: https://en.m.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
4 years 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.
4 years ago by undefined
4 years 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.
4 years ago by jimktrains2
If you seed your random number generator, then it is reproducible.
4 years ago by miked85
Are you saying you want a reproducible random number generator?
4 years ago by jchook
The equivalence classes modulo some n form a partition of the integers so you can use that to create a very efficient solution with very little code.
Here is a neat explanation:
https://preshing.com/20121224/how-to-generate-a-sequence-of-...
If you need even better properties (eg cryptographically secure) you can also look at PCG with k-dimensional equidistribution:
4 years 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.
4 years ago by nestorD
From memory you don't need size to be a prime, what you need is that it is coprime with your step.
Thus, the easiest solution is to take a step-size that is prime and different from you size (that works for any size). Given the index of the current element, the next index would be `(current_index + step) % size`.
4 years ago by NotCamelCase
Have you looked up LFSRs yet? https://en.wikipedia.org/wiki/Linear-feedback_shift_register
They are quite efficient for both HW and SW implementations.
Daily digest email
Get a daily email with the the top stories from Hacker News. No spam, unsubscribe at any time.