Foolproofing a randomizer

Hiya! First post after lurking around for a while, here goes!

I'm building a somewhat simple, random 'Hotkey Presser' by using a Teensy (which mimics a USB keyboard) and the Arduino programming environment. Basically, I'm imitating this guy: http://blog.makezine.com/archive/2011/04/the-awesome-button.html, but I've replaced his words by letters and numbers and added some more input buttons. Here's the code:

// Defining first category of random keys (letters)
const byte randomLetters = 20;
char* letters[randomLetters] = {
  "a", "b", "c", "d", "e", "f", "g", "h", "i", 
  "j", "k", "l", "m", "n", "o", "p", "q", "r",
  "s", "t" };
  
// Defining second category of random keys (numbers)
  const byte randomNumbers = 10;
char* numbers[randomNumbers] = {
  "1", "2", "3", "4", "5", "6", "7", "8", "9", "0"};
  
// Hello buttons, we will use you. Ha! 
int button1 = 0;
int button2 = 1;
int button3 = 2;


void setup(){
  Serial.begin(9600);
  randomSeed(analogRead(0));
  pinMode(button1,INPUT_PULLUP);
  pinMode(button2,INPUT_PULLUP);
  pinMode(button3,INPUT_PULLUP);
  delay(500);
}


void loop (){
  if(digitalRead(button1) == LOW)  //read buttonpress on button1

  {
   //generate a random letter, print it to the Mac:
    Keyboard.print(letters[random(0,randomLetters)]); 
    Keyboard.print("");
    
    delay(300); //little delay so we only get 1 letter at a time
  }
  

if(digitalRead(button2) == LOW) //read buttonpress on button2

  {
    //generate a random letter, print it to the Mac
    Keyboard.print(letters[random(0,randomLetters)]);
    Keyboard.print("");
    delay(300);
  }
  

if(digitalRead(button3) == LOW) //read buttonpress on button3
  {
   //generate a random number, print it to the Mac
    Keyboard.print(numbers[random(0,randomNumbers)]);
    Keyboard.print("");
    delay(300);
  }  
}

That works fine and all, but I need a little more functionality. For example, it should not be possible for two exactly the same letters to show up right after another (aa, bb, etc.). So I think this is what it needs to do:

1 - After randomizing, check if the current 'random result' matches the previous random result.
2 - If so, randomize and check again.
3 - If not, print the result, but remember it so we can compare the next result with it.

I was thinking of making oldResult and currentResult variables and somehow fill them with whatever the randomfunction gave and gives, but I miss the code knowhow to actually do this without getting quite a lot of errors. So could anybody help me out a little? : 0

Thanks in advance!

char oldResult = 0;

void loop ()
    {
    char currentResult;

    if(digitalRead(button1) == LOW)  //read buttonpress on button1

       {
   //generate a random letter, print it to the Mac:
    
    do {
        currentResult = letters[random(0,randomLetters)];
        } while (currentResult == oldResult);
    oldResult = currentResult;
    Keyboard.print(currentResult); 
    Keyboard.print("");
    
    delay(300); //little delay so we only get 1 letter at a time
  }
  

if(digitalRead(button2) == LOW) //read buttonpress on button2

  {
    do {
        currentResult = letters[random(0,randomLetters)];
        } while (currentResult == oldResult);
    oldResult = currentResult;
    Keyboard.print(currentResult); 
    Keyboard.print("");
    delay(300);
  }
  

if(digitalRead(button3) == LOW) //read buttonpress on button3
  {
   //generate a random number, print it to the Mac
    do {
        currentResult = numbers[random(0,randomNumbers)];
        } while (currentResult == oldResult);
    oldResult = currentResult;
    Keyboard.print(currentResult); 
    Keyboard.print("");
    delay(300);
  }  
}

Wow, thanks John! I get the logic in the Do - While loop, however there's an error saying there's an invalid conversion from 'char*' (coming from the 'letters' and 'numbers' arrays I guess) to a 'char' in the following line:
currentResult = letters[random(0,randomLetters)];

Is that something I should fix in the arrays part or in the loop part?

Edit: added the '*' to both the char currentResult and char oldResult. It works like a charm now! Thanks again : )

