Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
1 /* boost random/detail/const_mod.hpp header file
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)
8 * See http://www.boost.org for most recent version including documentation.
10 * $Id: const_mod.hpp,v 1.8 2004/07/27 03:43:32 dgregor Exp $
13 * 2001-02-18 moved to individual header files
16 #ifndef BOOST_RANDOM_CONST_MOD_HPP
17 #define BOOST_RANDOM_CONST_MOD_HPP
20 #include <boost/static_assert.hpp>
21 #include <boost/cstdint.hpp>
22 #include <boost/integer_traits.hpp>
23 #include <boost/detail/workaround.hpp>
29 * Some random number generators require modular arithmetic. Put
30 * everything we need here.
31 * IntType must be an integral type.
36 template<bool is_signed>
43 template<class IntType>
44 static IntType add(IntType m, IntType x, IntType c)
56 template<class IntType>
57 static IntType add(IntType, IntType, IntType)
60 assert(!"const_mod::add with c too large");
66 #if !(defined(__BORLANDC__) && (__BORLANDC__ == 0x560))
68 template<class IntType, IntType m>
72 static IntType add(IntType x, IntType c)
76 else if(c <= traits::const_max - m) // i.e. m+c < max
77 return add_small(x, c);
79 return detail::do_add<traits::is_signed>::add(m, x, c);
82 static IntType mult(IntType a, IntType x)
86 else if(m <= traits::const_max/a) // i.e. a*m <= max
87 return mult_small(a, x);
88 else if(traits::is_signed && (m%a < m/a))
89 return mult_schrage(a, x);
92 assert(!"const_mod::mult with a too large");
97 static IntType mult_add(IntType a, IntType x, IntType c)
99 if(m <= (traits::const_max-c)/a) // i.e. a*m+c <= max
102 return add(mult(a, x), c);
105 static IntType invert(IntType x)
106 { return x == 0 ? 0 : invert_euclidian(x); }
109 typedef integer_traits<IntType> traits;
111 const_mod(); // don't instantiate
113 static IntType add_small(IntType x, IntType c)
121 static IntType mult_small(IntType a, IntType x)
126 static IntType mult_schrage(IntType a, IntType value)
128 const IntType q = m / a;
129 const IntType r = m % a;
131 assert(r < q); // check that overflow cannot happen
133 value = a*(value%q) - r*(value/q);
134 // An optimizer bug in the SGI MIPSpro 7.3.1.x compiler requires this
135 // convoluted formulation of the loop (Synge Todo)
144 // invert c in the finite field (mod m) (m must be prime)
145 static IntType invert_euclidian(IntType c)
147 // we are interested in the gcd factor for c, because this is our inverse
148 BOOST_STATIC_ASSERT(m > 0);
149 #if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3003))
150 assert(boost::integer_traits<IntType>::is_signed);
151 #elif !defined(BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS)
152 BOOST_STATIC_ASSERT(boost::integer_traits<IntType>::is_signed);
161 l1 -= q * l2; // this requires a signed IntType!
164 return (l2 < 1 ? l2 + m : l2);
169 return (l1 < 1 ? l1 + m : l1);
174 // The modulus is exactly the word size: rely on machine overflow handling.
175 // Due to a GCC bug, we cannot partially specialize in the presence of
176 // template value parameters.
178 class const_mod<unsigned int, 0>
180 typedef unsigned int IntType;
182 static IntType add(IntType x, IntType c) { return x+c; }
183 static IntType mult(IntType a, IntType x) { return a*x; }
184 static IntType mult_add(IntType a, IntType x, IntType c) { return a*x+c; }
186 // m is not prime, thus invert is not useful
187 private: // don't instantiate
192 class const_mod<unsigned long, 0>
194 typedef unsigned long IntType;
196 static IntType add(IntType x, IntType c) { return x+c; }
197 static IntType mult(IntType a, IntType x) { return a*x; }
198 static IntType mult_add(IntType a, IntType x, IntType c) { return a*x+c; }
200 // m is not prime, thus invert is not useful
201 private: // don't instantiate
205 // the modulus is some power of 2: rely partly on machine overflow handling
206 // we only specialize for rand48 at the moment
207 #ifndef BOOST_NO_INT64_T
209 class const_mod<uint64_t, uint64_t(1) << 48>
211 typedef uint64_t IntType;
213 static IntType add(IntType x, IntType c) { return c == 0 ? x : mod(x+c); }
214 static IntType mult(IntType a, IntType x) { return mod(a*x); }
215 static IntType mult_add(IntType a, IntType x, IntType c)
216 { return mod(a*x+c); }
217 static IntType mod(IntType x) { return x &= ((uint64_t(1) << 48)-1); }
219 // m is not prime, thus invert is not useful
220 private: // don't instantiate
223 #endif /* !BOOST_NO_INT64_T */
228 // for some reason Borland C++ Builder 6 has problems with
229 // the full specialisations of const_mod, define a generic version
230 // instead, the compiler will optimise away the const-if statements:
233 template<class IntType, IntType m>
237 static IntType add(IntType x, IntType c)
247 else if(c <= traits::const_max - m) // i.e. m+c < max
248 return add_small(x, c);
250 return detail::do_add<traits::is_signed>::add(m, x, c);
254 static IntType mult(IntType a, IntType x)
264 else if(m <= traits::const_max/a) // i.e. a*m <= max
265 return mult_small(a, x);
266 else if(traits::is_signed && (m%a < m/a))
267 return mult_schrage(a, x);
270 assert(!"const_mod::mult with a too large");
276 static IntType mult_add(IntType a, IntType x, IntType c)
284 if(m <= (traits::const_max-c)/a) // i.e. a*m+c <= max
287 return add(mult(a, x), c);
291 static IntType invert(IntType x)
292 { return x == 0 ? 0 : invert_euclidian(x); }
295 typedef integer_traits<IntType> traits;
297 const_mod(); // don't instantiate
299 static IntType add_small(IntType x, IntType c)
307 static IntType mult_small(IntType a, IntType x)
312 static IntType mult_schrage(IntType a, IntType value)
314 const IntType q = m / a;
315 const IntType r = m % a;
317 assert(r < q); // check that overflow cannot happen
319 value = a*(value%q) - r*(value/q);
325 // invert c in the finite field (mod m) (m must be prime)
326 static IntType invert_euclidian(IntType c)
328 // we are interested in the gcd factor for c, because this is our inverse
329 BOOST_STATIC_ASSERT(m > 0);
330 #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
331 BOOST_STATIC_ASSERT(boost::integer_traits<IntType>::is_signed);
340 l1 -= q * l2; // this requires a signed IntType!
343 return (l2 < 1 ? l2 + m : l2);
348 return (l1 < 1 ? l1 + m : l1);
356 } // namespace random
359 #endif // BOOST_RANDOM_CONST_MOD_HPP