Random(ish) Number Generator

Go To Last Post
25 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Unlike most people who seem to want a true random number generator I need one with a few odd properties...

1) It generates an integer between 1 and N, where N is a variable between 1 and 384.

2) It generates each number once and only once.

3) It will generate every number between 1 and N if it is called N times.

It doesn't matter if each time it's run the same sequence comes out, execution time is not a major concern and I have plenty of flash space (but not enough to precompute every possible sequence).

Can anyone suggest anything?

Thanks.

#1 This forum helps those that help themselves

#2 All grounds are not created equal

#3 How have you proved that your chip is running at xxMHz?

#4 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand." - Heater's ex-boss

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What's wrong with rand()/random() then?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Google 'Fisher–Yates shuffle'

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Nice little project.
Create a table of elements 1..N. Use rnd() to pick an index into the table. Select the item there as your value. Remove the element from the table, slide all remaining elements down/up to remove the gap. Reduce N by one. Repeat until no elements remain.

--greg
Still learning, don't shout at me, educate me.
Starting the fire is easy; the hardest part is learning how to keep the flame!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

slide all remaining elements down/up to remove the gap

Sounds like a job for a linked list in fact.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
What's wrong with rand()/random() then?

Does that work?

My compiler's implementation of rand() generate a integer between 0 and 32767. Turn that into my desired range with rand() % 384 + 1 (for example) and there are multiple random numbers which map to the same number within my desired range, which violates my 2nd 'rule'.

I guess I could keep track of which numbers had already been generated and discard those.

The Fischer-Yates Shuffle looks very interesting.

#1 This forum helps those that help themselves

#2 All grounds are not created equal

#3 How have you proved that your chip is running at xxMHz?

