Go Down

Topic: Here's a very simple way of randomly seeding rand() (Read 8293 times) previous topic - next topic

ofransen

In another post I asked about how to randomly seed a randomSeed() call for use with the random() function. While messing with diodes and resistors on an analog input of the Arduino it occurred to me that the 10 bits of analog input must be pretty sensitive to noise. And if the analog in is not connected to anything it is floating and prey to any stray electrical noise in the vicinity. So I simply do this:

Code: [Select]
    // This is my setup for my sketch, but anyway bit 5 becomes an analog input
    DDRC = 0xCF; // PortC, Turn most analog inputs to digital outputs, except for bits 4 and 5

    // This stuff will be better inside a function of course, but basically
    // I read three times the presumably more noisy 3 LSB bits of the ADC
    // and form them into a single 9 bit (range 0...511) number.

    iRandom1 = analogRead(5) & 0x7 ;
    delay (10) ;
    iRandom2 = (analogRead(5) & 0x7) << 3 ;
    delay (10) ;
    iRandom3 = (analogRead(5) & 0x7) << 6 ;
    delay (10) ;
    iRandom = iRandom1 + iRandom2 + iRandom3 ;

    Serial.println(iRandom, DEC);     

No doubt it is not a good random number generator, but it is probably a good randomSeed maker for "non technical projects" which have a spare ADC pin and which require a different starting point every time the Arduino is switched on.

You have the advantage that you don't have to add any hardware or connect to the internet.

I'm prepared to be shot down in flames, so fire away!

Attached are a couple of runs as an Excel graph





simon.monk

#1
Aug 19, 2011, 04:05 pm Last Edit: Aug 19, 2011, 04:09 pm by Si Reason: 1
Interesting. The analog inputs usually float quite wildly at 50Hz. At least they do on my electrically noisy desk.

So your 9 bits will make a pretty good randomish number, but I bet there would be some bias on it.

You could put it in a loop and get a full 16 bits, one least significant bit at a time from the analogRead and use that as a seed to randomSeed.

But how often do you need a really random number on an Arduino.

randomSeed(analogRead(0))

is usually good enough.
--
I write books about Arduino and Electronics: http://simonmonk.org

graynomad

We had a long thread about this recently and I posted diagrams that looked very much like yours.

But I found quit obvious banding in the data.

I'll see if I can find the thread.

______
Rob
Rob Gray aka the GRAYnomad www.robgray.com

PaulS

Quote
I'm prepared to be shot down in flames, so fire away!

No by me. I don't really care, but there has been a lot of discussion on the forum of the last year why your approach is not a good idea. As long as you can control the level of noise on that unused pin, your approach works. Moving a hand or anything else near that pin changes the value that analogRead returns - sometimes to very consistent, repeatable values. Then, there goes your randomness.
The art of getting good answers lies in asking good questions.

gardner

Seeding PRNGs is actually a perennial topic it seems.  There have been many threads discussing the ins and outs.  The idea of exploiting noise in the low bits of the analogue input comes up from time to time and someone posted a usable library once.  There are some problems with using this method: the effectiveness varies from part to part and the "noise" is actually mostly interference withe the digital switching of the CPU and has a measurable pattern.  Nevertheless folks have used this method to good effect.

If it were me, I think I would add some features to what you have done.

(1) read the A2D more times -- at least a few hundred times, 3 bits per read x 200 reads gives you 1200 bits of entropy to work with
(2) use a "whitening" algorithm on the bits
(3) stir all the bits you read together using something like an XOR or calculate a CRC over the bits

And if you're really worried about randomness, your next line of inquiry should be into the quality of the random() function's PRNG -- hint: it is not stupendously good.  There are several much better quality longer period PRNGs that could be implemented in just a few hundred bytes of code, using 8 bytes of state.

Bobnova

I generally use an unsigned int and read an unconnected ADC pin a few dozen times and multiply them together.  It'll loop a few times, but that doesn't decrease the randomness.  Unless of course it hits zero exactly.
Then again, the randomness isn't that important to me either.

There was a thread/post on the old forum that had code that the guy claimed was a genuine 50/50 distribution for random(0,1);
I don't remember where it was though.

gardner


I would add some features


And this is what I came up with ---

Code: [Select]

uint32_t get_seed(int pin)
{

uint16_t aread;
union {
   uint32_t as_uint32_t;
   uint8_t  as_uint8_t[4];
} seed;
uint8_t i, t;


    /* "aread" shifts 3 bits each time and the shuffle
     * moves bytes around in chunks of 8.  To ensure
     * every bit is combined with every other bit,
     * loop 3 x 8 = 24 times.
     */
    for (i = 0; i < 24; i++) {

       /* Shift three bits of A2D "noise" into aread.
        */
       aread <<= 3;
       aread |= analogRead(pin) & 0x7;

       /* Now shuffle the bytes of the seed
        * and xor our new set of bits onto the
        * the seed.
        */
       t = seed.as_uint8_t[0];
       seed.as_uint8_t[0] = seed.as_uint8_t[3];
       seed.as_uint8_t[3] = seed.as_uint8_t[1];
       seed.as_uint8_t[1] = seed.as_uint8_t[2];
       seed.as_uint8_t[2] = t;

       seed.as_uint32_t ^= aread;
   }

   return(seed.as_uint32_t);
}

