Closed GoogleCodeExporter closed 9 years ago
This was also posted in the arduino forum...
It turns out that *the first* (pseudo) random number *after* seeding may or may
not appear to be random
depending on the arguments given to random().
Here are 2 programs that run 1000 trials for each random(0, max) where max goes
from 2 to 40. One seeds
only once, the other seeds prior to every use of random(). The difference is
quite clear.
(Note: to create nice big noisy seeds I called analogRead 32 times and then
used the 32 low bits to construct
the seed).
Phil
// program to test whether the numbers generated by random()
// are reasonably (pseudo) random. It turns out that regardless
// of the maximum value being used the results appear to be
// reasonably random.
int bins[40];
void setup(){
Serial.begin(9600);
long tempBits = 0; // create a long of random bits to use as seed
for (int i=1; i<=32 ; i++){
tempBits = ( tempBits | ( analogRead( 0 ) & 1 ) ) << 1;
}
randomSeed(tempBits); // seed
}
void loop(){
for (int max=2 ; max<=40 ; max++){ // test 2 through 40 as random maximums
for (int i=0 ; i<40 ; i++) bins[i] = 0; // zero out counting bins
for( int trial = 1 ; trial <= 1000 ; trial++ ){ // for each maximum run 1000 trials
bins[random( 0, max )]++; // and count the random number generated
}
Serial.print( max ); // display the results (counts for each random number)
Serial.print( " *** " );
for (int i=0 ; i<max ; i++){ // display the counts
Serial.print( bins[i] );
Serial.print( " " );
}
Serial.println(" ");
delay(400);
}
}
// program to test whether the *first number* generated by random()
// *after being seeded* is really (pseudo) random. It turns out that depending
// on the maximum value being used the result may or may not be
// reasonably random.
int bins[40];
void setup(){
Serial.begin(9600);
}
void loop(){
for (int max=2 ; max<=40 ; max++){ // test 2 through 40 as random maximums
for (int i=0 ; i<40 ; i++) bins[i] = 0; // zero out counting bins
for( int trial = 1 ; trial <= 1000 ; trial++ ){ // for each maximum run 1000 trials
long tempBits = 0; // create a long of random bits to use as seed
for (int i=1; i<=32 ; i++){
tempBits = ( tempBits | ( analogRead( 0 ) & 1 ) ) << 1;
}
randomSeed(tempBits); // seed
bins[random( 0, max )]++; // and count the random number generated
}
Serial.print( max ); // display the results (counts for each random number)
Serial.print( " *** " );
for (int i=0 ; i<max ; i++){ // display the counts
Serial.print( bins[i] );
Serial.print( " " );
}
Serial.println(" ");
}
}
Original comment by b...@philipgalanter.com
on 10 Mar 2010 at 6:45
As I understand it, this isn't really a bug, since you're only supposed to call
randomSeed() once (or occasionally).
Is that true? If not, any suggestions for what to do about this?
Original comment by dmel...@gmail.com
on 12 Apr 2010 at 9:55
This is definitely a bug.
If you give randomSeed() a truly random seed, then your first call to random()
should give you a random
number regardless of the range you ask for. But that is not happening.
This is a problem when you have a system you want to exhibit random behavior
upon power up. Like, for
example, my art project that uses a lighting system. Upon power up it should
display one of a million
different light sequences. Instead upon power up it always shows the same 2 or
3 or 4 sequences.
The bug is likely in the realm of numerical analysis and the RNG code in the
library. i.e. it's an algorithm thing
(or a typo in the code) not a matter of inaccurate documentation or
unreasonable expectations.
thanks, Phil
Original comment by philipga...@gmail.com
on 12 Apr 2010 at 11:13
I hate to come late to a discussion, but I don't like to see people go too far
off the path. The short answer is the randomseed() should be called only once
in setup() and this is not a bug.
Think of it as if you had a very long list of randomly picked numbers that
doesn't change. If you started taking numbers from a different place in the
middle of the list it would appear to a person that it was truely random, but
if you started at the same spot repeatedly, you would get the identical
sequence of numbers. This is how pseudo-random generators work.
It is suggested to read an unconnected pin because there will be a random
voltage there due to the capacitance of the pin and that would give you a
different place to start the psuedorandom generator, but reading the pin again
is very likely to give you the same seed so you get the same sequence of
numbers from random().
Original comment by Mark.Ric...@gmail.com
on 7 Jul 2014 at 10:23
I think if you go back and read my post more carefully you will see that I've
already considered what you are saying, and there is a problem nevertheless.
Here is the problem stated as succinctly as I can.
For some inputs random() fails to generate random results the first time it is
called. This happens despite the use of random seeds.
Details and evidence:
(1) To generate a random seed I read a floating pin 32 times and only use the
lowest, i.e. noisiest, bit. So I'm not using the same seed over and over
again. To see that this works check out the bit stream generated by this:
void setup(){
Serial.begin(9600);
}
void loop(){
Serial.println( analogRead(0) & 1 );
delay(400);
}
Or look at a series of seeds created this way:
void setup(){
Serial.begin(9600);
}
void loop(){
long tempBits = 0;
for (int i=1; i<=32 ; i++){
tempBits = ( tempBits | ( analogRead( 0 ) & 1 ) ) << 1;
}
Serial.println( tempBits, HEX );
delay(400);
}
(2) Typical random number generators will produce the same sequence when given
the same seed. A common technique is to use the same seed to get the same
random number sequence. The Arduino documentation affirms this. “Conversely,
it can occasionally be useful to use pseudo-random sequences that repeat
exactly. This can be accomplished by calling randomSeed() with a fixed number,
before starting the random sequence.”
In normal use one only calls randomSeed once, but there are occasions where
calling it multiple times makes sense, and debugging is one of those
situations. The code I’ve posted seeds more than once for the purpose of
testing and debugging. This is legal and a common practice in multiple
languages including Arduino.
(3) The bug I’ve tried to report here isn’t about seeding per se. It’s
about getting nonrandom results the first time random() is called. Seeding
prior to every call is only done to allow multiple “first” calls. This
should work, and for many arguments to random() it’s clear that it does.
Here are the results for generating (first) random numbers for the range (0,N)
where N is first 1, then 2, and so on. 1000 (first) random numbers are
generated, and then the counts for each value are given. You won’t, of
course, get a perfectly equal distribution among the possible outcomes, but
there shouldn’t be any extreme clumping of results.
For ranges like (0,2) or (0,12) or (0,30) you get what appears to be a fairly
uniform distribution. But for ranges like (0,1) or (0,6) or (0,34) you get
distributions which are clearly not uniform. This is a real problem. Results
and then code follow.
1 *** 984 16
2 *** 354 243 403
3 *** 470 14 504 12
4 *** 223 174 167 240 196
5 *** 358 4 416 4 212 6
6 *** 959 8 9 10 2 9 3
7 *** 341 5 376 7 138 12 118 3
8 *** 111 100 155 94 82 133 122 74 129
9 *** 214 5 148 10 208 4 156 1 248 6
10 *** 68 93 59 99 126 98 89 91 105 77 95
11 *** 175 1 247 1 104 4 170 2 179 1 114 2
12 *** 85 84 86 66 60 77 68 56 60 83 82 127 66
13 *** 964 3 3 5 4 3 1 3 2 3 2 5 1 1
14 *** 144 37 31 20 51 34 37 58 180 81 48 87 77 32 83
15 *** 259 0 280 2 96 0 5 0 135 3 118 2 5 2 91 2
16 *** 36 72 61 25 81 67 77 57 74 53 51 39 46 56 69 61 75
17 *** 129 0 154 4 59 0 119 3 120 2 100 6 101 3 129 4 65 2
18 *** 63 42 75 51 43 61 52 52 49 53 45 42 54 50 94 33 49 41
51
19 *** 129 1 107 4 89 1 58 0 88 2 82 1 68 2 100 2 103 1 160
2
20 *** 346 1 2 0 0 1 2 244 3 1 0 2 1 1 385 2 0 3 1 3 2
21 *** 67 2 83 0 124 3 102 2 87 2 77 1 97 2 98 1 87 2 94 3
65 1
22 *** 40 37 24 44 71 49 40 36 45 35 49 38 29 42 36 36 45 69
44 49 44 52 46
23 *** 160 0 179 1 38 4 28 3 140 4 78 1 52 1 48 0 76 1 120 1
27 2 34 2
24 *** 36 36 29 60 35 48 46 33 41 48 61 29 38 75 38 48 23 29
37 37 40 22 32 44 35
25 *** 89 2 78 0 60 0 60 0 83 1 93 1 60 3 92 1 44 0 70 2 60
0 83 0 118 0
26 *** 21 28 61 44 28 45 46 26 33 50 41 75 43 21 34 33 22 42
51 17 48 49 17 34 39 16 36
27 *** 473 1 1 3 7 0 1 3 0 2 4 1 2 2 480 2 3 2 0 1 4 2 0
4 1 0 0 1
28 *** 18 27 46 28 40 32 44 14 24 21 47 26 39 29 36 31 51 26
50 19 69 36 45 23 33 29 29 52 36
29 *** 119 1 43 1 94 0 48 0 168 0 37 2 81 1 57 1 52 1 29 0
29 1 51 1 77 0 65 0 38 3
30 *** 107 38 24 24 19 43 24 18 46 27 50 27 25 32 25 22 31 21
32 23 26 38 30 40 24 23 54 27 25 15 40
31 *** 167 2 94 2 89 1 2 0 111 0 107 0 1 4 100 1 81 0 194 3
7 0 6 2 2 1 5 1 5 5 6 1
32 *** 30 28 40 40 17 26 37 23 28 32 27 26 24 10 31 33 18 41
43 17 43 19 11 36 42 33 57 45 16 38 32 14 43
33 *** 37 0 73 0 64 1 73 0 59 1 70 4 36 1 49 0 43 3 71 4 49
2 78 0 66 0 66 2 37 0 49 2 60 0
34 *** 202 2 1 0 2 0 1 158 1 4 0 0 1 1 179 3 2 6 2 0 1 165
1 1 1 0 0 0 258 2 2 0 2 0 2
35 *** 64 1 109 0 32 0 68 1 36 0 48 2 92 0 61 2 34 6 55 0
52 1 27 0 62 3 77 0 46 3 39 1 53 0 24 1
36 *** 21 24 29 30 37 7 20 28 20 32 12 52 27 32 28 56 15 30
17 39 18 15 36 24 27 22 70 21 9 24 27 36 30 18 18 30 19
37 *** 53 0 70 0 39 1 42 1 37 2 47 3 80 3 82 2 38 2 44 0 54
2 49 2 57 2 62 1 54 1 35 2 46 0 45 2 40 0
38 *** 23 25 35 28 14 26 31 10 40 41 20 71 17 16 30 22 13 21
44 11 24 15 32 28 32 22 39 34 22 23 21 10 26 19 12 22 29 25
27
39 *** 95 1 77 0 44 1 10 1 81 1 64 2 8 1 28 1 75 0 143 0 24
1 24 0 69 0 58 2 14 3 21 1 35 2 74 1 21 0 17 0
// program to test whether the *first number* generated by random()
// *after being seeded* is really (pseudo) random. It turns out that depending
// on the maximum value being used the result may or may not be
// reasonably random.
int bins[40];
void setup(){
Serial.begin(9600);
}
void loop(){
for (int myMax=2 ; myMax<=40 ; myMax++){ // test 2 through 40 as random maximums
for (int i=0 ; i<40 ; i++) bins[i] = 0; // zero out counting bins
for( int trial = 1 ; trial <= 1000 ; trial++ ){ // for each maximum run 1000 trials
long tempBits = 0; // create a long of random bits to use as seed
for (int i=1; i<=32 ; i++){
tempBits = ( tempBits | ( analogRead( 0 ) & 1 ) ) << 1;
}
randomSeed(tempBits); // seed
bins[random( 0, myMax )]++; // and count the random number generated
}
Serial.print( ( myMax - 1 ) ); // display the results (counts for each random number)
Serial.print( " *** " );
for (int i=0 ; i<myMax ; i++){ // display the counts
Serial.print( bins[i] );
Serial.print( " " );
}
Serial.println(" ");
}
}
Original comment by galan...@viz.tamu.edu
on 7 Jul 2014 at 5:50
Because some folks have gotten hung up on calling randomSeed() multiple times,
here is a tedious way to demonstrate the problem. Run the code below, open the
monitor window, and then keep hitting the reset button. See how long it takes
to get a "random" number that isn't 0 despite the use of different seeds every
time.
// program to test whether the *first number* generated by random()
// *after being seeded* is really (pseudo) random. This test uses the range
// (0,7) but some other ranges are problematic, and some are not
void setup(){
Serial.begin(9600);
}
void loop(){
long tempBits = 0; // create a long of random bits to use as seed
for (int i=1; i<=32 ; i++){
tempBits = ( tempBits | ( analogRead( 0 ) & 1 ) ) << 1;
}
randomSeed(tempBits); // seed the random number generator
Serial.print( " Seed = " ); // display the results
Serial.print( tempBits, HEX );
Serial.print( " random(0,7) = " );
Serial.println( random(0,7) );
while( 1 ) {
}
}
Original comment by galan...@viz.tamu.edu
on 7 Jul 2014 at 6:19
I noted that I was left shifting the seed value once too many times resulting
in seeds that were always even numbers. That's fixed below and has no apparent
impact on the result. random(0,7) is still almost always 0 when first called.
// program to test whether the *first number* generated by random()
// *after being seeded* is really (pseudo) random. This test uses the range
// (0,7) but some other ranges are problematic, and some are not
void setup(){
Serial.begin(9600);
}
void loop(){
long tempBits = 0; // create a long of random bits to use as seed
for (int i=1; i<=32 ; i++){
tempBits = tempBits << 1;
tempBits = ( tempBits | ( analogRead( 0 ) & 1 ) );
}
randomSeed(tempBits); // seed the random number generator
Serial.print( " Seed = " ); // display the results
Serial.print( tempBits, HEX );
Serial.print( " random(0,7) = " );
Serial.println( random(0,7) );
while( 1 ) {
}
}
Original comment by galan...@viz.tamu.edu
on 7 Jul 2014 at 6:31
This issue cannot be solved because the function isn't implemented by us.
Original comment by a.guadal...@arduino.cc
on 24 Nov 2014 at 1:46
Original issue reported on code.google.com by
b...@philipgalanter.com
on 10 Mar 2010 at 7:16