ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/deliantra/server/include/rng.h
(Generate patch)

Comparing deliantra/server/include/rng.h (file contents):
Revision 1.2 by root, Tue Jul 6 20:00:46 2010 UTC vs.
Revision 1.3 by root, Sat Jul 10 21:07:47 2010 UTC

… …
26#include <compiler.h> 26#include <compiler.h>
27 27
28// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213. 28// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213.
29// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps 29// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
30// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps 30// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
31struct tausworthe_random_generator 31struct tausworthe_rng
32{ 32{
33 uint32_t state [4]; 33 uint32_t state [4];
34 34
35 void seed (uint32_t seed); 35 void seed (uint32_t seed);
36 uint32_t next (); 36 uint32_t next ();
… …
39// Xorshift RNGs, George Marsaglia 39// Xorshift RNGs, George Marsaglia
40// http://www.jstatsoft.org/v08/i14/paper 40// http://www.jstatsoft.org/v08/i14/paper
41// this one is about 40% faster than the tausworthe one above (i.e. not much), 41// this one is about 40% faster than the tausworthe one above (i.e. not much),
42// despite the inlining, and has the issue of only creating 2**32-1 numbers. 42// despite the inlining, and has the issue of only creating 2**32-1 numbers.
43// see also http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf 43// see also http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
44struct xorshift_random_generator 44struct xorshift_rng
45{ 45{
46 uint32_t x, y; 46 uint32_t x, y;
47 47
48 void seed (uint32_t seed) 48 void seed (uint32_t seed)
49 { 49 {
… …
58 y = y ^ (y >> 13) ^ t ^ (t >> 10); 58 y = y ^ (y >> 13) ^ t ^ (t >> 10);
59 return y; 59 return y;
60 } 60 }
61}; 61};
62 62
63template<uint32_t A, uint32_t B>
64struct lc_rng
65{
66 uint32_t x;
67
68 void seed (uint32_t seed)
69 {
70 x = seed;
71 }
72
73 uint32_t next ()
74 {
75 x = x * A + B;
76 return x;
77 }
78};
79
80typedef lc_rng<3039177861U, 0> borosh_niederreiter_rng;
81typedef lc_rng<2147001325U, 715136305U> bcpl_rng;
82
63template<typename T, int N, int k> 83template<typename T, int N, int k>
64struct gfsr_random_generator 84struct gfsr_rng
65{ 85{
66 int i; 86 int i;
67 T x[N]; 87 T x[N];
68 88
69 // rng must have same bitwidth as T 89 // rng must have same bitwidth as T
… …
87 } 107 }
88 108
89 // actually should subclass to gfsr32... :) 109 // actually should subclass to gfsr32... :)
90 void seed (uint32_t seed) 110 void seed (uint32_t seed)
91 { 111 {
92 xorshift_random_generator rng; 112 xorshift_rng rng;
93 113
94 rng.seed (seed); 114 rng.seed (seed);
95 this->seed_rng (rng); 115 this->seed_rng (rng);
96 } 116 }
97 117
… …
110 } 130 }
111}; 131};
112 132
113// these are about 2-3 times faster than tausworthe, non-inlined, 133// these are about 2-3 times faster than tausworthe, non-inlined,
114// and likely of higher quality. 134// and likely of higher quality.
115typedef gfsr_random_generator<uint32_t, 250, 103> r250_random_generator; 135typedef gfsr_rng<uint32_t, 250, 103> r250_rng;
116typedef gfsr_random_generator<uint32_t, 521, 168> r521_random_generator; 136typedef gfsr_rng<uint32_t, 521, 168> r521_rng;
117 137
118// freeciv uses this one, so it's good enough for us :) 138// freeciv uses this one, so it's good enough for us :)
119typedef gfsr_random_generator<uint32_t, 55, 24> freeciv_random_generator; 139typedef gfsr_rng<uint32_t, 55, 24> freeciv_rng;
120 140
121// this one should be high quality, but is slightly slower than tausworthe 141// this one should be high quality, but is slightly slower than tausworthe
122struct r250521_random_generator 142struct r250521_rng
123{ 143{
124 r250_random_generator r250; 144 r250_rng r250;
125 r521_random_generator r521; 145 r521_rng r521;
126 146
127 void seed (uint32_t seed); 147 void seed (uint32_t seed);
128 uint32_t next (); 148 uint32_t next ();
129}; 149};
130 150
… …
156 return is_constant (r_min <= r_max) && r_min <= r_max 176 return is_constant (r_min <= r_max) && r_min <= r_max
157 ? r_min + operator ()(r_max - r_min + 1) 177 ? r_min + operator ()(r_max - r_min + 1)
158 : get_range (r_min, r_max); 178 : get_range (r_min, r_max);
159 } 179 }
160 180
161 // return a number within the half-open interval [0..1[
162 double operator ()()
163 {
164 return this->next () / (double)0x100000000ULL;
165 }
166
167 uint32_t get_u32 (); 181 uint32_t get_u32 ();
168 uint64_t get_u64 (); 182 uint64_t get_u64 ();
183 float get_float ();
184 double get_double ();
185
186 // return a number within the half-open interval [0..1[
187 double operator () ()
188 {
189 return get_double ();
190 }
191
192 uint32_t poisson (double mean);
169 193
170protected: 194protected:
171 uint32_t get_range (uint32_t r_max); 195 uint32_t get_range (uint32_t r_max);
172 int get_range (int r_min, int r_max); 196 int get_range (int r_min, int r_max);
173}; 197};
174 198
175// the default rng used in the game 199// the default rng used in the game
176typedef random_number_generator<freeciv_random_generator> rand_gen; 200typedef random_number_generator<freeciv_rng> rand_gen;
177 201
178// used when we often seed 202// used when we often seed
179typedef random_number_generator<tausworthe_random_generator> seedable_rand_gen; 203typedef random_number_generator<tausworthe_rng> seedable_rand_gen;
180 204
181extern rand_gen rndm, rmg_rndm; 205extern rand_gen rndm, rmg_rndm;
182 206
183#endif 207#endif
184 208

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines