next topic »

[on:]

i am working on a research paper on how a logical computer can create a random number (because it's something of a paradox)  anyhow, i am well aware that the Arduino uses a pseudo-random mathematical algorithm in the "random" feature, but despite the open sourced nature of the Arduino i am having trouble finding out what that formula is exactly.  i could use any information, (but if the source is cite-able that would be preferred)

[Reply #1 on:]

Wikipedia is a good start: http://en.wikipedia.org/wiki/Random_number_generation
Arduino uses the GCC library, called 'libc'. That is were the rand() function is: http://www.nongnu.org/avr-libc/
On that page you can download the source code.
I downloaded the file: avr-libc-1.8.0.tar.bz2
In the folder libc/stdlib you will find two files: rand.c and random.c

[Reply #2 on:]

In volume 2 of "Donald E. Knuth, The Art of Computer Programming" is a whole chapter about creating random numbers. Perhaps this will help you.

best regards
Andreas

[Reply #3 on:]

i am working on a research paper on how a logical computer can create a random number

There are many papers written on this. e.g. google "random number generation site:arxiv.org" for cite-able papers

This is a pretty famous (and fast) algorithm:

Code:

/*
An example of a simple pseudo-random number generator is the
Multiply-with-carry method invented by George Marsaglia. It is
computationally fast and has good (albeit not cryptographically
strong) randomness properties.

m_w = <choose-initializer>;    // must not be zero
m_z = <choose-initializer>;    /* must not be zero
 
uint get_random()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit result
}
*/

void setup()
{
  Serial.begin(115200);
}

void loop()
{
  Serial.println(getRandom());
}


// An example of a simple pseudo-random number generator is the
// Multiply-with-carry method invented by George Marsaglia.
// two initializers (not null)
unsigned long m_w = 1;
unsigned long m_z = 2;

unsigned long getRandom()
{
    m_z = 36969L * (m_z & 65535L) + (m_z >> 16);
    m_w = 18000L * (m_w & 65535L) + (m_w >> 16);
    return (m_z << 16) + m_w;
}

[Reply #4 on:]

From an engineering/programming point of view, I wouldn't say it's a paradox.   It's an engineering challenge to make something random enough, or unpredictable enough for the intended application.

I think I could program a slot machine that's random-enough that you would run-out of quarters before you could ever figure-out the "pattern".    And, I wouldn't have to use any of those fancy quantum-physics or true-noise "tricks".   (I probably would so something with the "random" time between handle-pulls.)

If you are a philosopher, perhaps it is a paradox.  Or, perhaps the answer is simple... perhaps nothing is truly random since God (or a theoretical all-knowing being or an all-powerful machine) could always predict the next number...

[Reply #5 on:]

perhaps nothing is truly random since God (or a theoretical all-knowing being or an all-powerful machine) could always predict the next number...

Reminds me of a statement of an English mathematician (Roger Penrose?) about the Allmighty and stones. Transfered to the world of random generators it would be:

Can the Allmighty make a random generator that generates numbers he cannot predict?

[If he can, he is not allmighty as he cannot predict the numbers; if he can predict all numbers he cannot make the generator]

That does not say anything about the existance of truly random generators, only that our language can create paradoxal constructs.


disclaimer: no offense meant

[Reply #6 on:]

but despite the open sourced nature of the Arduino i am having trouble finding out what that formula is exactly.  i could use any information, (but if the source is cite-able that would be preferred)

Park-Miller minimum standard.  I'll get you reference in a minute...

[Reply #7 on:]

http://svn.savannah.nongnu.org/viewvc/*checkout*/trunk/avr-libc/libc/stdlib/random.c?root=avr-libc&content-type=text%2Fplain

[Reply #8 on:]

From an engineering/programming point of view, I wouldn't say it's a paradox.   It's an engineering challenge to make something random enough, or unpredictable enough for the intended application.

I think I could program a slot machine that's random-enough that you would run-out of quarters before you could ever figure-out the "pattern".    And, I wouldn't have to use any of those fancy quantum-physics or true-noise "tricks".   (I probably would so something with the "random" time between handle-pulls.)

If you are a philosopher, perhaps it is a paradox.  Or, perhaps the answer is simple... perhaps nothing is truly random since God (or a theoretical all-knowing being or an all-powerful machine) could always predict the next number...

You can make a pseudo-random generator (PRNG) that will pass lots of statistical 'tests' for randomness - but it may cryptographically weak as water.

You(*) can make a cryptographically secure pseudo random generator that - assuming it has a truly random seed value - generates unpredictable output (unpredictable in practice).  This will also pass all the statistical tests of course. A strong crypto RNG has the property that given any amount of its output you cannot (without peeking at the seed or hidden state) compute any of the other output (before or after the given sample) in practice.   Most simple PRNGs fail totally at this (and thus should never be used to generate cryptographic keys!!)  [ "In practice" means something like "cannot be done without a billion processors for a million years" ]

Or you can generate truly random numbers using a physical source of randomness.  This is a good way to provide a seed for a crypto PRNG.

(*) You, personally, cannot do this - you have to use an existing trusted design. In fact even the best experts struggle to make good crypto - the best crypto has been around for years and many experts have tried many times to break it and failed.  All roll-your-own crypto RNGs will be incredibly weak (to a very close approximation).