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

   1 /* yarandom.c -- 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    Note: xlockmore 4.03a10 uses this very simple RNG:
  16
  17         if ((seed = seed % 44488 * 48271 - seed / 44488 * 3399) < 0)
  18           seed += 2147483647;
  19         return seed-1;
  20
  21    of which it says
  22
  23         ``Dr. Park's algorithm published in the Oct. '88 ACM  "Random Number
  24           Generators: Good Ones Are Hard To Find" His version available at
  25           ftp://cs.wm.edu/pub/rngs.tar Present form by many authors.''
  26
  27    Karlton says: ``the usual problem with that kind of RNG turns out to
  28    be unexepected short cycles for some word lengths.''
  29
  30    Karlton's RNG is faster, since it does three adds and two stores, while the
  31    xlockmore RNG does two multiplies, two divides, three adds, and one store.
  32
  33    Compiler optimizations make a big difference here:
  34        gcc -O:     difference is 1.2x.
  35        gcc -O2:    difference is 1.4x.
  36        gcc -O3:    difference is 1.5x.
  37        SGI cc -O:  difference is 2.4x.
  38        SGI cc -O2: difference is 2.4x.
  39        SGI cc -O3: difference is 5.1x.
  40    Irix 6.2; Indy r5k; SGI cc version 6; gcc version 2.7.2.1.
  41  */
  42
  43
  44 #ifdef HAVE_CONFIG_H
  45 # include "config.h"
  46 #endif
  47
  48 #ifdef HAVE_UNISTD_H
  49 # include <unistd.h>  /* for getpid() */
  50 #endif
  51 #include <sys/time.h> /* for gettimeofday() */
  52
  53 #include "yarandom.h"
  54
  55
  56 /* The following 'random' numbers are taken from CRC, 18th Edition, page 622.
  57    Each array element was taken from the corresponding line in the table,
  58    except that a[0] was from line 100. 8s and 9s in the table were simply
  59    skipped. The high order digit was taken mod 4.
  60  */
  61 #define VectorSize 55
  62 static unsigned int a[VectorSize] = {
  63  035340171546, 010401501101, 022364657325, 024130436022, 002167303062, /*  5 */
  64  037570375137, 037210607110, 016272055420, 023011770546, 017143426366, /* 10 */
  65  014753657433, 021657231332, 023553406142, 004236526362, 010365611275, /* 14 */
  66  007117336710, 011051276551, 002362132524, 001011540233, 012162531646, /* 20 */
  67  007056762337, 006631245521, 014164542224, 032633236305, 023342700176, /* 25 */
  68  002433062234, 015257225043, 026762051606, 000742573230, 005366042132, /* 30 */
  69  012126416411, 000520471171, 000725646277, 020116577576, 025765742604, /* 35 */
  70  007633473735, 015674255275, 017555634041, 006503154145, 021576344247, /* 40 */
  71  014577627653, 002707523333, 034146376720, 030060227734, 013765414060, /* 45 */
  72  036072251540, 007255221037, 024364674123, 006200353166, 010126373326, /* 50 */
  73  015664104320, 016401041535, 016215305520, 033115351014, 017411670323  /* 55 */
  74 };
  75
  76 static int i1, i2;
  77
  78 unsigned int
  79 ya_random (void)
  80 {
  81   register int ret = a[i1] + a[i2];
  82   a[i1] = ret;
  83   if (++i1 >= VectorSize) i1 = 0;
  84   if (++i2 >= VectorSize) i2 = 0;
  85   return ret;
  86 }
  87
  88 void
  89 ya_rand_init(unsigned int seed)
  90 {
  91   int i;
  92   if (seed == 0)
  93     {
  94       struct timeval tp;
  95 #ifdef GETTIMEOFDAY_TWO_ARGS
  96       struct timezone tzp;
  97       gettimeofday(&tp, &tzp);
  98 #else
  99       gettimeofday(&tp);
 100 #endif
 101       /* ignore overflow */
 102       seed = (999*tp.tv_sec) + (1001*tp.tv_usec) + (1003 * getpid());
 103     }
 104
 105   a[0] += seed;
 106   for (i = 1; i < VectorSize; i++)
 107     {
 108       seed = a[i-1]*1001 + seed*999;
 109       a[i] += seed;
 110     }
 111
 112   i1 = a[0] % VectorSize;
 113   i2 = (i1 + 024) % VectorSize;
 114 }