Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Evolution of Random Number Generators

johndcook.com

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Evolution of Random Number Generators

#41

Post by HelloNurse »

SuchAnonMuchWow wrote: post #16
FabHK wrote: post #8

Earlier quoted context omitted.

Generating 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 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 he…

Storing 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 ?

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.

Re: Evolution of Random Number Generators

#42

Post by miked85 »

TekMol wrote: post #18
Ayesh wrote: post #15

Earlier quoted context omitted.

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

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.

Are you saying you want a reproducible random number generator?

Re: Evolution of Random Number Generators

#43

Post by rainworld »

galangalalgol wrote: post #33
rurban wrote: post #28

Earlier quoted context omitted.

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

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

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

Re: Evolution of Random Number Generators

#44

Post by anderskaseorg »

ascar wrote: post #38
TekMol wrote: post #2

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) a…

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. y…

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 ….

Re: Evolution of Random Number Generators

#45

Post by anderskaseorg »

kinos wrote: post #9
TekMol wrote: post #6

Earlier quoted context omitted.

Ah 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.

for JS you can probably just do `[...Array(n).keys()].sort(()=>Math.random() - 0.5)` ?

That is exactly the algorithm that Microsoft used to bias its purportedly random “browser choice” screen. Don’t use it.

https://www.robweir.com/blog/2010/02/microsoft-random-browse...

The Fisher–Yates shuffle is the right way to shuffle an array in an unbiased way.

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Re: Evolution of Random Number Generators

#46

Post by CipherThrowaway »

TekMol wrote: post #6
thewakalix wrote: post #5

Earlier quoted context omitted.

What 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?

Ah 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.

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.

https://web.cs.ucdavis.edu/~rogaway/papers/subset.pdf

Re: Evolution of Random Number Generators

#47

Post by nestorD »

jlouis wrote: post #27
TekMol wrote: post #2

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) a…

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 thu…

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`.

Re: Evolution of Random Number Generators

#48

Post by aDfbrtVt »

ufo wrote: post #39
FabHK wrote: post #26

Earlier quoted context omitted.

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

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.

[1] https://www.pcg-random.org/posts/xoshiro-repeat-flaws.html

Re: Evolution of Random Number Generators

#49

Post by TekMol »

jhgb wrote: post #36
TekMol wrote: post #18

Earlier quoted context omitted.

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.

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.

    Fisher-Yates is one of the simplest
    things out there IMO
Just using "$n xor $something" would be simpler. I am just not sure yet, what a good "$something" is.

Re: Evolution of Random Number Generators

#50

Post by TekMol »

Someone wrote: post #30
TekMol wrote: post #2

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) a…

Xoring 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 numb…

    if 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.

Post reply on HN