x
Yes
No
Do you want to visit DriveHQ English website?
首页
产品服务
价格
免费试用
下载客户端
关于我们
云文件服务
|
云备份服务
|
FTP服务
|
企业邮箱服务
|
网站托管
|
客户端软件
云文件服务
云备份服务
FTP服务
企业级邮箱服务
网站托管
客户端软件
const_mod.hpp - Hosted on DriveHQ Cloud IT Platform
返回上层目录
上传
下载
共享
发布
新建文件夹
新建文件
复制
剪切
删除
粘贴
评论
升级服务
路径: \\game3dprogramming\materials\GameFactory\GameFactoryDemo\references\boost_1_35_0\boost\random\detail\const_mod.hpp
旋转
特效
属性
历史版本
/* 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 41369 2007-11-25 18:07:19Z bemandawes $ * * Revision history * 2001-02-18 moved to individual header files */ #ifndef BOOST_RANDOM_CONST_MOD_HPP #define BOOST_RANDOM_CONST_MOD_HPP #include
#include
#include
#include
#include
namespace boost { namespace random { /* * Some random number generators require modular arithmetic. Put * everything we need here. * IntType must be an integral type. */ namespace detail { template
struct do_add { }; template<> struct do_add
{ template
static IntType add(IntType m, IntType x, IntType c) { if (x < m - c) return x + c; else return x - (m-c); } }; template<> struct do_add
{ template
static IntType add(IntType, IntType, IntType) { // difficult assert(!"const_mod::add with c too large"); return 0; } }; } // namespace detail #if !(defined(__BORLANDC__) && (__BORLANDC__ == 0x560)) template
class const_mod { public: static IntType add(IntType x, IntType c) { if(c == 0) return x; else if(c <= traits::const_max - m) // i.e. m+c < max return add_small(x, c); else return detail::do_add
::add(m, x, c); } static IntType mult(IntType a, IntType x) { 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 { // difficult assert(!"const_mod::mult with a too large"); return 0; } } static IntType mult_add(IntType a, IntType x, IntType c) { if(m <= (traits::const_max-c)/a) // i.e. a*m+c <= max return (a*x+c) % m; else return add(mult(a, x), c); } static IntType invert(IntType x) { return x == 0 ? 0 : invert_euclidian(x); } private: typedef integer_traits
traits; const_mod(); // don't instantiate static IntType add_small(IntType x, IntType c) { x += c; if(x >= m) x -= m; return x; } static IntType mult_small(IntType a, IntType x) { return a*x % m; } static IntType mult_schrage(IntType a, IntType value) { const IntType q = m / a; const IntType r = m % a; assert(r < q); // check that overflow cannot happen value = a*(value%q) - r*(value/q); // An optimizer bug in the SGI MIPSpro 7.3.1.x compiler requires this // convoluted formulation of the loop (Synge Todo) for(;;) { if (value > 0) break; value += m; } return value; } // 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_STATIC_ASSERT(m > 0); #if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3003)) assert(boost::integer_traits
::is_signed); #elif !defined(BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS) BOOST_STATIC_ASSERT(boost::integer_traits
::is_signed); #endif assert(c > 0); IntType l1 = 0; IntType l2 = 1; IntType n = c; IntType p = m; for(;;) { IntType q = p / n; l1 -= q * l2; // this requires a signed IntType! p -= q * n; if(p == 0) return (l2 < 1 ? l2 + m : l2); IntType q2 = n / p; l2 -= q2 * l1; n -= q2 * p; if(n == 0) return (l1 < 1 ? l1 + m : l1); } } }; // The modulus is exactly the word size: rely on machine overflow handling. // Due to a GCC bug, we cannot partially specialize in the presence of // template value parameters. template<> class const_mod
{ typedef unsigned int IntType; public: static IntType add(IntType x, IntType c) { return x+c; } static IntType mult(IntType a, IntType x) { return a*x; } static IntType mult_add(IntType a, IntType x, IntType c) { return a*x+c; } // m is not prime, thus invert is not useful private: // don't instantiate const_mod(); }; template<> class const_mod
{ typedef unsigned long IntType; public: static IntType add(IntType x, IntType c) { return x+c; } static IntType mult(IntType a, IntType x) { return a*x; } static IntType mult_add(IntType a, IntType x, IntType c) { return a*x+c; } // m is not prime, thus invert is not useful private: // don't instantiate const_mod(); }; // the modulus is some power of 2: rely partly on machine overflow handling // we only specialize for rand48 at the moment #ifndef BOOST_NO_INT64_T template<> class const_mod
{ typedef uint64_t IntType; public: static IntType add(IntType x, IntType c) { return c == 0 ? x : mod(x+c); } static IntType mult(IntType a, IntType x) { return mod(a*x); } static IntType mult_add(IntType a, IntType x, IntType c) { return mod(a*x+c); } static IntType mod(IntType x) { return x &= ((uint64_t(1) << 48)-1); } // m is not prime, thus invert is not useful private: // don't instantiate const_mod(); }; #endif /* !BOOST_NO_INT64_T */ #else // // for some reason Borland C++ Builder 6 has problems with // the full specialisations of const_mod, define a generic version // instead, the compiler will optimise away the const-if statements: // template
class const_mod { public: static IntType add(IntType x, IntType c) { if(0 == m) { return x+c; } else { if(c == 0) return x; else if(c <= traits::const_max - m) // i.e. m+c < max return add_small(x, c); else return detail::do_add
::add(m, x, c); } } static IntType mult(IntType a, IntType x) { if(x == 0) { return a*x; } 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 { // difficult assert(!"const_mod::mult with a too large"); return 0; } } } static IntType mult_add(IntType a, IntType x, IntType c) { if(m == 0) { return a*x+c; } else { if(m <= (traits::const_max-c)/a) // i.e. a*m+c <= max return (a*x+c) % m; else return add(mult(a, x), c); } } static IntType invert(IntType x) { return x == 0 ? 0 : invert_euclidian(x); } private: typedef integer_traits
traits; const_mod(); // don't instantiate static IntType add_small(IntType x, IntType c) { x += c; if(x >= m) x -= m; return x; } static IntType mult_small(IntType a, IntType x) { return a*x % m; } static IntType mult_schrage(IntType a, IntType value) { const IntType q = m / a; const IntType r = m % a; assert(r < q); // check that overflow cannot happen value = a*(value%q) - r*(value/q); while(value <= 0) value += m; return value; } // 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_STATIC_ASSERT(m > 0); #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS BOOST_STATIC_ASSERT(boost::integer_traits
::is_signed); #endif assert(c > 0); IntType l1 = 0; IntType l2 = 1; IntType n = c; IntType p = m; for(;;) { IntType q = p / n; l1 -= q * l2; // this requires a signed IntType! p -= q * n; if(p == 0) return (l2 < 1 ? l2 + m : l2); IntType q2 = n / p; l2 -= q2 * l1; n -= q2 * p; if(n == 0) return (l1 < 1 ? l1 + m : l1); } } }; #endif } // namespace random } // namespace boost #endif // BOOST_RANDOM_CONST_MOD_HPP
const_mod.hpp
网页地址
文件地址
上一页 1/6
下一页
下载
( 8 KB )
Comments
Total ratings:
0
Average rating:
无评论
of 10
Would you like to comment?
Join now
, or
Logon
if you are already a member.