Hi all,
While browsing the source codes, I noticed this implementation of randomSeed (in WMath.cpp):
void randomSeed(unsigned long seed)
{
if (seed != 0) {
srandom(seed);
}
}
What is the purpose or rationale behind the "seed != 0" check? After all, zero is a legitimate parameter value for srandom.
Thanks,
Ido
What is the default value if srandom() is not called? Is that any different from calling srandom(0)?
PaulS:
What is the default value if srandom() is not called? Is that any different from calling srandom(0)?
First of all, it is different (I checked this with a little Arduino program - it seems the default value is actually 1, but I'm not certain about that).
Second, randomSeed is sometimes used to "reset" the random number sequence - not just at the beginning of the program - and for these cases, I don't see why 0 should get this special treatment.
It might be the case that for the value 0 the random algorithm breaks in some way. (did’t look at the underlying algorithm. This could result e.g. in a shorter cycle
(oversimplified example)
randomn+1 = randomn * some complex formula
if random0 == 0 we get a very short cycle 
robtillaart:
It might be the case that for the value 0 the random algorithm breaks in some way. (did’t look at the underlying algorithm. This could result e.g. in a shorter cycle(oversimplified example)
randomn+1 = randomn * some complex formulaif random0 == 0 we get a very short cycle
Heh, that’s a wild assumption 
I can tell you that the cycle is certainly not THAT short - and I doubt it’s any different than for other numbers.
That IF kind of breaks the functionality of randomSeed, and it’s neither mentioned in the function reference nor explained anywhere (that I saw).
Not that wild,
have a look at the random generator invented by George Marsaglia
/*
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.[7] (note that this example is not
thread safe):
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
}
*/
Oh, I edited instead of adding a new post… 
Anyway, to answer myself - the source for srandom is in AVR Libc’s “random.c” (I assume that’s what Arduino uses). Here are the relevant segments:
do_random(unsigned long *ctx) {
/*
* Compute x = (7^5 * x) mod (2^31 - 1)
* wihout overflowing 31 bits:
* (2^31 - 1) = 127773 * (7^5) + 2836
* From "Random number generators: good ones are hard to find",
* Park and Miller, Communications of the ACM, vol. 31, no. 10,
* October 1988, p. 1195.
*/
long hi, lo, x;
x = *ctx;
/* Can't be initialized with 0, so use another value. */
if (x == 0)
x = 123459876L;
hi = x / 127773L;
lo = x % 127773L;
x = 16807L * lo - 2836L * hi;
if (x < 0)
x += 0x7fffffffL;
return ((*ctx = x) % ((unsigned long)RANDOM_MAX + 1));
}
static unsigned long next = 1;
long random(void) {
return do_random(&next);
}
void srandom(unsigned long seed) {
next = seed;
}
So what do we learn:
you are completely right, the value zero is handled separately.
but also notice that the value 0 would result in the next value 0
hi = x / 127773L;
lo = x % 127773L;
x = 16807L * lo - 2836L * hi;
hi becomes 0
lo becomes 0
x becomes 0
robtillaart:
but also notice that the value 0 would result in the next value 0
But it'll never be 0. Even if do_random returns 0 (which is possible), that return value is also fed back into the seed ("*xtc"), so the next time around it will be spotted and assigned 123459876L instead.
It did make me wonder, though, how long it would take to get a 0 from do_random, because that would cause the random sequence to "reset" to a known seed, and that can be a security loophole. I wrote a program that's running in the background right now, looking for a 0 for various seeds (0-1023, can you guess why? 
). So far, none of them got to 0 after 100M iterations. Maybe there's a mathematical safeguard hidden in the formulas?
Again, I'll answer myself...
I looked at the document mentioned in do_random's comments ("Random number generators: good ones are hard to find", Park and Miller, Communications of the ACM, vol. 31, no. 10, October 1988, p. 1195.) - it's available on the web - and although the math is beyond me, they do seem to suggest that 0 is impossible. That's for the "dangerous" value of the seed. The function itself is capable of returning 0 to the user because it does a modulus operation on the result.
Only question left now - is it worthwhile to ask for a fix to Arduino's randomSeed() ?
The math saveguard should be in the line
x = 16807L * lo - 2836L * hi;
16807 = 75 and 2836 = 22*709 so these factors are prime wrt each other.
There is only value pair possible for hi and lo for which the formula can return 0: lo = 2836 and hi = 16807
given that
hi = x / 127773L;
lo = x % 127773L;
==>
x = hi * 127773 + lo ( = 2,147,480,811 + 2,836 = 2,147,483,647 == 231 -1)
so if you use 2,147,483,647 as seed the next value should be a 0.
static uint32_t next = 1;
void setup()
{
Serial.begin(115200);
Serial.print("Start ");
Serial.println(__FILE__);
next = 2147483647 ;
uint32_t r = doo_random(&next);
Serial.println(r, DEC);
Serial.println(next, DEC);
r = doo_random(&next);
Serial.println(r, DEC);
Serial.println(next, DEC);
}
void loop()
{
}
uint32_t doo_random(unsigned long *ctx) {
/*
* Compute x = (7^5 * x) mod (2^31 - 1)
* wihout overflowing 31 bits:
* (2^31 - 1) = 127773 * (7^5) + 2836
* From "Random number generators: good ones are hard to find",
* Park and Miller, Communications of the ACM, vol. 31, no. 10,
* October 1988, p. 1195.
*/
long hi, lo, x;
x = *ctx;
/* Can't be initialized with 0, so use another value. */
if (x == 0)
x = 123459876L;
hi = x / 127773L;
lo = x % 127773L;
x = 16807L * lo - 2836L * hi;
if (x < 0)
x += 0x7fffffffL;
return ((*ctx = x) % ((unsigned long)RANDOM_MAX + 1));
}
Yes it is good to propose a fix as it will reduce the footprint of all sketches with a few bytes.
And resources can sometimes be scarce ... every byte counts.
BTW
srandom(2147483647);
int n = random();
Serial.println(n);
works too
robtillaart:
- analogRead as seed
2 points
robtillaart:
so if you use 2,147,483,647 as seed the next value should be a 0.
Indeed. So the question becomes, will we ever get to a seed value of 2,147,483,647 by calculation. And this, at least according to my simple brute-force test, is impossible.
What if we send 2,147,483,647 as a random seed ourselves? As expected (and as you showed while I was typing!), the first result of random(whatever) would be 0.
Final note from me (I hope! ) about this issue:
The "security loophole" I was worried about earlier is really a non-issue. Even if the algorithm was able to produce the value 0, the chance of that happening should be around 1 / 2^32 - same as for any other number, so no backdoor for evil hackers there.
as for PRNGs (pseudo-random number generators) the Arduino random API functions are not ANSI C lib compatible, I use my own ones which are fine and stdlib compliant - at least I never encounterd issues so far:
#define LRAND_MAX 32767
#define srand(seed) randomSeed(seed)
#define rand() random(LRAND_MAX)
#define rando() ((float)rand()/(LRAND_MAX+1))
as I was not sure how RAND_MAX is processed by Arduino for AVR vs. ARM cpus I definied my own LRAND_MAX range.
you also may choose
#define LRAND_MAX 2147483647 // == LONG_MAX
instead.
rand() Return Value: An integer value >= 0 and <= LRAND_MAX.
http://www.cplusplus.com/reference/cstdlib/rand/
v0 = rand(); // v0 in the range 0 to RAND_MAX
v1 = rand() % 100; // v1 in the range 0 to 99
v2 = rand() % 100 + 1; // v2 in the range 1 to 100
v3 = rand() % 30 + 1985; // v3 in the range 1985-2014
vf = rando(); // vf (float) in the range 0<= vf <1
Anyway, the PRNG algs are all different and what is generated depends on the compiler and the targeted system - many PRNGs are awfully bad non-random actually.
Also, how the srand() function seeds the rand() function is obscured and depends on the rand implementation. It does nothing different but to transfer a start value to the rand() function.
For srand(seed), perhaps 0 is handled seperately to avoid division by zero, but that may vary to the actual PRNG which is used.
Note that a PRNG initialized by a certain fixed value will always generate identical pseudo-random series to infinity, which can be used for code testing purposes - but which will not make much sense for common PRNG use!
(edit:)
As Arduino boards don’t provide a system clock - I’m using my own “randomized rand() initialization” by
srand ( (unsigned int)( millis() + AnalogRead(A0) ) );
If I personally am uncertain about the system PRNG and so I want to play it safe, I’m usinig the Kernighan & Ritchie LCG (linear congruence generator) or, even better, a Mersenne Twister TT800.
HTH!