Commit | Line | Data |
---|---|---|
3144ee8a AT |
1 | /* yarandom.c -- Yet Another Random Number Generator. |
2 | * Copyright (c) 1997-2014 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 = (999U * (unsigned int) tp.tv_sec); | |
120 | seed = ROT (seed, 11); | |
121 | seed += (1001 * (unsigned int) tp.tv_usec); | |
122 | seed = ROT (seed, 7); | |
123 | seed += (1003 * (unsigned int) 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 | } |