As all of them are also faster than old school rand, its worth upgrading for the performance increase if nothing else.
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.
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.
Out of curiosity, is running the state through a hash a reasonable rand strategy?
Say it is initialized with "size=5" then it might output:
Is there something like this?
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...?
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.
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.
Fisher-Yates is one of the simplest
things out there IMO
Here is a neat explanation:
If you need even better properties (eg cryptographically secure) you can also look at PCG with k-dimensional equidistribution:
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.
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`.
They are quite efficient for both HW and SW implementations.
Yes, when initialized with "size=5" the numbers in the output must be precisely 1,2,3,4,5 but in random looking order.
And I don't want to store the whole sequence. I want to say gimmeTheNumberAtPosition(x) and it return just that number.
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:
In other words, good old Fisher Yates, storing the resulting permutation, and a simple lookup is probably the way to go.
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?
r would need to be in the range 1..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.
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]
Edit: yes, here is an example (in the comments) of how biased this is: https://stackoverflow.com/a/18650169/923847
The Fisher–Yates shuffle is the right way to shuffle an array in an unbiased way.
- 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.
if your n isn’t a power of two,
it may produce numbers larger
The others are not such big problems as I don't need strong resemblence to real randomness.
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.
There is no adversary. The use case is not about security.
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;