newlib/libc/stdlib/rand_r.c

   1 #include <stdlib.h>
   2
   3 /* Pseudo-random generator based on Minimal Standard by
   4    Lewis, Goodman, and Miller in 1969.
   5
   6    I[j+1] = a*I[j] (mod m)
   7
   8    where a = 16807
   9          m = 2147483647
  10
  11    Using Schrage's algorithm, a*I[j] (mod m) can be rewritten as:
  12
  13      a*(I[j] mod q) - r*{I[j]/q}      if >= 0
  14      a*(I[j] mod q) - r*{I[j]/q} + m  otherwise
  15
  16    where: {} denotes integer division
  17           q = {m/a} = 127773
  18           r = m (mod a) = 2836
  19
  20    note that the seed value of 0 cannot be used in the calculation as
  21    it results in 0 itself
  22 */
  23
  24 int
  25 rand_r (unsigned int *seed)
  26 {
  27         long k;
  28         long s = (long)(*seed);
  29         if (s == 0)
  30           s = 0x12345987;
  31         k = s / 127773;
  32         s = 16807 * (s - k * 127773) - 2836 * k;
  33         if (s < 0)
  34           s += 2147483647;
  35         (*seed) = (unsigned int)s;
  36         return (int)(s & RAND_MAX);
  37 }