ofransen



I would add some features


And this is what I came up with ---


I'm not qualified enough to know if this makes for a better random number seed or not, but thanks for the code!

I foresee the application running for hours, with the need for a random number every 2 or 3 minutes or so. So I'll need a seed maybe twice a day. I will write and expand a function to have more bits, but that is all I need, practically.




ofransen



But how often do you need a really random number on an Arduino.

randomSeed(analogRead(0))

is usually good enough.



From what I've seen analogRead() hangs around at between 200 and 500 roughly. So I'd prefer to mix in several reads of low order bits, rather than having that restricted range.

ofransen


We had a long thread about this recently and I posted diagrams that looked very much like yours.

But I found quit obvious banding in the data.
______
Rob


But this is for creating the seed (not the random number) and since I'll only do that occasionally I don't much care about banding, it will not be noticeable for this art project.

By the way I did not mention I am using the Colorduino, I presume the physics of high impedance 10 bit ADCs is the same on the Arduino, I presume the Arduino does not have some strange pull ups or downs....


ofransen


Quote
I'm prepared to be shot down in flames, so fire away!

No by me. I don't really care, but there has been a lot of discussion on the forum of the last year why your approach is not a good idea. As long as you can control the level of noise on that unused pin, your approach works. Moving a hand or anything else near that pin changes the value that analogRead returns - sometimes to very consistent, repeatable values. Then, there goes your randomness.


I don't believe that moving a hand near a pin will produce consistent lower order bits. Have you tried it?

I know that touching the pin can do.

My random seed will be required only very rarely.



Coding Badly

Quote
I don't believe that moving a hand near a pin will produce consistent lower order bits. Have you tried it?


Yes, I have.  It can.  Using analogRead on a floating pin to generate random data is unreliable.

Quote
but it is probably a good randomSeed maker for "non technical projects"


I mostly agree.  I would use the label "good enough" rather than "good".

Don't bother collecting more than 16 bits.  The parameter for randomSeed is (unfortunately) an "int".

buzzdavidson

Hee.  Yet another "cool way to seed a PRNG" thread - it's interesting that these crop up ALL OF THE TIME on every MCU site I lurk on.  Fun times :D.

Honestly, if you're interested in truly random numbers (for whatever reason), use one of the free online services (hotbits, for example) as a data source and stuff the bits in an eeprom/flash/FRAM/whatever.  Use these bits to either seed the PRNG or use the values directly. 

Analog noise is fine for making more random-y looking randoms for NON SECURITY RELATED stuff.  (hey, someone had to say it in this thread too :P).  There is no shortage of information on this topic online by some seriously intelligent and talented folks.  Also take a look at the classics - Don Knuth's "Art of Computer Programming" has a lot of information on this topic, including increasing the randomness of PRNG-generated values.  Volume 2 is probably the most applicable in this case.  (as an aside, I've been a professional software developer for over 30 years and this is by far the most useful reference set I have ever owned...)

More food for thought: http://www.google.com/url?sa=t&source=web&cd=3&ved=0CCgQFjAC&url=http%3A%2F%2Fwww.eng.auburn.edu%2Fcsse%2Fclasses%2Fcomp7440%2Flessons%2FRandom_Numbers.pdf&rct=j&q=don%20knuth%20random&ei=c4ZPTv2RMbLciALr77GSAQ&usg=AFQjCNGN14MUXxMQLK85Ph44xR7imYmJ9g&sig2=x3sj1HZiU8lUrqUpJVVZOw&cad=rja...

robtillaart

Quote
Don't bother collecting more than 16 bits.  The parameter for randomSeed is (unfortunately) an "int".

I have reported this - http://code.google.com/p/arduino/issues/detail?id=575 -

If you collect more than 16 bits you can call   srandom(seed);   directly ...
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

ofransen


Quote
I don't believe that moving a hand near a pin will produce consistent lower order bits. Have you tried it?

Yes, I have.  It can.  Using analogRead on a floating pin to generate random data is unreliable.
Quote
but it is probably a good randomSeed maker for "non technical projects"



I've just tried it and it makes no difference whether there is hand there or not, the lower 3 bits are not predictable, which is what I am interested in. So I have to disagree, in my experience using  analogRead on a floating pin for the 3 lowest bits does not make it predictable.

Think about it. You are reading a signal which at 10 bits and 5 volts means that:

LSB0 = 4.8mV or 0.0048 V or 0.098% of full range
LSB1 = 9.7mV or 0.0096 V or 0.195% of full range
LSB2 = 19.5mV or 0.0195 V or 0.391% of full range

Can you really move your hand near (but not touching) the pin to get exactly the number (0x05 for example) you want? I can't!

We'll have to agree to disagree I suppose, but I'd be interested in hearing your experimental setup so I can try it here.




Go Up