7 ms·
Evolution of Random Number Generators
- TekMol 5y agoI 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...?
- thewakalix 5y agoAre you talking about generating a random permutation?
- TekMol 5y agoI don't think so. Maybe a "random sequence" could be a name for it. But not sure.
- thewakalix 5y agoWhat I mean is, in your example, do you need to have precisely the numbers 1, 2, 3, 4, and 5, but in any order? Or is the constraint something else?
- TekMol 5y agoAh yes, you are right. In that sense, it is a random permutation of the numbers from 1 to max. 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.
- FabHK 5y agoGenerating random permutations is quite a different problem from creating random numbers. The standard algo for random permutations is the Fisher-Yates Shuffle. https://en.wikipedia.org/wiki/Fisher–Yates_shuffle https://en.wikipedia.org/wiki/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: https://stackoverflow.com/questions/29236556/how-can-i-calculate-n-th-permutation-or-tell-the-lexicographic-order-of-a-given https://stackoverflow.com/questions/29236556/how-can-i-calcu...
- SuchAnonMuchWow 5y agoStoring a number of the order of magnitude of n! will take the same amount of memory than storing a permutation of n elements, so what's the point ?
- FabHK 5y agoGood point. Storing a number of magnitude n! will take n log n bits, and storing n numbers up to n will also take n log n bit. In other words, good old Fisher Yates, storing the resulting permutation, and a simple lookup is probably the way to go.
- HelloNurse 5y agoIf 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.
- kinos 5y agofor JS you can probably just do `[...Array(n).keys()].sort(()=>Math.random() - 0.5)` ?
- wizeman 5y agoLook into linear feedback shift registers, they are very simple and can produce random-looking permutations.
- vince14 5y agohttps://news.ycombinator.com/item?id=25497357 https://news.ycombinator.com/item?id=25497357
- Ayesh 5y agoProbably looking for this: https://en.m.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.m.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- TekMol 5y agoThis 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.
- jimktrains2 5y agoIf you seed your random number generator, then it is reproducible.
- jhgb 5y agoFisher-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.
- deleted 5y ago[deleted]
- miked85 5y agoAre you saying you want a reproducible random number generator?
- jamespwilliams 5y agoIf you’re using Go, you can use rand.Perm (https://golang.org/pkg/math/rand/#Perm https://golang.org/pkg/math/rand/#Perm), which uses a Fisher-Yates shuffle under the hood.
- NotCamelCase 5y agoHave you looked up LFSRs yet? https://en.wikipedia.org/wiki/Linear-feedback_shift_register https://en.wikipedia.org/wiki/Linear-feedback_shift_register They are quite efficient for both HW and SW implementations.
- jchook 5y agoThe 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-unique-random-integers 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: http://www.pcg-random.org/index.html http://www.pcg-random.org/index.html
- jlouis 5y agoIf 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.
- nestorD 5y agoFrom 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`.
- Someone 5y agoXoring won’t work: - 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.
- TekMol 5y agoif your n isn’t a power of two, it may produce numbers larger than n This is the biggest problem. The others are not such big problems as I don't need strong resemblence to real randomness.
- Someone 5y agoI 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.
- TekMol 5y agoAlterning odd and even numbers is fine. There is no adversary. The use case is not about security.
- ascar 5y agoIf 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.
- anderskaseorg 5y agoYour 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 ….
- amitp 5y agoYes, 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 http://pcgworkshop.com/archive/mawhorter2019anarchy.pdf [2]: https://github.com/solsword/anarchy https://github.com/solsword/anarchy
- midjji 5y agoRecently 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.
- FabHK 5y agoI think both the PCG family and the xoroshiro family are faster still. https://prng.di.unimi.it https://prng.di.unimi.it https://www.pcg-random.org https://www.pcg-random.org ETA: https://github.com/lemire/testingRNG https://github.com/lemire/testingRNG
- ufo 5y agoDoes 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.
- aDfbrtVt 5y agoThere'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 https://www.pcg-random.org/posts/xoshiro-repeat-flaws.html
- rurban 5y agoMT 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 https://rurban.github.io/dieharder/QUALITY.html
- 5y ago
- jedimastert 5y agoI'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/ https://nullprogram.com/blog/2018/07/31/ Out of curiosity, is running the state through a hash a reasonable rand strategy?
- an1sotropy 5y agoThe 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.html 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.