Oops.. I wasn't expecting character strings because you were dealing with individual characters. You did the right thing by changing the two variables to character pointers.

That works fine and all, but I need a little more functionality. For example, it should not be possible for two exactly the same letters to show up right after another (aa, bb, etc.).

If you filter such combination out, it is strictly speaking not really random (with dices you throw the same value also 1 in 6) . Can you tell the rationale behind this requirement?

Another way to solve the double letters is just take the next char:

currentResult = letters[random(0,randomLetters)];
if (currentResult == oldResult) currentresult = ( currentresult +1 ) % randomLetters;

The advantage over the while loop is that the if construct is 100% deterministic as it cannot get stuck in the while loop. In theory the while loop can iterate multiple times as a random generator might generate the same number multiple times. This chance however is very small : order (1/randomLetters) ^ n where n is the number of iterations.

PSneep:
For example, it should not be possible for two exactly the same letters to show up right after another (aa, bb, etc.).

Yes, OK, but I warn you that if you try to "improve the randomizer" you are making it less random (as robtillaart said).

As an extreme example, say you did coin tosses but you said "it should not be possible for two exactly the same letters to show up right after another", so you never get head/head or tail/tail. OK so what must you always get? head/tail/head/tail/head/tail

So it isn't at all random. But you reply "I didn't mean that", but you say "I don't mind head/head as long as I don't get head/head/head". Well that still means that if you force a "tail" after two heads, it is completely predictable. As soon as you see two heads you know the next result must be a tail.

Mind you, I have heard of some MMO games filtering their randomizers to make things "look random". For example, in a dungeon, if one person wins all the loot rolls, it might be random, but it doesn't "look random". So sometimes they impose corrections on the random generator results so they don't get heaps of complaints the next day.

You could use analogRead() to seed the randomizer; this will use "noise" to create the seed.

You could use analogRead() to seed the randomizer; this will use "noise" to create the seed.

That assumes you're not using the analogue inputs for something else.
And that you've got a nice long antenna on the unused input you're using for randomisation.

I don't see any reason why "avoid repeats" and "good randomizer" have to be mutually exclusive - the shuffle functions on e.g. CD/MP3 players are random enough for all intents and purposes, but won't play the same song twice in a row. Have a look at the Fisher-Yates shuffle algorithm, "modern version": this basically puts all your items to be randomized into an array and treats it like a deck of cards. Starting at the end of the array and working backwards, swap that element with a randomly-selected element between (including) position 0 and the current position. (This means the item could even be swapped with itself, but the computer doesn't mind.)

This method is mathematically unbiased (even though items near the beginning of the list might appear to get "shuffled more", i.e. swap positions more times), and assuming the 'deck' does not include duplicates of the same item, guarantees no repeats until the deck runs out and has to be reshuffled. You could still get a repeat if the first item in the new deck happened to be the last item in the old deck, but it would be pretty uncommon (and you could still throw it away if it really mattered :slight_smile:

Using the Arduino's timer to seed the randomizer upon a button-press seems like it would be good enough to assure the results were unique. Unless the user is a robot and presses the button in an exact (msec-timed) sequence every time!

And that you've got a nice long antenna on the unused input you're using for randomisation.

Even with a several centimeter antenna, analogRead does not appear to be a particularly good choice. In my testing, the values fall into a small subset of the available buckets and follow easily recognizable patterns. The antenna seems to pick up digital noise from the processor more than anything else. If the antenna is shielded close to the processor and outside of the processor's influence I suppose the values would be higher quality.

But why bother? random produces good results. For seeding, just save the previous value in EEPROM. That's actually how random (and it's ilk) are meant to be used.

Using the Arduino's timer to seed the randomizer upon a button-press seems like it would be good enough to assure the results were unique.

There's a good example in the "old forum" based on that idea. The person was trying to build a "dice roller". One value (I think it was "4') had about 2:1 odds of occurring with one value never occurring. The code looked like it would work but failed horribly.

There are subtle problems with fiddling with random numbers, even using rand () can lead to problems (apart from the obvious ones about whether it is implemented properly). For example, if you want to get a number in a range (eg. dice) you might do this:

