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.
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.
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.
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.
If the next number depends on the previous number (like with wyrand and many others) it can't be simdified.
You could simdify computation with different seeds tho, which might be fine for many purposes. However at that point it's also a custom implementation with a different number sequence than the non-simd version, which isn't the case with a SIMDified MT.
Also xoshiro generators are enough cheaper than MT that even if you couldn't simdify it, you could keep 4 and get run the 4 together in SIMD to get 4 outputs way cheaper than 1 SIMD MT.
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.
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.
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...?
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.
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.
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`.
Generating random permutations is quite a different problem from creating random numbers. The standard algo for random permutations is the Fisher-Yates Shuffle.
ETA: As you don't want to store the permutation, you might want to pick a number randomly from 1 to n!, and then generate the permutation on the fly up to the desired element, using the techniques outlined here:
If one really wants to do it the slow and hard way, it's possible to compute a random permutation of n elements one element at a time with n bits of storage (less with fairly generic compression techniques): just remember the set of numbers that have been produced so far and sequentially pick one of the remaining ones.
You'll waste some combination of additional memory (for arithmetic decoding state) and random bits (for rejected samples), but materializing a large randomly permuted vector should be slower.
I guess you could predictably enumerate the permutations, so that you could lookup with parameters size/n, position/i, seed/r - where r is the permutation.
For size=1, all parameters are 1, and only result is 1.
For size 2, r can be 1 or 2, naming the permutations [1,2];[2,1] - and eg: rand_at(n=2,r=2,i=2) would return 2, but i=1, would return 2.
I'm not sure how I'd implement this - I suppose it might be possible to generate a predictable "walk" based on n/r/i?
But for sizes less than, say, a million i would think that a shuffled array would be easier?
What you want is a cipher from 1..N to 1..N. This problem is often approached as an encryption problem known as Format Preserving Encryption. The Sometimes Recurse Shuffle linked elsewhere in this thread is one solution but the most foundational and accessible paper on this is Black and Rogaway's "Ciphers with Arbitrary Domains" The Generalized Feistel Network (Method 3) is fast and easy to implement.
So you want a mapping of [1, n] to a permutation of [1, n] without having to generate the list [1, n] and shuffling it. An affine transformation modular n should work. Instead of [1, n], look at [0, n). Find a value `a` in [0, n) such that gcd(a, n) = 1 and pick a random integer b in [0, n). Then the `random` number at each position is `a * x + b mod n`.
This is simple and fast, but is not secure at all. You can solve for a, b by solving the linear congruence. It also does not generate every permutation of `n`. For n = 5, only 20 sequences can be found out of 5! = 120.
Since the "randomness" of the permutation is not that great, I was looking for something better, but could not find anything. The closest I got was https://en.wikipedia.org/wiki/Xorshift#xoshiro_and_xoroshiro which only works for powers of two. A workaround would be to choose the next larger power of two and reject all random values which are smaller than `n`, but that introduces unpredictable latency and destroys the cool jump-ahead feature.
The LCG is the improved extension which causes you to have to compute values x_0 = seed to x_n in order to calculate x_{n+1}. What I am talking about is just a mapping of index x -> f(x) which is what the OP seemed to have wanted. In that case, `a` only needs to be relatively prime. This cannot account for every permutation of n since the number of values relatively prime to n, the totient, has an upper bound of n, which is the possible values for a. The number of values for b is also n, so at most n^2 possible sequences are generated, which is less than n! for n > 3.
For example, with n = 5:
Let a = 3 and b = 2.
x = [0, 1, 2, 3, 4],
a * x = [0, 3, 6, 9, 12],
a * x + b = [2, 5, 8, 11, 14],
a * x + b mod n = [2, 0, 3, 1, 4]
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".
- xoring will only produce permutations that have period two, and every element will be part of a 2-cycle.
- if your n isn’t a power of two, it may produce numbers larger than n
The set of 2-cycles will have a lot of structure, too (for example, if your magic constant is even, all cycles will have either two even numbers or two odd numbers; if it is odd, all cycles will have an even and an odd number), but the above should already be bad enough to drop that idea.
I can’t look into your use case, but I’m not sure you realize how spectacularly bad xoring with a fixed value is as a way to generate a ‘random’ permutation.
For example, it will still alternate odd and even numbers.
Also, an adversary can derive the xor key from a single sample, and predict the entire sequence from it.
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.
Your algorithm fails to choose k and N coprime for about 19% of N, such as N = 6, 10, 14, 15, 25, 27, 35, 36, 45, 54, 55, 65, 66, 75, 84, 85, 90, 93, 95 ….
As all of them are also faster than old school rand, its worth upgrading for the performance increase if nothing else.