Pseudo-random numbers trick for small values

Game Resources
1

So, I just shaved another 100 bytes in Hexxagon by getting rid of random() and, instead, using a small trick to achieve a similar effect.

But first, a caveat, this will only work in a passable way if you need only a small range of random numbers and you would never want to use this for any type of cryptography ( :wink: ).

So, what I did was replace:

byte n = random(2);

With:

byte n = millis() % 3;

The reason this works as a reasonable approximation is because there are several factors that determine the amount of time that will pass between loop() iterations (one of them being the time data takes to be transmitted via IR which by itself already makes this be pretty close to random) so as you are using a very small range of numbers, this is almost as unpredictable as it gets (again as an approximation).

Storage-wise, this is a lot less expensive then a random() call and the associated randomize() call.

3 Likes
2

Ha! Yeah I use that trick all over the place when I need a coin flip. I even created a version of millis() that only returns 8 bits and it shaved off a handful more bytes.

2 Likes
3

BTW, there is a huge caveat I did not mention because, in my mind, it was obviousā€¦ But maybe it might be that obvious to everybody so here it goes:

This just works if you only call it once per loop iteration. Specially because time is frozen (from the millis() perspective) during loop iterations so if you try to call that multiple times, you will get always the same number. Not very random. :slight_smile:

1 Like
4

Another caveat to remember is that until something external happens (like a button press), all blinks are deterministically the same and all will do exactly the same thing. So, for example, this code will always end up with a GREEN blink. Always, on every blink, every time it is startedā€¦

void setup() {
  // put your setup code here, to run once:

}

bool colorSetFlag = false;

void loop() {
  // put your main code here, to run repeatedly:

  if (!colorSetFlag) {

    byte randomColorPicker = millis() % 3;

    switch (randomColorPicker) {

      case 0: setColor(RED);   break;
      case 1: setColor(GREEN); break;
      case 2: setColor(BLUE);  break;
      
    }
    
    colorSetFlag = true;
  }

}

If you have a bunch of blinks and you download this program to them all, they will all dutifully turn GREEN at the end of the download.

While this might seem like a contrived example, it did come up in real games. That is why I had to make the entropy-based randomize() function. (Note that it is very hard to find entropy inside a blink before any button presses. :slight_smile:)

Also note that if your application can use a range that happens to be a power of two, then you can save an additional ~80 bytes. So, for exampleā€¦

byte coinFlip = millis() % 2;

ā€¦is smaller than

byte centuryToss = millis() % 100;

This happens because the compiler can reduce a mod of a power of 2 down to a single binary and, whereas a mod of an non-power of two requires a divide and multiply (very expensive on this chip).

ā€¦and finally I need to add the warning that random numbers are a surprisingly tricky business to do right. You might see the above, and writeā€¦

byte dieRoll = min( (millis() % 8 ) , 5 );

Seems fine because it is random (or at lest pseudo) and the result is always in the range 0-5ā€¦ but it is not evenly distributed. If you used this for a craps game then youā€™d find some very bad outcomes! Whole empires have fallen when hapless programmers have fallen for this mistake!

And on a closing warning note, do you see why even this is no good and terribly wrong?..

randomize(); 
byte twoDiceRoll = random( 11 ) + 1;

If you are interested, Knuth has much to say about this topic.

2 Likes
5

Ah, yes, the trick I mentioned will not work for the first loop iteration (this was implied by my comment about IR transmission as it only happens after loop() runs). In the case where I applied it, this will never be an issue.

I understand the case of the summing 2 dice rolls in the link you provided, but I do not think it applies for the example you gave. In a more general way, I do not think it applies to a constant + ā€œrandomā€ number as the constant itself, being a constant and separate from the random number generation, can not change the properties of the generated random number. Another way to think about it is that you could change your code to take into account numbers from 1 to 12 instead of 0 to 11 and that would not (and can not) have any effect on the generated number (or the general distribution).

But yes, generating random numbers (specially truly random numbers) is not a trivial thing. Approximations tend to be, but they are, indeed, just approximations.

1 Like