source: trunk/third/xscreensaver/utils/yarandom.c @ 20148

Revision 20148, 4.2 KB checked in by ghudson, 21 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r20147, which included commits to RCS files with non-trunk default branches.
Line 
1/* yarandom.c -- Yet Another Random Number Generator.
2 * Copyright (c) 1997, 1998, 2003 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=20 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
73static 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
87static int i1, i2;
88
89unsigned int
90ya_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
99void
100ya_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      /* ignore overflow */
113      seed = (999*tp.tv_sec) + (1001*tp.tv_usec) + (1003 * getpid());
114    }
115
116  a[0] += seed;
117  for (i = 1; i < VectorSize; i++)
118    {
119      seed = a[i-1]*1001 + seed*999;
120      a[i] += seed;
121    }
122
123  i1 = a[0] % VectorSize;
124  i2 = (i1 + 024) % VectorSize;
125}
Note: See TracBrowser for help on using the repository browser.