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.1 by root, Fri Jul 2 02:00:47 2010 UTC vs.
Revision 1.7 by root, Tue Apr 26 14:41:36 2011 UTC

1/* 1/*
2 * This file is part of Deliantra, the Roguelike Realtime MMORPG. 2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 * 3 *
4 * Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team 4 * Copyright (©) 2010,2011 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * 5 *
6 * Deliantra is free software: you can redistribute it and/or modify it under 6 * Deliantra is free software: you can redistribute it and/or modify it under
7 * the terms of the Affero GNU General Public License as published by the 7 * the terms of the Affero GNU General Public License as published by the
8 * Free Software Foundation, either version 3 of the License, or (at your 8 * Free Software Foundation, either version 3 of the License, or (at your
9 * option) any later version. 9 * option) any later version.
… …
23#ifndef RNG_H__ 23#ifndef RNG_H__
24#define RNG_H__ 24#define RNG_H__
25 25
26#include <compiler.h> 26#include <compiler.h>
27 27
28typedef uint32_t seed_t; // overkill
29
28// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213. 30// 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 31// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
30// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps 32// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
31struct tausworthe_random_generator 33struct tausworthe_rng
32{ 34{
33 uint32_t state [4]; 35 uint32_t state [4];
34 36
35 void seed (uint32_t seed); 37 void seed (uint32_t seed);
36 uint32_t next (); 38 uint32_t next ();
… …
39// Xorshift RNGs, George Marsaglia 41// Xorshift RNGs, George Marsaglia
40// http://www.jstatsoft.org/v08/i14/paper 42// http://www.jstatsoft.org/v08/i14/paper
41// this one is about 40% faster than the tausworthe one above (i.e. not much), 43// 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. 44// 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 45// see also http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
44struct xorshift_random_generator 46struct xorshift_rng
45{ 47{
46 uint32_t x, y; 48 uint32_t x, y;
47 49
48 void seed (uint32_t seed) 50 void seed (uint32_t seed)
49 { 51 {
50 x = seed | 1; 52 x = seed ? seed : 0xdeadbeef;
51 y = x * 69069U; 53 y = x * 69069U;
52 } 54 }
53 55
54 uint32_t next () 56 uint32_t next ()
55 { 57 {
… …
58 y = y ^ (y >> 13) ^ t ^ (t >> 10); 60 y = y ^ (y >> 13) ^ t ^ (t >> 10);
59 return y; 61 return y;
60 } 62 }
61}; 63};
62 64
65template<uint32_t A, uint32_t B>
66struct lc_rng
67{
68 uint32_t x;
69
70 void seed (uint32_t seed)
71 {
72 x = seed;
73 }
74
75 uint32_t next ()
76 {
77 x = x * A + B;
78 return x;
79 }
80};
81
82typedef lc_rng<3039177861U, 0> borosh_niederreiter_rng;
83typedef lc_rng<2147001325U, 715136305U> bcpl_rng;
84
63template<typename T, int N, int k> 85template<typename T, int N, int k>
64struct gfsr_random_generator 86struct gfsr_rng
65{ 87{
66 int i; 88 int i;
67 T x[N]; 89 T x[N];
68 90
69 // rng must have same bitwidth as T 91 // rng must have same bitwidth as T
… …
85 } 107 }
86 while (i); 108 while (i);
87 } 109 }
88 110
89 // actually should subclass to gfsr32... :) 111 // actually should subclass to gfsr32... :)
90 void seed (uint32_t seed) 112 void seed (seed_t seed)
91 { 113 {
92 xorshift_random_generator rng; 114 xorshift_rng rng;
93 115
94 rng.seed (seed); 116 rng.seed (seed);
95 this->seed_rng (rng); 117 this->seed_rng (rng);
96 } 118 }
97 119
… …
110 } 132 }
111}; 133};
112 134
113// these are about 2-3 times faster than tausworthe, non-inlined, 135// these are about 2-3 times faster than tausworthe, non-inlined,
114// and likely of higher quality. 136// and likely of higher quality.
115typedef gfsr_random_generator<uint32_t, 250, 103> r250_random_generator; 137typedef gfsr_rng<uint32_t, 250, 103> r250_rng;
116typedef gfsr_random_generator<uint32_t, 521, 168> r521_random_generator; 138typedef gfsr_rng<uint32_t, 521, 168> r521_rng;
117 139
118// freeciv uses this one, so it's good enough for us :) 140// freeciv uses this one, so it's good enough for us :)
119typedef gfsr_random_generator<uint32_t, 55, 24> freeciv_random_generator; 141typedef gfsr_rng<uint32_t, 55, 24> freeciv_rng;
120 142
121// this one should be high quality, but is slightly slower than tausworthe 143// this one should be high quality, but is slightly slower than tausworthe
122struct r250521_random_generator 144struct r250521_rng
123{ 145{
124 r250_random_generator r250; 146 r250_rng r250;
125 r521_random_generator r521; 147 r521_rng r521;
126 148
127 void seed (uint32_t seed); 149 void seed (uint32_t seed);
128 uint32_t next (); 150 uint32_t next ();
129}; 151};
130 152
131// this is actually an adaptor that provides different types 153// this is actually an adaptor that provides different
132// of random numbers. 154// distributions of random numbers.
133template<class generator> 155template<class generator>
134struct random_number_generator : generator 156struct random_number_generator : generator
135{ 157{
158 random_number_generator ()
159 {
160 }
161
162 random_number_generator (seed_t seed)
163 {
164 this->seed (seed);
165 }
166
136 // uniform distribution, [0 .. num - 1] 167 // uniform distribution, [0 .. num - 1]
137 uint32_t operator ()(uint32_t num) 168 uint32_t operator ()(uint32_t num)
138 { 169 {
139 return !is_constant (num) ? get_range (num) // non-constant 170 return !is_constant (num) ? get_range (num) // non-constant
140 : num & (num - 1) ? (this->next () * (uint64_t)num) >> 32U // constant, non-power-of-two 171 : num & (num - 1) ? (this->next () * (uint64_t)num) >> 32U // constant, non-power-of-two
… …
147 return is_constant (r_min <= r_max) && r_min <= r_max 178 return is_constant (r_min <= r_max) && r_min <= r_max
148 ? r_min + operator ()(r_max - r_min + 1) 179 ? r_min + operator ()(r_max - r_min + 1)
149 : get_range (r_min, r_max); 180 : get_range (r_min, r_max);
150 } 181 }
151 182
152 // return a number within the half-open interval [0..1[
153 double operator ()()
154 {
155 return this->next () / (double)0x100000000ULL;
156 }
157
158 uint32_t get_u32 (); 183 uint32_t get_u32 ();
159 uint64_t get_u64 (); 184 uint64_t get_u64 ();
185 float get_float ();
186 double get_double ();
187
188 // return a number within the half-open interval [0..1[
189 double operator () ()
190 {
191 return get_double ();
192 }
193
194 uint32_t poisson (double mean);
160 195
161protected: 196protected:
162 uint32_t get_range (uint32_t r_max); 197 uint32_t get_range (uint32_t r_max);
163 int get_range (int r_min, int r_max); 198 int get_range (int r_min, int r_max);
164}; 199};
165 200
166// the default rng used in the game 201// the default rng used in the game
167typedef random_number_generator<freeciv_random_generator> rand_gen; 202typedef random_number_generator<freeciv_rng> rand_gen;
203
204// used when we often seed
205typedef random_number_generator<tausworthe_rng> seedable_rand_gen;
168 206
169extern rand_gen rndm, rmg_rndm; 207extern rand_gen rndm, rmg_rndm;
170 208
171#endif 209#endif
172 210

Diff Legend

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