#4 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand." - Heater's ex-boss

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Set a buffer of 384 bytes (or bits if you're short of RAM) to 0. Use rand() or any other generator to get an index into the buffer. If that buffer entry is 0, use the index (+1) as your random value and set the buffer entry to 1. If already 1, increment (or decrement) through the buffer until you find the first 0, then set it to 1 and return that index (+1). You'll have to account for wrap-around, of course. And deal with the situation where all numbers have been used (otherwise you'll loop forever looking for a 0).

Last Edited: Fri. Sep 23, 2011 - 06:57 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Brian Fairchild wrote:
I guess I could keep track of which numbers had already been generated and discard those.

This is pretty much what the FY shuffle does. Here is a C implementation, not tested on AVR!

#include 

/* Arrange the N elements of ARRAY in random order. */

void shuffle(int *array, size_t n)
{
  if (n > 1) {
    size_t i;
    for (i = 0; i < n - 1; i++) {
      size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
      int t = array[j];
      array[j] = array[i];
      array[i] = t;
    }
  }
}

Hope it helps.

Edit: kk6gm posted at exactly the same time as me, see above for a more efficient solution for an 8 bit mcu.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Fisher-Yates seems to be working quite nicely. I need to test it under all circumstances but so far it looks good. The end result will be seen by some 20,000 audience members next weekend plus a few 100,000 DVD sales so I need to get it right!

Thanks for the suggestions.

#1 This forum helps those that help themselves

#2 All grounds are not created equal

#3 How have you proved that your chip is running at xxMHz?

#4 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand." - Heater's ex-boss

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Find an 9 bit LSFR, that will generate all values from 1 to 511, and simply throw away any values that are over 384. Nice and simple, no list to keep track of.

Google for "maximal length LFSR" and pick a "set of taps".

John

Four legs good, two legs bad, three legs stable.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

With the FY shuffle, do remember that it is no better than the randomness generator you use for the shuffle. There are many ways to get it wrong, and they are not obvious. Also, once shuffled, the function is entirely deterministic.

http://www.youtube.com/watch?v=UN0LvFZMKq8 is a classic. TV2 in Denmark had a similar issue, I believe.

If you need a 'gambling quality' generator, make a 384-long list, and pick numbers out of it using a crypto-quality TRNG with 9 bit output. Try until successful, and shrink the list. Once the pool has 256 elements, you may drop the TRNG output to 8 bit, and so forth. With this method the pick is done when the function is called, and is not predictable even if you knew the state of the system at some earlier point.

/Kasper

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Also, once shuffled, the function is entirely deterministic.
Which is exactly what the OP asked for.

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Sounds like a job for a linked list in fact.
Actually, I was thinking of a gapless vector, no need to traverse a list, the rnd() function would always create a direct index. Quick, simple and efficient (Just the way I like things). The slide/shuffle could be handled with something as simple as a memcpy/mv etc. With appropriate seeding, you'd get a different result each run. It also addresses each of the OP's three requirements.

--greg
Still learning, don't shout at me, educate me.
Starting the fire is easy; the hardest part is learning how to keep the flame!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You can add any irreducible subgroup factor to generate all the elements of the set. 1 works if you have no problem with a monotonic increasing sequence. If N is prime any addition < N works modulo N. If N is not prime you need to add something relatively prime to N. N-1 works if you have no problem with a monotonic decreasing sequence. For an apparent uniform distribution pick a large non-factor multiple of a non-divisor of N.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

The slide/shuffle could be handled with something as simple as a memcpy/mv etc.

And my point was that with a linked list no memory moving is required.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
And my point was that with a linked list no memory moving is required.
Indeed, but my point was that with a linked list, the chain has to be traversed.

--greg
Still learning, don't shout at me, educate me.
Starting the fire is easy; the hardest part is learning how to keep the flame!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

@dak644

Thanks for the suggestion. I've actually been doing something similar. To date my N has always been even and I've been doing N/2 + 1 MOD N, which as you say does generate a maximal length sequence. The end result however fails my (unwritten until now) point 4.

4) It has to look good.

How on earth can a random sequence look good? Let me try to explain. Imagine that every value of N turns on one of N lights for 1 second and that those lights are arranged, in order, in a long row. To look 'random' I need a sequence which has no discernible 'movement', 'direction' or 'clustering'. All horribly vague terms but I hope you can deduce what I mean.

I am interested enough on the technique to experiment further though. Could you please expand on your statement...

Quote:

a large non-factor multiple of a non-divisor of N

My maths isn't quite strong enough to understand what you mean. I feel that there ought to be a solution that increases the apparent randomness of the result.

#1 This forum helps those that help themselves

#2 All grounds are not created equal

#3 How have you proved that your chip is running at xxMHz?

#4 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand." - Heater's ex-boss

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Brian Fairchild wrote:
My maths isn't quite strong enough to understand what you mean. I feel that there ought to be a solution that increases the apparent randomness of the result.

Apparent randomness, I consider to be something of a contradiction, it is either random or it is not and unfortunately a truly random sequence may appear to be perfectly well ordered. Consider that the likelihood of generating a linear sequence from 1 through 384 has just the same chance to occur as any other permutation.

The effect you are looking for is entirely subjective, the only thing I can suggest (given your example with lights) is to speed things up and run the generator until you find a sequence you are happy with. Save as many sequences as you have enough flash for then just pick one at random on each run.

KKP has made some valid points regarding the limitation of PRNGs. Relatively few of the pow(384, 384) permutations are actually possible (esp. true with Fisher-Yates).
One idea to increase possible perms would be to create the initial array statically so that you don't always start from a fresh deck on each shuffle, current state of the deck could even be held in eeprom between power cycles.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Apparent randomness, I consider to be something of a contradiction, it is either random or it is not and unfortunately a truly random sequence may appear to be perfectly well ordered. Consider that the likelihood of generating a linear sequence from 1 through 384 has just the same chance to occur as any other permutation.

Martin Gardner had a proof of the non-existence of true randomness in one of his great books which went along the line that say you were picking the digits 0..9 then if the sequence were truly random then you ought to pick each digit at a roughly equal frequency but if that were the case you'd be able to predict the likely outcome of a selection which wouldn't then be random.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
Martin Gardner had a proof of the non-existence of true randomness in one of his great books which went along the line that say you were picking the digits 0..9 then if the sequence were truly random then you ought to pick each digit at a roughly equal frequency but if that were the case you'd be able to predict the likely outcome of a selection which wouldn't then be random.

I believe some people use this principle to pick lottery numbers but I am pretty sure it does not improve their chances of winning one bit.
IMO the assumption that you ought to pick each digit at roughly equal frequency is wrong. Indeed it is theoretically possible to pick from 0..9 an infinite number of times and never get a 7 (for example).

Edit: Speaking of lotteries, I have kept the same 6 numbers since the uk national lotto started back in 1994 and have never had more than three numbers up. Now what are the chances of that? :(

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It basically uses the reason behind Fermat's little theorem http://en.wikipedia.org/wiki/Fermat%27s_little_theorem, if p is prime then for any a coprime with p, a^p = a mod p, i.e. multiplying a*a*a... p times gets you back to a, generating all the integers from 1 to p-1 if a is also prime.
For p=7, a=3, the sequence is 3 2 6 4 5 1 3
For p=383, a=3 it is 3 9 27 81 243 346 272 50 .. which does not look random. But using a large prime like the next one, a=397 gives 14 196 63 etc.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
and have never had more than three numbers up. Now what are the chances of that?
50/50. Either it is true, or, it is not ;)

BTW: this is the principal on which I 'still' play the lotto... either I get the jackpot, or, I don't.. 50/50! Pretty good odds to me ;)

--greg
Still learning, don't shout at me, educate me.
Starting the fire is easy; the hardest part is learning how to keep the flame!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I like random numbers so I tried something: Subjected the numbers from 0..2**n to reversible operations: xor, rotate, add. An amateurish low bit symmetric cipher. It sorta works, but sometimes the sequence has very obvious regularities: small and big numbers alternate. Dunno if you can make something with it.

Ohh, and you need to discard the numbers outside of your range.

Hmm, increasing ROUNDS to 50 appearently improved things.

edit: made code a bit nicer

License: public domain

Attachment(s): 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

maximax wrote:

Apparent randomness, I consider to be something of a contradiction, it is either random or it is not and unfortunately a truly random sequence may appear to be perfectly well ordered.

I quite agree. My need for a random sequence that 'looks good' flies in the face of probably every other use of random numbers.

I've seen somewhere that over 10,000 people take part in the UK lottery each week by playing the numbers 1,2,3,4,5,6 - can you imagine how they'll feel if those numbers do win to learn that their 'jackpot' will be around £400 and not the millions they imagine.

#1 This forum helps those that help themselves

#2 All grounds are not created equal

#3 How have you proved that your chip is running at xxMHz?

#4 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand." - Heater's ex-boss

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks to everyone who came up with suggestions. In the end I went with the in-place version of Fisher-Yates.

#1 This forum helps those that help themselves

#2 All grounds are not created equal

#3 How have you proved that your chip is running at xxMHz?

#4 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand." - Heater's ex-boss