int getrandom (const int x)
{
 return (rand () % x);
}   // end of getrandom

But by taking the modulus you are throwing away all the bits from rand() except the lower-order ones. So for example, if you did getrandom(2) and rand() (for some reason) always returned even numbers (but was otherwise random in the other bits) then you will always only get one result.

A better way is:

int getrandom (const int x)
{
  return ((double) rand () / (double) (RAND_MAX + 1)) * (double) x;
}   // end of getrandom

This first turns the output of rand() into a number in the range [0,1). That is, including 0 but excluding 1.

Now we multiply this by the argument to get a number in the range 0 to the argument, but excluding the argument.

That uses all the bits in the random number we chose (whether it is from rand(), millis() or whatever).

robtillaart:

That works fine and all, but I need a little more functionality. For example, it should not be possible for two exactly the same letters to show up right after another (aa, bb, etc.).

If you filter such combination out, it is strictly speaking not really random (with dices you throw the same value also 1 in 6) . Can you tell the rationale behind this requirement?

The reason behind this is that the randomizer will be used for generating hotkeys linked to let's say 36 video's. A push of a button should skip to the next video at random. However, if a user pushes the button and by chance the randomizer generates the same hotkey as the previous one, there will be no noticable change in video and thus leaving the user confused (thinking his input had no result). So direct feedback is a must, and by ruling out the possibility of getting the same result twice in a row we rule out the possible confusion.

More out of curiosity than anything, has anyone built a cheap "high" quality RNG for Arduino, for some value of "high"?

I was thinking of connecting a reverse biased Zener to an analogue in and looking for zener noise. I'm not sure there's enough gain in the ADC comparators. Another idea I had was to make a 555 oscillator out of low grade parts and feed the trigger voltage into the ADC.

Seeding a PRNG would then collect some entropy from the ADC, and maybe other sources. Maybe make few hundred A-D readings over a 1 second period and feed all that into a CRC-32 would not be too complicated.

The PRNG could be an Xorshift type generator. Something that doesn't need to keep too much state, but has good statistical performance. Better would be something that is suited to feeding extra entropy into over time.

Is this already "done" somewhere?

Begin of this year there was a discussion on the old forum about randomness, using the internal temperature sensor of the UNO as a random seed generator and about fetching a random number/seed from the internet. might be worth reading - http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1294239019

gardner:
More out of curiosity than anything, has anyone built a cheap "high" quality RNG for Arduino, for some value of "high"?

There is this...
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1268761421

In my testing, it performed very poorly. The raw and cooked values followed noticeable patterns. The algorithm can sometimes take a very long time to generate values.

The strategy is just on the verge of working / not working. Any little tweak of the code and the values fall into a degenerative state (e.g. all ones, always toggle, all zeros, no value produced).

I was thinking of connecting a reverse biased Zener...

The ideal hardware solution would generate an interrupt when more entropy is available. This would allow data to be collected in the background. Something like this may work...

? Relatively low speed independent "unstable" oscillator (the entropy source)

? Connected to an interrupt pin on the processor

? Timer 1 or timer 2 configured to "run free"

? When the interrupt fires, record the least significant bit from the timer

feed all that into a CRC-32

I'd stay away from CRC. I don't think it works well as a random mixing function.

The PRNG could be an Xorshift type generator. Something that doesn't need to keep too much state, but has good statistical performance.

I don't know if it's an Xorshift type generator but rand / random does well with most statistical tests.

Better would be something that is suited to feeding extra entropy into over time.

XOR values from rand with values from a hardware generator.

The AVR-libc random() is a Park and Miller linear congruential PRNG with a period of 2^31. It's fine if it's seeded properly, but it's not great. I was thinking that something with a longer period might be nice. Xorshift is fast, has a period of 2^64 and still only needs 64 bits of state. Either way, the problem is really to seed it right.

There is this...
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1268761421

That's interesting. I wasn't able to see what he actually did to set-up/read the A2D. I am not convinced that the A2D has enough sensitivity -- or maybe not enough sensitivity in all cases -- to get a useful amount of entropy without some extra wiring external to the Arduino. The temperature sensor mentioned here looks like a better bet:

worth reading - http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1294239019

I'm not surprised that folks would have issues with using these directly to generate random bits. The whitening algorithm is not guaranteed to complete in any specific time, which leads to problems if you use it in the normal course of getting random bits. What I would propose is to use a source like this just to seed a conventional PRNG. The conventional PRNG should be fast, with predictable run-time in the 100s of instructions.

independent "unstable" oscillator

Yes, the "clock skew" method. This would be fine.

That's kind of what I was also suggesting with feeding an analogue waveform into the A2D from a simple 555 circuit. Only my feeling was that you should be able to get ~4 or more bits of entropy from the circuit on demand, and not have to have any code around for storing it or have to mess with interrupts. Just read bits, wait a few ms and read more bits.

I'd stay away from CRC. I don't think it works well as a random mixing function.

The idea would be to use this only for generating the seed. If we guess that an A2D reading has 1/4 of a bit of entropy in it, we can read it 128 times and feed all the readings into a CRC-32 to obtain a concentrated 32-bit seed from that. CRC has a couple of good properties: It is easy to calculate and requires very little memory and it provably combines all the input bits into all the output bits. It is not cryptographically secure, but that's not the requirement. It performs the same basic function as the Von Neumann whitening, but has deterministic run time.

XOR values from rand with values from a hardware generator.

No, I don't like that. I want the new entropy to go into the PRNG state, not just into the output. Re-seeding via srandom(random() + new_entropy_bits) maybe. I'm not sure if the properties of Park and Miller or Xorshift are suited to that. I'm not an expert.

I also don't want to be obligated to come up with hardware randomness when the code asks for a PRNG, since that risks non-deterministic behaviour of the main get-me-a-random-number() method.

gardner:
I was thinking that something with a longer period might be nice. Xorshift is fast, has a period of 2^64 and still only needs 64 bits of state.

Do you have a generator in mind?

Either way, the problem is really to seed it right.

That's certainly the issue that comes up in the forum.

There is this...
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1268761421

That's interesting. I wasn't able to see what he actually did to set-up/read the A2D.

It doesn't work like this but this is how I visualize what happens: Enable the pull-up resistor so the pin goes high. Turn off the pull-up resistor and start a conversion. At a certain point, the falling pin voltage and the rising comparison voltage cross paths and the conversion completes. The theory is that the two voltages cross at a random point in the conversion.

I am not convinced that the A2D has enough sensitivity

I believe it does. From my testing, the problem is that the only potential source of entropy from an AVR processor is the digital noise generated by the processor itself which is not at all random.

It's important to remember that AVR processors are meant to be very deterministic and it's tough to get anything random out of something that is deterministic.

-- or maybe not enough sensitivity in all cases -- to get a useful amount of entropy without some extra wiring external to the Arduino.

I agree!

The temperature sensor mentioned here looks like a better bet:

My testing does not bear that out. (comments in that thread)

I'd stay away from CRC. I don't think it works well as a random mixing function.

It performs the same basic function as the Von Neumann whitening, but has deterministic run time.

The reason Von Neumann is not deterministic is because of a lack of entropy. That potential problem also applies to CRC (and everything else). If you can collect enough data (128 quarter bits in your example) for the CRC to produce a result than you can also collect enough data for Von Neumann to produce a result. If you cannot collect enough data, then neither will produce a result.

Re-seeding via srandom(random() + new_entropy_bits) maybe.

The problem with re-seeding is that it potentially invalidates the statistical tests that are performed on the generator to prove its quality.

XOR values from rand with values from a hardware generator.

No, I don't like that.

In that case...

The idea would be to use this only for generating the seed.

...is the best choice.

gardner:
I was thinking that something with a longer period might be nice.

Mersenne Twister

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ewhat-is-mt.html

Claimed there:

Far longer period and far higher order of equidistribution than any other implemented generators. (It is proved that the period is 2^19937-1, and 623-dimensional equidistribution property is assured.)

I suspect you're joking, but M-T needs over 600 bytes of state and is pretty computationally expensive. I want something with 48 or 64 bits of state that is computationally cheap. And ideally something that has a known re-seeding procedure. An L-C or LFSR is good for a small state.