true random number generator for Axon

[Admin]

I created a new TRUE random number generator for WebbotLib that works great.

It basically relies on total random static in the ADC to create the seed, so if your mcu has ADC, this will work.

Follow the instructions in random_number_gen.h to use it. The other two files are examples of how to use it.

If your PC needs random numbers for an algorithm, just hook up your Axon by USB to be a true random number generator.

Webbot will probably add this to the next WebbotLib version, making it even easier to use.

experimental results:                     
65500   total number of random numbers                        
                           
0   1   2   3   4   5   6   7   8   9
6507   6543   6488   6590   6543   6497   6589   6775   6372   6596
9.934%   9.989%   9.905%   10.061%   9.989%   9.919%   10.060%   10.344%   9.728%   10.070%


edit: improved code to speed it up

[guncha]

Wow, I'm impressed. Good work!

[madsci1016]

Sorry to nit-pick, but is the term "True" random number generator apply here?

For what i was taught, your method still isn't 'true' because with enough samples, the method of creating a number based on a particular seed could be reverse engineered, and the seed found; then when the generator is re-seeded; with a few initial samples to determine the seed value, all future values could be predicted.

One of the only 'true' computerized random number generator i know of uses the radioactive element from a smoke detector and a CMOS camera, and as the substance decays, random pixels are excited on the CMOS sensor; resulting in a physically impossible to predict random number.

I'm ready to insert foot into mouth here, because i could be way off as this was only an interest of mine in school, and i never went through the formal training.

[Admin]

The seed can be changed at any time by taking a new ADC reading. If the seed can be predicted after only 3 or 4 outputs, then the seed can easily be changed after ever 3.

[madsci1016]

At that point though, your 'random number' might as well be a single reading straight off the ADC with some scaling, and if so I might argue it's more fuzzy logic then a 'true' random number.

from wikipedia, http://en.wikipedia.org/wiki/Pseudorandom_number_generator

A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state.

Most computer "random number generators" are not hardware devices, but are software routines implementing generator algorithms. They are often supplied as library routines in programming language implementations, or as part of the operating system. These are more properly called pseudo-random number generators, since, being deterministic finite-state machines, they cannot produce truly random outputs

"True" random number generators in software are a thing of myth. If it were easy, then there would be no need for things like http://gamesbyemail.com/News/DiceOMatic

Sorry to rain in on your hard work, I just have images of my old professors screaming in my head about there are no such thing as  'true' random number generators for computers.


Here is what i was talking about btw,
http://inventgeek.com/Projects/alpharad/overview.aspx

[Webbot]

One of the only 'true' computerized random number generator i know of uses the radioactive element from a smoke detector and a CMOS camera, and as the substance decays, random pixels are excited on the CMOS sensor; resulting in a physically impossible to predict random number.

Aren't we just looking at light-weight easy coding for the masses here rather than banking chip'n'pin ?

Sure - you could probably add all sorts of one-way encryption to avoid reverse engineering but not in a 'handfull of bytes'.

When Admin means 'true' then I think he means this:
If you just call random() then you get the next random number (according to a fixed algorithm) from a very long list.
Rebooting your chip will result in the same sequence of random numbers.
The only way to change the sequence is to seed the list with srandom() stating the starting point in the list. And thats the problem - coming up with a random number for srandom() without using random(). So his use of ADC noise is one approach.

So by using his code -then the program will receive a different sequence of random numbers each time - as opposed to the default C library behavior of returning the same list.

@madsci1016 - Not questioning what you say in 'theory' but sometimes theory can be overkill for practice! And as you say 'TRUE is a thing of myth' - so lets forget it !!

So if Admins ADC routine can come up with a random number for the seed - then why not just use it rather than calling random() ?

Well the answer is that the ADC addition may always end up with a small number - say a maximum of 100. So if you are trying to generate random numbers in the range 0 - 20,000 then it would be useless. But since Admin is using it as a seed value then the next call to random() can return a value in the complete variable range.

[Admin]

At that point though, your 'random number' might as well be a single reading straight off the ADC with some scaling, and if so I might argue it's more fuzzy logic then a 'true' random number.

Well, its random in that its not predictable in any manner . . . it doesn't rely on only an algorithm in software.

All true random generators require hardware measurements.

A PRNG can be started from an arbitrary starting state using a seed state. It will always produce the same sequence thereafter when initialized with that state.

This doesn't happen if I use the ADC to continually change the seed value.

Anyway, as far as a robot creator is concerned, he'll always be guaranteed a new random sequence of values every time his bot is initialized.

(and yea, what Webbot said, too )

[madsci1016]

@madsci1016 - Not questioning what you say in 'theory' but sometimes theory can be overkill for practice! And as you say 'TRUE is a thing of myth' - so lets forget it !!

I never argued that his code isn't valuable, efficient or worth using, (or better then the default C lib) just that using the word 'True' to describe it, is equivalent to claiming the invention of a perpetual motion machine; ie. academic suicide.

It can be a Really Really Ridiculously Good Looking (for people that CAN read good) Random Number Machine, but not a 'True' random number machine.

[madsci1016]

This doesn't happen if I use the ADC to continually change the seed value.

This may be, however,

A physical random number generator can be based on an essentially random atomic or subatomic physical phenomenon whose unpredictability can be traced to the laws of quantum mechanics. Sources of entropy include radioactive decay, thermal noise, shot noise, avalanche noise in Zener diodes, clock drift, the timing of actual movements of a hard disk read/write head, and radio noise.
However, physical phenomena and tools used to measure them generally feature asymmetries and systematic biases that make their outcomes not uniformly random.

[Admin]

Ok, better worded, '100% unpredictable random number generator'

Or even, 'functionally true random number generator'.


The user has no knowledge of the static electricity state, or the ability to control it, so its as good as random, no?

[madsci1016]

better, although I would still stray away form the absolute terms like '100%' and 'true' anything. It's enough of a gray area because both sides can argue convincing points, that's it's pretty accepted that there is no absolute truth either way.


We have this problem at my lab. We are one of the leading for-fronts in unmanned technology for they Navy, but anyone caught saying 'fully autonomous' or '100% autonomous' has pretty much put the brakes on their career permanently. Every systems requires human intervention at some point, thus negating a 'truly' autonomous system.


(And i still like my name better. Does no one remember zoolander? )

[Webbot]

Can we settle on a 'practical, quick and working random number generator' ? If not then I've "lost the will to contribute further" !

After all - a lot of the code relies on random() which is implemented by the AVR C library and is beyond all of our control!

[madsci1016]

Yeah, I'm done. The voices in my head have settled down now. 

As i said before; I'm sorry John if this got taken the wrong way at all. You code is absolutely wonderful and a big improvement over what was a sad excuse for 'random'. Please don't think any less of me for sort of 'calling you out'.

 And i don't think this discussion was a waste, as it could help educate any youngsters reading better understand the murky waters of the idea of 'truly random'; I think it breaks down to a mixture of physics and a dash of philosophy.

[Admin]

Well, my code is always open to criticism (ie suggested adjustments to make it 'more' random ). I'm not a professional programmer, after all