| 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 |
|---|
| 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 | /* 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 | } |
|---|
