1 | /* boost random/linear_congruential.hpp header file |
---|
2 | * |
---|
3 | * Copyright Jens Maurer 2000-2001 |
---|
4 | * Distributed under the Boost Software License, Version 1.0. (See |
---|
5 | * accompanying file LICENSE_1_0.txt or copy at |
---|
6 | * http://www.boost.org/LICENSE_1_0.txt) |
---|
7 | * |
---|
8 | * See http://www.boost.org for most recent version including documentation. |
---|
9 | * |
---|
10 | * $Id: linear_congruential.hpp,v 1.22 2005/05/21 15:57:00 dgregor Exp $ |
---|
11 | * |
---|
12 | * Revision history |
---|
13 | * 2001-02-18 moved to individual header files |
---|
14 | */ |
---|
15 | |
---|
16 | #ifndef BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP |
---|
17 | #define BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP |
---|
18 | |
---|
19 | #include <iostream> |
---|
20 | #include <cassert> |
---|
21 | #include <stdexcept> |
---|
22 | #include <boost/config.hpp> |
---|
23 | #include <boost/limits.hpp> |
---|
24 | #include <boost/static_assert.hpp> |
---|
25 | #include <boost/random/detail/const_mod.hpp> |
---|
26 | #include <boost/detail/workaround.hpp> |
---|
27 | |
---|
28 | namespace boost { |
---|
29 | namespace random { |
---|
30 | |
---|
31 | // compile-time configurable linear congruential generator |
---|
32 | template<class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
33 | class linear_congruential |
---|
34 | { |
---|
35 | public: |
---|
36 | typedef IntType result_type; |
---|
37 | #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION |
---|
38 | static const bool has_fixed_range = true; |
---|
39 | static const result_type min_value = ( c == 0 ? 1 : 0 ); |
---|
40 | static const result_type max_value = m-1; |
---|
41 | #else |
---|
42 | BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); |
---|
43 | #endif |
---|
44 | BOOST_STATIC_CONSTANT(IntType, multiplier = a); |
---|
45 | BOOST_STATIC_CONSTANT(IntType, increment = c); |
---|
46 | BOOST_STATIC_CONSTANT(IntType, modulus = m); |
---|
47 | |
---|
48 | // MSVC 6 and possibly others crash when encountering complicated integral |
---|
49 | // constant expressions. Avoid the check for now. |
---|
50 | // BOOST_STATIC_ASSERT(m == 0 || a < m); |
---|
51 | // BOOST_STATIC_ASSERT(m == 0 || c < m); |
---|
52 | |
---|
53 | explicit linear_congruential(IntType x0 = 1) |
---|
54 | : _modulus(modulus), _x(_modulus ? (x0 % _modulus) : x0) |
---|
55 | { |
---|
56 | assert(c || x0); /* if c == 0 and x(0) == 0 then x(n) = 0 for all n */ |
---|
57 | // overflow check |
---|
58 | // disabled because it gives spurious "divide by zero" gcc warnings |
---|
59 | // assert(m == 0 || (a*(m-1)+c) % m == (c < a ? c-a+m : c-a)); |
---|
60 | |
---|
61 | // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope |
---|
62 | #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS |
---|
63 | BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer); |
---|
64 | #endif |
---|
65 | } |
---|
66 | |
---|
67 | template<class It> |
---|
68 | linear_congruential(It& first, It last) { seed(first, last); } |
---|
69 | |
---|
70 | // compiler-generated copy constructor and assignment operator are fine |
---|
71 | void seed(IntType x0 = 1) |
---|
72 | { |
---|
73 | assert(c || x0); |
---|
74 | _x = (_modulus ? (x0 % _modulus) : x0); |
---|
75 | } |
---|
76 | |
---|
77 | template<class It> |
---|
78 | void seed(It& first, It last) |
---|
79 | { |
---|
80 | if(first == last) |
---|
81 | throw std::invalid_argument("linear_congruential::seed"); |
---|
82 | IntType value = *first++; |
---|
83 | _x = (_modulus ? (value % _modulus) : value); |
---|
84 | } |
---|
85 | |
---|
86 | result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return c == 0 ? 1 : 0; } |
---|
87 | result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return modulus-1; } |
---|
88 | |
---|
89 | IntType operator()() |
---|
90 | { |
---|
91 | _x = const_mod<IntType, m>::mult_add(a, _x, c); |
---|
92 | return _x; |
---|
93 | } |
---|
94 | |
---|
95 | static bool validation(IntType x) { return val == x; } |
---|
96 | |
---|
97 | #ifdef BOOST_NO_OPERATORS_IN_NAMESPACE |
---|
98 | |
---|
99 | // Use a member function; Streamable concept not supported. |
---|
100 | bool operator==(const linear_congruential& rhs) const |
---|
101 | { return _x == rhs._x; } |
---|
102 | bool operator!=(const linear_congruential& rhs) const |
---|
103 | { return !(*this == rhs); } |
---|
104 | |
---|
105 | #else |
---|
106 | friend bool operator==(const linear_congruential& x, |
---|
107 | const linear_congruential& y) |
---|
108 | { return x._x == y._x; } |
---|
109 | friend bool operator!=(const linear_congruential& x, |
---|
110 | const linear_congruential& y) |
---|
111 | { return !(x == y); } |
---|
112 | |
---|
113 | #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) |
---|
114 | template<class CharT, class Traits> |
---|
115 | friend std::basic_ostream<CharT,Traits>& |
---|
116 | operator<<(std::basic_ostream<CharT,Traits>& os, |
---|
117 | const linear_congruential& lcg) |
---|
118 | { |
---|
119 | return os << lcg._x; |
---|
120 | } |
---|
121 | |
---|
122 | template<class CharT, class Traits> |
---|
123 | friend std::basic_istream<CharT,Traits>& |
---|
124 | operator>>(std::basic_istream<CharT,Traits>& is, |
---|
125 | linear_congruential& lcg) |
---|
126 | { |
---|
127 | return is >> lcg._x; |
---|
128 | } |
---|
129 | |
---|
130 | private: |
---|
131 | #endif |
---|
132 | #endif |
---|
133 | |
---|
134 | IntType _modulus; // work-around for gcc "divide by zero" warning in ctor |
---|
135 | IntType _x; |
---|
136 | }; |
---|
137 | |
---|
138 | // probably needs the "no native streams" caveat for STLPort |
---|
139 | #if !defined(__SGI_STL_PORT) && BOOST_WORKAROUND(__GNUC__, == 2) |
---|
140 | template<class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
141 | std::ostream& |
---|
142 | operator<<(std::ostream& os, |
---|
143 | const linear_congruential<IntType,a,c,m,val>& lcg) |
---|
144 | { |
---|
145 | return os << lcg._x; |
---|
146 | } |
---|
147 | |
---|
148 | template<class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
149 | std::istream& |
---|
150 | operator>>(std::istream& is, |
---|
151 | linear_congruential<IntType,a,c,m,val>& lcg) |
---|
152 | { |
---|
153 | return is >> lcg._x; |
---|
154 | } |
---|
155 | #elif defined(BOOST_NO_OPERATORS_IN_NAMESPACE) || defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) || BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) |
---|
156 | template<class CharT, class Traits, class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
157 | std::basic_ostream<CharT,Traits>& |
---|
158 | operator<<(std::basic_ostream<CharT,Traits>& os, |
---|
159 | const linear_congruential<IntType,a,c,m,val>& lcg) |
---|
160 | { |
---|
161 | return os << lcg._x; |
---|
162 | } |
---|
163 | |
---|
164 | template<class CharT, class Traits, class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
165 | std::basic_istream<CharT,Traits>& |
---|
166 | operator>>(std::basic_istream<CharT,Traits>& is, |
---|
167 | linear_congruential<IntType,a,c,m,val>& lcg) |
---|
168 | { |
---|
169 | return is >> lcg._x; |
---|
170 | } |
---|
171 | #endif |
---|
172 | |
---|
173 | #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION |
---|
174 | // A definition is required even for integral static constants |
---|
175 | template<class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
176 | const bool linear_congruential<IntType, a, c, m, val>::has_fixed_range; |
---|
177 | template<class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
178 | const typename linear_congruential<IntType, a, c, m, val>::result_type linear_congruential<IntType, a, c, m, val>::min_value; |
---|
179 | template<class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
180 | const typename linear_congruential<IntType, a, c, m, val>::result_type linear_congruential<IntType, a, c, m, val>::max_value; |
---|
181 | template<class IntType, IntType a, IntType c, IntType m, IntType val> |
---|
182 | const IntType linear_congruential<IntType,a,c,m,val>::modulus; |
---|
183 | #endif |
---|
184 | |
---|
185 | } // namespace random |
---|
186 | |
---|
187 | // validation values from the publications |
---|
188 | typedef random::linear_congruential<int32_t, 16807, 0, 2147483647, |
---|
189 | 1043618065> minstd_rand0; |
---|
190 | typedef random::linear_congruential<int32_t, 48271, 0, 2147483647, |
---|
191 | 399268537> minstd_rand; |
---|
192 | |
---|
193 | |
---|
194 | #if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T) |
---|
195 | // emulate the lrand48() C library function; requires support for uint64_t |
---|
196 | class rand48 |
---|
197 | { |
---|
198 | public: |
---|
199 | typedef int32_t result_type; |
---|
200 | #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION |
---|
201 | static const bool has_fixed_range = true; |
---|
202 | static const int32_t min_value = 0; |
---|
203 | static const int32_t max_value = integer_traits<int32_t>::const_max; |
---|
204 | #else |
---|
205 | enum { has_fixed_range = false }; |
---|
206 | #endif |
---|
207 | int32_t min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; } |
---|
208 | int32_t max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return std::numeric_limits<int32_t>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); } |
---|
209 | |
---|
210 | explicit rand48(int32_t x0 = 1) : lcf(cnv(x0)) { } |
---|
211 | explicit rand48(uint64_t x0) : lcf(x0) { } |
---|
212 | template<class It> rand48(It& first, It last) : lcf(first, last) { } |
---|
213 | // compiler-generated copy ctor and assignment operator are fine |
---|
214 | void seed(int32_t x0 = 1) { lcf.seed(cnv(x0)); } |
---|
215 | void seed(uint64_t x0) { lcf.seed(x0); } |
---|
216 | template<class It> void seed(It& first, It last) { lcf.seed(first,last); } |
---|
217 | |
---|
218 | int32_t operator()() { return static_cast<int32_t>(lcf() >> 17); } |
---|
219 | // by experiment from lrand48() |
---|
220 | static bool validation(int32_t x) { return x == 1993516219; } |
---|
221 | |
---|
222 | #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE |
---|
223 | |
---|
224 | #ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS |
---|
225 | template<class CharT,class Traits> |
---|
226 | friend std::basic_ostream<CharT,Traits>& |
---|
227 | operator<<(std::basic_ostream<CharT,Traits>& os, const rand48& r) |
---|
228 | { os << r.lcf; return os; } |
---|
229 | |
---|
230 | template<class CharT,class Traits> |
---|
231 | friend std::basic_istream<CharT,Traits>& |
---|
232 | operator>>(std::basic_istream<CharT,Traits>& is, rand48& r) |
---|
233 | { is >> r.lcf; return is; } |
---|
234 | #endif |
---|
235 | |
---|
236 | friend bool operator==(const rand48& x, const rand48& y) |
---|
237 | { return x.lcf == y.lcf; } |
---|
238 | friend bool operator!=(const rand48& x, const rand48& y) |
---|
239 | { return !(x == y); } |
---|
240 | #else |
---|
241 | // Use a member function; Streamable concept not supported. |
---|
242 | bool operator==(const rand48& rhs) const |
---|
243 | { return lcf == rhs.lcf; } |
---|
244 | bool operator!=(const rand48& rhs) const |
---|
245 | { return !(*this == rhs); } |
---|
246 | #endif |
---|
247 | private: |
---|
248 | random::linear_congruential<uint64_t, |
---|
249 | uint64_t(0xDEECE66DUL) | (uint64_t(0x5) << 32), // xxxxULL is not portable |
---|
250 | 0xB, uint64_t(1)<<48, /* unknown */ 0> lcf; |
---|
251 | static uint64_t cnv(int32_t x) |
---|
252 | { return (static_cast<uint64_t>(x) << 16) | 0x330e; } |
---|
253 | }; |
---|
254 | #endif /* !BOOST_NO_INT64_T && !BOOST_NO_INTEGRAL_INT64_T */ |
---|
255 | |
---|
256 | } // namespace boost |
---|
257 | |
---|
258 | #endif // BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP |
---|