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

   1 /* yarandom.c -- Yet Another Random Number Generator.
   2  * Copyright (c) 1997-2010 by Jamie Zawinski <jwz@jwz.org>
   3  *
   4  * Permission to use, copy, modify, distribute, and sell this software and its
   5  * documentation for any purpose is hereby granted without fee, provided that
   6  * the above copyright notice appear in all copies and that both that
   7  * copyright notice and this permission notice appear in supporting
   8  * documentation.  No representations are made about the suitability of this
   9  * software for any purpose.  It is provided "as is" without express or
  10  * implied warranty.
  11  */
  12
  13 /* The unportable mess that is rand(), random(), drand48() and friends led me
  14    to ask Phil Karlton <karlton@netscape.com> what the Right Thing to Do was.
  15    He responded with this.  It is non-cryptographically secure, reasonably
  16    random (more so than anything that is in any C library), and very fast.
  17
  18    I don't understand how it works at all, but he says "look at Knuth,
  19    Vol. 2 (original edition), page 26, Algorithm A.  In this case n=55,
  20    k=24 and m=2^32."
  21
  22    So there you have it.
  23
  24    ---------------------------
  25    Note: xlockmore 4.03a10 uses this very simple RNG:
  26
  27         if ((seed = seed % 44488 * 48271 - seed / 44488 * 3399) < 0)
  28           seed += 2147483647;
  29         return seed-1;
  30
  31    of which it says
  32
  33         ``Dr. Park's algorithm published in the Oct. '88 ACM  "Random Number
  34           Generators: Good Ones Are Hard To Find" His version available at
  35           ftp://cs.wm.edu/pub/rngs.tar Present form by many authors.''
  36
  37    Karlton says: ``the usual problem with that kind of RNG turns out to
  38    be unexepected short cycles for some word lengths.''
  39
  40    Karlton's RNG is faster, since it does three adds and two stores, while the
  41    xlockmore RNG does two multiplies, two divides, three adds, and one store.
  42
  43    Compiler optimizations make a big difference here:
  44        gcc -O:     difference is 1.2x.
  45        gcc -O2:    difference is 1.4x.
  46        gcc -O3:    difference is 1.5x.
  47        SGI cc -O:  difference is 2.4x.
  48        SGI cc -O2: difference is 2.4x.
  49        SGI cc -O3: difference is 5.1x.
  50    Irix 6.2; Indy r5k; SGI cc version 6; gcc version 2.7.2.1.
  51  */
  52
  53
  54 #ifdef HAVE_CONFIG_H
  55 # include "config.h"
  56 #endif
  57
  58 #ifdef HAVE_UNISTD_H
  59 # include <unistd.h>  /* for getpid() */
  60 #endif
  61 #include <sys/time.h> /* for gettimeofday() */
  62
  63 #include "yarandom.h"
  64 # undef ya_rand_init
  65
  66
  67 /* The following 'random' numbers are taken from CRC, 18th Edition, page 622.
  68    Each array element was taken from the corresponding line in the table,
  69    except that a[0] was from line 100. 8s and 9s in the table were simply
  70    skipped. The high order digit was taken mod 4.
  71  */
  72 #define VectorSize 55
  73 static unsigned int a[VectorSize] = {
  74  035340171546, 010401501101, 022364657325, 024130436022, 002167303062, /*  5 */
  75  037570375137, 037210607110, 016272055420, 023011770546, 017143426366, /* 10 */
  76  014753657433, 021657231332, 023553406142, 004236526362, 010365611275, /* 14 */
  77  007117336710, 011051276551, 002362132524, 001011540233, 012162531646, /* 20 */
  78  007056762337, 006631245521, 014164542224, 032633236305, 023342700176, /* 25 */
  79  002433062234, 015257225043, 026762051606, 000742573230, 005366042132, /* 30 */
  80  012126416411, 000520471171, 000725646277, 020116577576, 025765742604, /* 35 */
  81  007633473735, 015674255275, 017555634041, 006503154145, 021576344247, /* 40 */
  82  014577627653, 002707523333, 034146376720, 030060227734, 013765414060, /* 45 */
  83  036072251540, 007255221037, 024364674123, 006200353166, 010126373326, /* 50 */
  84  015664104320, 016401041535, 016215305520, 033115351014, 017411670323  /* 55 */
  85 };
  86
  87 static int i1, i2;
  88
  89 unsigned int
  90 ya_random (void)
  91 {
  92   register int ret = a[i1] + a[i2];
  93   a[i1] = ret;
  94   if (++i1 >= VectorSize) i1 = 0;
  95   if (++i2 >= VectorSize) i2 = 0;
  96   return ret;
  97 }
  98
  99 void
 100 ya_rand_init(unsigned int seed)
 101 {
 102   int i;
 103   if (seed == 0)
 104     {
 105       struct timeval tp;
 106 #ifdef GETTIMEOFDAY_TWO_ARGS
 107       struct timezone tzp;
 108       gettimeofday(&tp, &tzp);
 109 #else
 110       gettimeofday(&tp);
 111 #endif
 112       /* Since the multiplications will have a larger effect on the
 113          upper bits than the lower bits, after every addition in the
 114          seed, perform a bitwise rotate by an odd number, resulting
 115          in a better distribution of randomness throughout the bits.
 116          -- Brian Carlson, 2010.
 117        */
 118 #define ROT(X,N) (((X)<<(N)) | ((X)>>((sizeof(unsigned int)*8)-(N))))
 119       seed = (999 * tp.tv_sec);
 120       seed = ROT (seed, 11);
 121       seed += (1001 * tp.tv_usec);
 122       seed = ROT (seed, 7);
 123       seed += (1003 * getpid());
 124       seed = ROT (seed, 13);
 125     }
 126
 127   a[0] += seed;
 128   for (i = 1; i < VectorSize; i++)
 129     {
 130       seed = seed*999;
 131       seed = ROT (seed, 9);
 132       seed += a[i-1]*1001;
 133       seed = ROT (seed, 15);
 134       a[i] += seed;
 135     }
 136
 137   i1 = a[0] % VectorSize;
 138   i2 = (i1 + 24) % VectorSize;
 139 }