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 71018 2011-04-05 21:27:52Z steven_watanabe $
13 * 2001-02-18 moved to individual header files
16 #ifndef BOOST_RANDOM_CONST_MOD_HPP
17 #define BOOST_RANDOM_CONST_MOD_HPP
19 #include <boost/assert.hpp>
20 #include <boost/static_assert.hpp>
21 #include <boost/integer_traits.hpp>
22 #include <boost/type_traits/make_unsigned.hpp>
23 #include <boost/random/detail/large_arithmetic.hpp>
25 #include <boost/random/detail/disable_warnings.hpp>
30 template<class IntType, IntType m>
34 static IntType apply(IntType x)
36 if(((unsigned_m() - 1) & unsigned_m()) == 0)
37 return (unsigned_type(x)) & (unsigned_m() - 1);
39 IntType supress_warnings = (m == 0);
40 BOOST_ASSERT(supress_warnings == 0);
41 return x % (m + supress_warnings);
45 static IntType add(IntType x, IntType c)
47 if(((unsigned_m() - 1) & unsigned_m()) == 0)
48 return (unsigned_type(x) + unsigned_type(c)) & (unsigned_m() - 1);
57 static IntType mult(IntType a, IntType x)
59 if(((unsigned_m() - 1) & unsigned_m()) == 0)
60 return unsigned_type(a) * unsigned_type(x) & (unsigned_m() - 1);
65 else if(m <= traits::const_max/a) // i.e. a*m <= max
66 return mult_small(a, x);
67 else if(traits::is_signed && (m%a < m/a))
68 return mult_schrage(a, x);
70 return mult_general(a, x);
73 static IntType mult_add(IntType a, IntType x, IntType c)
75 if(((unsigned_m() - 1) & unsigned_m()) == 0)
76 return (unsigned_type(a) * unsigned_type(x) + unsigned_type(c)) & (unsigned_m() - 1);
79 else if(m <= (traits::const_max-c)/a) { // i.e. a*m+c <= max
80 IntType supress_warnings = (m == 0);
81 BOOST_ASSERT(supress_warnings == 0);
82 return (a*x+c) % (m + supress_warnings);
84 return add(mult(a, x), c);
87 static IntType pow(IntType a, boost::uintmax_t exponent)
90 while(exponent != 0) {
91 if(exponent % 2 == 1) {
92 result = mult(result, a);
100 static IntType invert(IntType x)
101 { return x == 0 ? 0 : (m == 0? invert_euclidian0(x) : invert_euclidian(x)); }
104 typedef integer_traits<IntType> traits;
105 typedef typename make_unsigned<IntType>::type unsigned_type;
107 const_mod(); // don't instantiate
109 static IntType mult_small(IntType a, IntType x)
111 IntType supress_warnings = (m == 0);
112 BOOST_ASSERT(supress_warnings == 0);
113 return a*x % (m + supress_warnings);
116 static IntType mult_schrage(IntType a, IntType value)
118 const IntType q = m / a;
119 const IntType r = m % a;
121 BOOST_ASSERT(r < q); // check that overflow cannot happen
123 return sub(a*(value%q), r*(value/q));
126 static IntType mult_general(IntType a, IntType b)
128 IntType suppress_warnings = (m == 0);
129 BOOST_ASSERT(suppress_warnings == 0);
130 IntType modulus = m + suppress_warnings;
131 BOOST_ASSERT(modulus == m);
132 if(::boost::uintmax_t(modulus) <=
133 (::std::numeric_limits< ::boost::uintmax_t>::max)() / modulus)
135 return static_cast<IntType>(boost::uintmax_t(a) * b % modulus);
137 return static_cast<IntType>(detail::mulmod(a, b, modulus));
141 static IntType sub(IntType a, IntType b)
149 static unsigned_type unsigned_m()
152 return unsigned_type((std::numeric_limits<IntType>::max)()) + 1;
154 return unsigned_type(m);
158 // invert c in the finite field (mod m) (m must be prime)
159 static IntType invert_euclidian(IntType c)
161 // we are interested in the gcd factor for c, because this is our inverse
181 // invert c in the finite field (mod m) (c must be relatively prime to m)
182 static IntType invert_euclidian0(IntType c)
184 // we are interested in the gcd factor for c, because this is our inverse
191 IntType max = (std::numeric_limits<IntType>::max)();
193 BOOST_ASSERT(max % n != n - 1 && "c must be relatively prime to m.");
211 } // namespace random
214 #include <boost/random/detail/enable_warnings.hpp>
216 #endif // BOOST_RANDOM_CONST_MOD_HPP