randomSeed: Why is 0 ignored?

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 :wink:

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 formula

if random0 == 0 we get a very short cycle :wink:

Heh, that’s a wild assumption :slight_smile: 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… :confused:

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:

  1. As I guessed above, the default seed is indeed 1 :slight_smile:
  2. The algorithm does dislike zero, but that’s handled at the implementation level - there’s no point in the functionality-breaking extra check in randomSeed().

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? :slight_smile: ). 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() ?

  1. analogRead as seed :slight_smile:

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 :slight_smile:

robtillaart:

  1. analogRead as seed :slight_smile:

2 points :slight_smile:

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! :slight_smile: ) 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!