git.hungrycats.org Git - xscreensaver/blob - utils/yarandom.c

   1 /* ya_random -- Yet Another Random Number Generator.
   2
   3    The unportable mess that is rand(), random(), drand48() and friends led me
   4    to ask Phil Karlton <karlton@netscape.com> what the Right Thing to Do was.
   5    He responded with this.  It is non-cryptographically secure, reasonably
   6    random (more so than anything that is in any C library), and very fast.
   7
   8    I don't understand how it works at all, but he says "look at Knuth,
   9    Vol. 2 (original edition), page 26, Algorithm A.  In this case n=55,
  10    k=20 and m=2^32."
  11
  12    So there you have it.
  13  */
  14
  15 #include <unistd.h>   /* for getpid() */
  16 #include <sys/time.h> /* for gettimeofday() */
  17
  18
  19 /* The following 'random' numbers are taken from CRC, 18th Edition, page 622.
  20    Each array element was taken from the corresponding line in the table,
  21    except that a[0] was from line 100. 8s and 9s in the table were simply
  22    skipped. The high order digit was taken mod 4.
  23  */
  24 #define VectorSize 55
  25 static unsigned int a[VectorSize] = {
  26  035340171546, 010401501101, 022364657325, 024130436022, 002167303062, /*  5 */
  27  037570375137, 037210607110, 016272055420, 023011770546, 017143426366, /* 10 */
  28  014753657433, 021657231332, 023553406142, 004236526362, 010365611275, /* 14 */
  29  007117336710, 011051276551, 002362132524, 001011540233, 012162531646, /* 20 */
  30  007056762337, 006631245521, 014164542224, 032633236305, 023342700176, /* 25 */
  31  002433062234, 015257225043, 026762051606, 000742573230, 005366042132, /* 30 */
  32  012126416411, 000520471171, 000725646277, 020116577576, 025765742604, /* 35 */
  33  007633473735, 015674255275, 017555634041, 006503154145, 021576344247, /* 40 */
  34  014577627653, 002707523333, 034146376720, 030060227734, 013765414060, /* 45 */
  35  036072251540, 007255221037, 024364674123, 006200353166, 010126373326, /* 50 */
  36  015664104320, 016401041535, 016215305520, 033115351014, 017411670323  /* 55 */
  37 };
  38
  39 static int i1, i2;
  40
  41 unsigned int ya_random()
  42 {
  43   register int ret = a[i1] + a[i2];
  44   a[i1] = ret;
  45   i1 = i1 >= VectorSize ? 0 : i1 + 1;
  46   i2 = i2 >= VectorSize ? 0 : i2 + 1;
  47   return ret;
  48 }
  49
  50 void ya_rand_init(seed)
  51    register unsigned int seed;
  52 {
  53   int i;
  54   if (seed == 0)
  55     {
  56       struct timeval tp;
  57       struct timezone tzp;
  58       gettimeofday(&tp, &tzp);
  59       /* ignore overflow */
  60       seed = (999*tp.tv_sec) + (1001*tp.tv_usec) + (1003 * getpid());
  61     }
  62
  63   a[0] += seed;
  64   for (i = 1; i < VectorSize; i++)
  65     {
  66       seed = a[i-1]*1001 + seed*999;
  67       a[i] += seed;
  68     }
  69
  70   i1 = a[0] % VectorSize;
  71   i2 = (i1 + 024) % VectorSize;
  72 }