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

21–30 of 56 posts

Re: Evolution of Random Number Generators

#21

Post by resolvent »

johndough wrote: post #19
resolvent wrote: post #12

Earlier quoted context omitted.

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

The value `a` has to fulfill some more properties: https://en.wikipedia.org/wiki/Linear_congruential_generator#... 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…

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]

Re: Evolution of Random Number Generators

#22

Post by e12e »

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.

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?

r would need to be in the range 1..n!

Re: Evolution of Random Number Generators

#23

Post by jchook »

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…

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:

http://www.pcg-random.org/index.html

Re: Evolution of Random Number Generators

#24

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

Re: Evolution of Random Number Generators

#25

Post by jimktrains2 »

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.

If you seed your random number generator, then it is reproducible.

Re: Evolution of Random Number Generators

#26

Post by FabHK »

midjji wrote: post #24

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, i…

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

Re: Evolution of Random Number Generators

#27

Post by jlouis »

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 thus it generates the whole group in p steps.

Re: Evolution of Random Number Generators

#28

Post by rurban »

midjji wrote: post #24

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, i…

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

Re: Evolution of Random Number Generators

#29

Post by FabHK »

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 ?

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

Re: Evolution of Random Number Generators

#30

Post by Someone »

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 number), but the above should already be bad enough to drop that idea.

Post reply on HN