1 #include <stdlib.h> 2 3 /* 4 * algorithm by 5 * D. P. Mitchell & J. A. Reeds 6 */ 7 #define LEN 607 8 #define TAP 273 9 #define MASK 0x7fffffffL 10 #define A 48271 11 #define M 2147483647 12 #define Q 44488 13 #define R 3399 14 15 typedef unsigned long ulong; 16 17 static ulong rng_vec[LEN]; 18 static ulong* rng_tap = rng_vec; 19 static ulong* rng_feed = 0; 20 21 void srand(unsigned int seed)22srand(unsigned int seed) 23 { 24 long lo, hi, x; 25 int i; 26 27 rng_tap = rng_vec; 28 rng_feed = rng_vec+LEN-TAP; 29 seed = seed%M; 30 if(0 && seed < 0) /* seed is unsigned */ 31 seed += M; 32 if(seed == 0) 33 seed = 89482311; 34 x = seed; 35 /* 36 * Initialize by x[n+1] = 48271 * x[n] mod (2**31 - 1) 37 */ 38 for(i = -20; i < LEN; i++) { 39 hi = x / Q; 40 lo = x % Q; 41 x = A*lo - R*hi; 42 if(x < 0) 43 x += M; 44 if(i >= 0) 45 rng_vec[i] = x; 46 } 47 } 48 49 static long lrand(void)50lrand(void) 51 { 52 ulong x; 53 54 rng_tap--; 55 if(rng_tap < rng_vec) { 56 if(rng_feed == 0) { 57 srand(1); 58 rng_tap--; 59 } 60 rng_tap += LEN; 61 } 62 rng_feed--; 63 if(rng_feed < rng_vec) 64 rng_feed += LEN; 65 x = (*rng_feed + *rng_tap) & MASK; 66 *rng_feed = x; 67 return x; 68 } 69 70 int rand(void)71rand(void) 72 { 73 74 return lrand() & 0x7fff; 75 } 76