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

11–20 of 56 posts

Re: Evolution of Random Number Generators

#11

Post by nightcracker »

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.

You can construct arbitrarily-sized permutations with log(n) time random access using Sometimes-Recurse Shuffle: https://eprint.iacr.org/2013/560.pdf.

Re: Evolution of Random Number Generators

#12

Post by resolvent »

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.

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.

Re: Evolution of Random Number Generators

#13

Post by matsemann »

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)` ?

Having an unstable comparator might wreak havoc and maybe not give a proper distributed space of possible results?

Edit: yes, here is an example (in the comments) of how biased this is: https://stackoverflow.com/a/18650169/923847

Re: Evolution of Random Number Generators

#14

Post by vince14 »

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…

https://news.ycombinator.com/item?id=25497357

Re: Evolution of Random Number Generators

#15

Post by Ayesh »

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…

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

Re: Evolution of Random Number Generators

#16

Post by SuchAnonMuchWow »

FabHK wrote: post #8
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.

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 ?

Re: Evolution of Random Number Generators

#17

Post by jamespwilliams »

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’re using Go, you can use rand.Perm (https://golang.org/pkg/math/rand/#Perm), which uses a Fisher-Yates shuffle under the hood.

Re: Evolution of Random Number Generators

#18

Post by TekMol »

Ayesh wrote: post #15
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…

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.

Re: Evolution of Random Number Generators

#19

Post by johndough »

resolvent wrote: post #12
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.

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 and reject all random values which are smaller than `n`, but that introduces unpredictable latency and destroys the cool jump-ahead feature.

Re: Evolution of Random Number Generators

#20

Post by NotCamelCase »

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…

Have you looked up LFSRs yet? https://en.wikipedia.org/wiki/Linear-feedback_shift_register

They are quite efficient for both HW and SW implementations.

Post reply on HN