As I played with my Arduino in anticipation of programming Something Really Big Now, I got a surprise – the randomSeed() function didn’t work very well.
Of course, notice the quotes around ‘bug’ in the title – the fact is, the function itself is fine, but the input isn’t.
On the Arduino website, they recommend seeding it with a port value, like this:
randomSeed(analogRead(0));
The problem? That value from analogRead(0) is not as random as we think; in fact, when I use the following sketch to check my port values:
void setup()
{
Serial.begin(9600);
for (int i=0;i<256;++i)
{
Serial.print(analogRead(0));
if (0==(i&0xF)) // for line breaking/formatting
Serial.print("n");
Serial.print(" ");
}
}
void loop()
{
}
Here’s some of my results:
450 448 448 449 449 447 447 448 448 446 446 447 446 445 444 445 445 443 443 444 444 442 442 443 442 441 441 442 441 440 440 440 440 439 439 440 439 438 438 439 438 437 437 438 437 436 436 437 435 434 435 435 434 433 434 434 433 432 432 433 432 431 431 432 431 430 431 431 430 429 430 430 429 428 429 429 428 427 428 428 427 426 427 427 426 425 426 426 424 424 425 425 423 423 424 423
To use, just run it for your Arduino – I’m very curious if everyone else has this very narrow range of values.
Now this list is decidedly not random, especially since this port should return a value from 0-1023, or 10 bits of information.
But the hardware isn’t the problem – after all, it’s not made to be random, just a useful side effect of the design. So what we need to do is figure out how to make this side effect work for us – and get real random values.
In a nutshell, I decided to use the change between values – if the next number from analogRead() was different from the previous one, I counted it as a single ‘1’, and if no change, I’d count it as a ‘0’.
So looking at the previous values, I’d get a series of bits as they change:
1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1
However, that isn’t quite random enough – notice the ratio of ones to zeroes (30 zeroes and 65 ones). While the input seems random enough, it’s seriously biased, and I needed to unbias it.
Fortunately, the solution is easy: Von Neuman had a simple way of removing random bit bias by “casting off” extra bits. Basically, you take pairs of random bits. If they are identical, you throw them away. If not, then the first bit is used for the final result. Do it often enough, and your bits are biased properly, with more or less even amounts of ones and zeroes (but not too even of course, since even that should be random!)
So grouping the bits into pairs:
10 10 10 10 10 11 11 10 10 10 10 11 10 11 10 00 10 11 10 11 10 11 10 11 11 01 11 01 10 11 10 11 11 01 11 01 11 01 11 01 11 01 11 01 01 01 01
And casting off 00 and 11 pairs:
10 10 10 10 10 11 11 10 10 10 10 11 10 11 10 00 10 11 10 11 10 11 10 11 11 01 11 01 10 11 10 11 11 01 11 01 11 01 11 01 11 01 11 01 01 01 01
We end up with the remaining random bits – but a whole lot less of them!
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0
So put together, the final code is this:
void setup()
{
Serial.begin(9600);
// signal ready to go and then wait a bit
pinMode(13, OUTPUT);
digitalWrite(13, HIGH);
delay(2000);
}
//------------------------------------------------------------------------------
void loop()
{
// create 31 bit seed and show value, random results
unsigned long seed=seedOut(31);
Serial.print("seed = ");
Serial.print(seed);
// now show sequence
randomSeed(seed);
Serial.print(" random (1-99) = ");
for (int i=0;i<20;++i)
{
Serial.print(random(1,100));
Serial.print(" ");
}
Serial.print('n');
}
//------------------------------------------------------------------------------
unsigned int bitOut(void)
{
static unsigned long firstTime=1, prev=0;
unsigned long bit1=0, bit0=0, x=0, port=0, limit=99;
if (firstTime)
{
firstTime=0;
prev=analogRead(port);
}
while (limit--)
{
x=analogRead(port);
bit1=(prev!=x?1:0);
prev=x;
x=analogRead(port);
bit0=(prev!=x?1:0);
prev=x;
if (bit1!=bit0)
break;
}
return bit1;
}
//------------------------------------------------------------------------------
unsigned long seedOut(unsigned int noOfBits)
{
// return value with 'noOfBits' random bits set
unsigned long seed=0;
for (int i=0;i<noOfBits;++i)
seed = (seed<<1) | bitOut();
return seed;
}
Here’s some some notes on using it:
- The code shows how to use the two functions, bitOut() and seedOut(), which contain all the details of bit handling. Add them to your code, and then call seedOut() to get a random number back. You can use this number directly, or as a seed value via randomSeed(). You call it with the number of bits you want in your result, and it returns them. I’d recommend no more than 31, since 32 bits can cause strange results if you’re not expecting it (in C, this is a sign bit and could make the number negative if you aren’t familiar with C/C++ casting rules). However, even if you use 15 for the value, that’s 32,768 possible start positions for random numbers.
- As you can imagine, using only one bit per reading, and then throwing away many bit pairs to unbias the values can use a LOT of cycles. In my tests, it’s at least 10:1 – 10 port readings to get one usable bit. So you’re better off using these routines once to get your seed value, using randomSeed(), and then letting the random() function get all the rest of your numbers.
- The value in bitOut() called limit keeps the loop from running forever. What it does is limit the number of bit pairs thrown out per sample. Making it low makes the routine run faster, but risks the bias creeping back in. Raising it higher can slow the program down. I found 99 worked well, but as a rough guide, 10 is at the lower end (faster, but more bias), while 1000 is at the upper end (slower, but less bias). However, don’t be tempted to take the limit out: if for example the port always returned the same number (say, because of something connected to it), then you’d stay in an infinite loop.
Feel free to use the code, and I’d like to hear how it helps your projects!
Note: an update with more (and simpler) code is available on this post.
