Pages: [1]   Go Down
 Author Topic: pseudo-random algorithm?  (Read 503 times) 0 Members and 1 Guest are viewing this topic.
Offline
Newbie
Karma: 0
Posts: 10
 « on: May 03, 2012, 10:10:02 am » Bigger Smaller Reset

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)
 Logged

Offline
Edison Member
Karma: 9
Posts: 1000
 « Reply #1 on: May 03, 2012, 11:09:26 am » Bigger Smaller Reset

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/
In the folder libc/stdlib you will find two files: rand.c and random.c
 Logged

Hannover, Germany
Offline
Jr. Member
Karma: 0
Posts: 50
 « Reply #2 on: May 03, 2012, 11:34:28 am » Bigger Smaller Reset

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
 Logged

http://danimathblog.blogspot.com

#define true '/'/'/'
#define false '-'-'-'

Netherlands
Offline
Tesla Member
Karma: 91
Posts: 9449
In theory there is no difference between theory and practice, however in practice there are many...
 « Reply #3 on: May 03, 2012, 12:22:05 pm » Bigger Smaller Reset

Quote
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;
}
 Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -

Offline
God Member
Karma: 10
Posts: 778
 « Reply #4 on: May 03, 2012, 01:35:59 pm » Bigger Smaller Reset

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...
 Logged

Netherlands
Offline
Tesla Member
Karma: 91
Posts: 9449
In theory there is no difference between theory and practice, however in practice there are many...
 « Reply #5 on: May 03, 2012, 03:16:54 pm » Bigger Smaller Reset

Quote
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
 Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -

Global Moderator
Dallas
Offline
Shannon Member
Karma: 120
Posts: 10201
 « Reply #6 on: May 03, 2012, 03:49:55 pm » Bigger Smaller Reset

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...
 Logged

Global Moderator
Dallas
Offline
Shannon Member
Karma: 120
Posts: 10201
 « Reply #7 on: May 03, 2012, 03:54:19 pm » Bigger Smaller Reset

 Logged

0
Offline
Tesla Member
Karma: 73
Posts: 6638
Arduino rocks
 « Reply #8 on: May 03, 2012, 05:52:01 pm » Bigger Smaller Reset

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).
 Logged

 Pages: [1]   Go Up