/usr/include/boost/random/detail/const_mod.hpp is in libboost1.55-dev 1.55.0+dfsg-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 | /* boost random/detail/const_mod.hpp header file
*
* Copyright Jens Maurer 2000-2001
* Distributed under the Boost Software License, Version 1.0. (See
* accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
*
* See http://www.boost.org for most recent version including documentation.
*
* $Id: const_mod.hpp 71018 2011-04-05 21:27:52Z steven_watanabe $
*
* Revision history
* 2001-02-18 moved to individual header files
*/
#ifndef BOOST_RANDOM_CONST_MOD_HPP
#define BOOST_RANDOM_CONST_MOD_HPP
#include <boost/assert.hpp>
#include <boost/static_assert.hpp>
#include <boost/integer_traits.hpp>
#include <boost/type_traits/make_unsigned.hpp>
#include <boost/random/detail/large_arithmetic.hpp>
#include <boost/random/detail/disable_warnings.hpp>
namespace boost {
namespace random {
template<class IntType, IntType m>
class const_mod
{
public:
static IntType apply(IntType x)
{
if(((unsigned_m() - 1) & unsigned_m()) == 0)
return (unsigned_type(x)) & (unsigned_m() - 1);
else {
IntType supress_warnings = (m == 0);
BOOST_ASSERT(supress_warnings == 0);
return x % (m + supress_warnings);
}
}
static IntType add(IntType x, IntType c)
{
if(((unsigned_m() - 1) & unsigned_m()) == 0)
return (unsigned_type(x) + unsigned_type(c)) & (unsigned_m() - 1);
else if(c == 0)
return x;
else if(x < m - c)
return x + c;
else
return x - (m - c);
}
static IntType mult(IntType a, IntType x)
{
if(((unsigned_m() - 1) & unsigned_m()) == 0)
return unsigned_type(a) * unsigned_type(x) & (unsigned_m() - 1);
else if(a == 0)
return 0;
else if(a == 1)
return x;
else if(m <= traits::const_max/a) // i.e. a*m <= max
return mult_small(a, x);
else if(traits::is_signed && (m%a < m/a))
return mult_schrage(a, x);
else
return mult_general(a, x);
}
static IntType mult_add(IntType a, IntType x, IntType c)
{
if(((unsigned_m() - 1) & unsigned_m()) == 0)
return (unsigned_type(a) * unsigned_type(x) + unsigned_type(c)) & (unsigned_m() - 1);
else if(a == 0)
return c;
else if(m <= (traits::const_max-c)/a) { // i.e. a*m+c <= max
IntType supress_warnings = (m == 0);
BOOST_ASSERT(supress_warnings == 0);
return (a*x+c) % (m + supress_warnings);
} else
return add(mult(a, x), c);
}
static IntType pow(IntType a, boost::uintmax_t exponent)
{
IntType result = 1;
while(exponent != 0) {
if(exponent % 2 == 1) {
result = mult(result, a);
}
a = mult(a, a);
exponent /= 2;
}
return result;
}
static IntType invert(IntType x)
{ return x == 0 ? 0 : (m == 0? invert_euclidian0(x) : invert_euclidian(x)); }
private:
typedef integer_traits<IntType> traits;
typedef typename make_unsigned<IntType>::type unsigned_type;
const_mod(); // don't instantiate
static IntType mult_small(IntType a, IntType x)
{
IntType supress_warnings = (m == 0);
BOOST_ASSERT(supress_warnings == 0);
return a*x % (m + supress_warnings);
}
static IntType mult_schrage(IntType a, IntType value)
{
const IntType q = m / a;
const IntType r = m % a;
BOOST_ASSERT(r < q); // check that overflow cannot happen
return sub(a*(value%q), r*(value/q));
}
static IntType mult_general(IntType a, IntType b)
{
IntType suppress_warnings = (m == 0);
BOOST_ASSERT(suppress_warnings == 0);
IntType modulus = m + suppress_warnings;
BOOST_ASSERT(modulus == m);
if(::boost::uintmax_t(modulus) <=
(::std::numeric_limits< ::boost::uintmax_t>::max)() / modulus)
{
return static_cast<IntType>(boost::uintmax_t(a) * b % modulus);
} else {
return static_cast<IntType>(detail::mulmod(a, b, modulus));
}
}
static IntType sub(IntType a, IntType b)
{
if(a < b)
return m - (b - a);
else
return a - b;
}
static unsigned_type unsigned_m()
{
if(m == 0) {
return unsigned_type((std::numeric_limits<IntType>::max)()) + 1;
} else {
return unsigned_type(m);
}
}
// invert c in the finite field (mod m) (m must be prime)
static IntType invert_euclidian(IntType c)
{
// we are interested in the gcd factor for c, because this is our inverse
BOOST_ASSERT(c > 0);
IntType l1 = 0;
IntType l2 = 1;
IntType n = c;
IntType p = m;
for(;;) {
IntType q = p / n;
l1 += q * l2;
p -= q * n;
if(p == 0)
return l2;
IntType q2 = n / p;
l2 += q2 * l1;
n -= q2 * p;
if(n == 0)
return m - l1;
}
}
// invert c in the finite field (mod m) (c must be relatively prime to m)
static IntType invert_euclidian0(IntType c)
{
// we are interested in the gcd factor for c, because this is our inverse
BOOST_ASSERT(c > 0);
if(c == 1) return 1;
IntType l1 = 0;
IntType l2 = 1;
IntType n = c;
IntType p = m;
IntType max = (std::numeric_limits<IntType>::max)();
IntType q = max / n;
BOOST_ASSERT(max % n != n - 1 && "c must be relatively prime to m.");
l1 += q * l2;
p = max - q * n + 1;
for(;;) {
if(p == 0)
return l2;
IntType q2 = n / p;
l2 += q2 * l1;
n -= q2 * p;
if(n == 0)
return m - l1;
q = p / n;
l1 += q * l2;
p -= q * n;
}
}
};
} // namespace random
} // namespace boost
#include <boost/random/detail/enable_warnings.hpp>
#endif // BOOST_RANDOM_CONST_MOD_HPP
|