ceph/src/boost/libs/integer/test/common_factor_test.cpp

   1 //  Boost GCD & LCM common_factor.hpp test program  --------------------------//
   2
   3 //  (C) Copyright Daryle Walker 2001, 2006.
   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 //  Revision History
  11 //  01 Dec 2006  Various fixes for old compilers (Joaquin M Lopez Munoz)
  12 //  10 Nov 2006  Make long long and __int64 mutually exclusive (Daryle Walker)
  13 //  04 Nov 2006  Use more built-in numeric types, binary-GCD (Daryle Walker)
  14 //  03 Nov 2006  Use custom numeric types (Daryle Walker)
  15 //  02 Nov 2006  Change to Boost.Test's unit test system (Daryle Walker)
  16 //  07 Nov 2001  Initial version (Daryle Walker)
  17
  18 #define BOOST_TEST_MAIN  "Boost.integer GCD & LCM unit tests"
  19
  20 #include <boost/config.hpp>              // for BOOST_MSVC, etc.
  21 #include <boost/detail/workaround.hpp>
  22 #include <boost/integer/common_factor.hpp>  // for boost::integer::gcd, etc.
  23 #include <boost/mpl/list.hpp>            // for boost::mpl::list
  24 #include <boost/operators.hpp>
  25 #include <boost/core/lightweight_test.hpp>
  26 #include <boost/random.hpp>
  27 #include <boost/rational.hpp>
  28
  29 #include <istream>  // for std::basic_istream
  30 #include <limits>   // for std::numeric_limits
  31 #include <ostream>  // for std::basic_ostream
  32
  33 #ifdef BOOST_INTEGER_HAS_GMPXX_H
  34 #include <gmpxx.h>
  35 #endif
  36
  37 #if (defined(BOOST_MSVC) && (BOOST_MSVC < 1500)) || (defined(__clang_major__) && (__clang_major__ == 3) && (__clang_minor__ < 2))
  38 #define DISABLE_MP_TESTS
  39 #endif
  40
  41 #ifndef DISABLE_MP_TESTS
  42 #include <boost/multiprecision/cpp_int.hpp>
  43 #endif
  44
  45 namespace {
  46
  47 // TODO: add polynominal/non-real type; especially after any switch to the
  48 // binary-GCD algorithm for built-in types
  49
  50 // Custom integer class (template)
  51 template < typename IntType, int ID = 0 >
  52 class my_wrapped_integer
  53     : private ::boost::shiftable1<my_wrapped_integer<IntType, ID>,
  54         ::boost::operators<my_wrapped_integer<IntType, ID> > >
  55 {
  56     // Helper type-aliases
  57     typedef my_wrapped_integer    self_type;
  58     typedef IntType self_type::*  bool_type;
  59
  60     // Member data
  61     IntType  v_;
  62
  63 public:
  64     // Template parameters
  65     typedef IntType  int_type;
  66
  67     BOOST_STATIC_CONSTANT(int,id = ID);
  68
  69     // Lifetime management (use automatic destructor and copy constructor)
  70     my_wrapped_integer( int_type const &v = int_type() )  : v_( v )  {}
  71
  72     // Accessors
  73     int_type  value() const  { return this->v_; }
  74
  75     // Operators (use automatic copy assignment)
  76     operator bool_type() const  { return this->v_ ? &self_type::v_ : 0; }
  77
  78     self_type &  operator ++()  { ++this->v_; return *this; }
  79     self_type &  operator --()  { --this->v_; return *this; }
  80
  81     self_type  operator ~() const  { return self_type( ~this->v_ ); }
  82     self_type  operator !() const  { return self_type( !this->v_ ); }
  83     self_type  operator +() const  { return self_type( +this->v_ ); }
  84     self_type  operator -() const  { return self_type( -this->v_ ); }
  85
  86     bool  operator  <( self_type const &r ) const  { return this->v_ < r.v_; }
  87     bool  operator ==( self_type const &r ) const  { return this->v_ == r.v_; }
  88
  89     self_type &operator *=(self_type const &r) {this->v_ *= r.v_; return *this;}
  90     self_type &operator /=(self_type const &r) {this->v_ /= r.v_; return *this;}
  91     self_type &operator %=(self_type const &r) {this->v_ %= r.v_; return *this;}
  92     self_type &operator +=(self_type const &r) {this->v_ += r.v_; return *this;}
  93     self_type &operator -=(self_type const &r) {this->v_ -= r.v_; return *this;}
  94     self_type &operator<<=(self_type const &r){this->v_ <<= r.v_; return *this;}
  95     self_type &operator>>=(self_type const &r){this->v_ >>= r.v_; return *this;}
  96     self_type &operator &=(self_type const &r) {this->v_ &= r.v_; return *this;}
  97     self_type &operator |=(self_type const &r) {this->v_ |= r.v_; return *this;}
  98     self_type &operator ^=(self_type const &r) {this->v_ ^= r.v_; return *this;}
  99
 100     // Input & output
 101     friend std::istream & operator >>( std::istream &i, self_type &x )
 102     { return i >> x.v_; }
 103
 104     friend std::ostream & operator <<( std::ostream &o, self_type const &x )
 105     { return o << x.v_; }
 106
 107 };  // my_wrapped_integer
 108
 109 template < typename IntType, int ID >
 110 my_wrapped_integer<IntType, ID>  abs( my_wrapped_integer<IntType, ID> const &x )
 111 { return ( x < my_wrapped_integer<IntType, ID>(0) ) ? -x : +x; }
 112
 113 typedef my_wrapped_integer<int>          MyInt1;
 114 typedef my_wrapped_integer<unsigned>     MyUnsigned1;
 115 typedef my_wrapped_integer<int, 1>       MyInt2;
 116 typedef my_wrapped_integer<unsigned, 1>  MyUnsigned2;
 117
 118 // Without these explicit instantiations, MSVC++ 6.5/7.0 does not find
 119 // some friend operators in certain contexts.
 120 MyInt1       dummy1;
 121 MyUnsigned1  dummy2;
 122 MyInt2       dummy3;
 123 MyUnsigned2  dummy4;
 124
 125 // Various types to test with each GCD/LCM
 126 typedef ::boost::mpl::list<signed char, short, int, long,
 127 #if BOOST_WORKAROUND(BOOST_MSVC, <= 1500)
 128 #elif defined(BOOST_HAS_LONG_LONG)
 129  boost::long_long_type,
 130 #elif defined(BOOST_HAS_MS_INT64)
 131  __int64,
 132 #endif
 133  MyInt1
 134 #ifndef DISABLE_MP_TESTS
 135    , boost::multiprecision::cpp_int
 136 #endif
 137 >  signed_test_types;
 138 typedef ::boost::mpl::list<unsigned char, unsigned short, unsigned,
 139  unsigned long,
 140 #if BOOST_WORKAROUND(BOOST_MSVC, <= 1500)
 141 #elif defined(BOOST_HAS_LONG_LONG)
 142  boost::ulong_long_type,
 143 #elif defined(BOOST_HAS_MS_INT64)
 144  unsigned __int64,
 145 #endif
 146  MyUnsigned1, MyUnsigned2 /*, boost::multiprecision::uint256_t*/>  unsigned_test_types;
 147
 148 }  // namespace
 149
 150 #define BOOST_NO_MACRO_EXPAND /**/
 151
 152 // Specialize numeric_limits for _some_ of our types
 153 namespace std
 154 {
 155
 156 template < >
 157 class numeric_limits< MyInt1 >
 158 {
 159     typedef MyInt1::int_type             int_type;
 160     typedef numeric_limits<int_type>  limits_type;
 161
 162 public:
 163     BOOST_STATIC_CONSTANT(bool, is_specialized = limits_type::is_specialized);
 164
 165     static MyInt1 min BOOST_NO_MACRO_EXPAND() throw()  { return (limits_type::min)(); }
 166     static MyInt1 max BOOST_NO_MACRO_EXPAND() throw()  { return (limits_type::max)(); }
 167
 168     BOOST_STATIC_CONSTANT(int, digits      = limits_type::digits);
 169     BOOST_STATIC_CONSTANT(int, digits10    = limits_type::digits10);
 170 #ifndef BOOST_NO_CXX11_NUMERIC_LIMITS
 171     BOOST_STATIC_CONSTANT(int, max_digits10    = limits_type::max_digits10);
 172 #endif
 173     BOOST_STATIC_CONSTANT(bool, is_signed  = limits_type::is_signed);
 174     BOOST_STATIC_CONSTANT(bool, is_integer = limits_type::is_integer);
 175     BOOST_STATIC_CONSTANT(bool, is_exact   = limits_type::is_exact);
 176     BOOST_STATIC_CONSTANT(int, radix       = limits_type::radix);
 177     static MyInt1 epsilon() throw()      { return limits_type::epsilon(); }
 178     static MyInt1 round_error() throw()  { return limits_type::round_error(); }
 179
 180     BOOST_STATIC_CONSTANT(int, min_exponent   = limits_type::min_exponent);
 181     BOOST_STATIC_CONSTANT(int, min_exponent10 = limits_type::min_exponent10);
 182     BOOST_STATIC_CONSTANT(int, max_exponent   = limits_type::max_exponent);
 183     BOOST_STATIC_CONSTANT(int, max_exponent10 = limits_type::max_exponent10);
 184
 185     BOOST_STATIC_CONSTANT(bool, has_infinity             = limits_type::has_infinity);
 186     BOOST_STATIC_CONSTANT(bool, has_quiet_NaN            = limits_type::has_quiet_NaN);
 187     BOOST_STATIC_CONSTANT(bool, has_signaling_NaN        = limits_type::has_signaling_NaN);
 188     BOOST_STATIC_CONSTANT(float_denorm_style, has_denorm = limits_type::has_denorm);
 189     BOOST_STATIC_CONSTANT(bool, has_denorm_loss          = limits_type::has_denorm_loss);
 190
 191     static MyInt1 infinity() throw()      { return limits_type::infinity(); }
 192     static MyInt1 quiet_NaN() throw()     { return limits_type::quiet_NaN(); }
 193     static MyInt1 signaling_NaN() throw() {return limits_type::signaling_NaN();}
 194     static MyInt1 denorm_min() throw()    { return limits_type::denorm_min(); }
 195
 196     BOOST_STATIC_CONSTANT(bool, is_iec559  = limits_type::is_iec559);
 197     BOOST_STATIC_CONSTANT(bool, is_bounded = limits_type::is_bounded);
 198     BOOST_STATIC_CONSTANT(bool, is_modulo  = limits_type::is_modulo);
 199
 200     BOOST_STATIC_CONSTANT(bool, traps                    = limits_type::traps);
 201     BOOST_STATIC_CONSTANT(bool, tinyness_before          = limits_type::tinyness_before);
 202     BOOST_STATIC_CONSTANT(float_round_style, round_style = limits_type::round_style);
 203
 204 };  // std::numeric_limits<MyInt1>
 205
 206 template < >
 207 class numeric_limits< MyUnsigned1 >
 208 {
 209     typedef MyUnsigned1::int_type        int_type;
 210     typedef numeric_limits<int_type>  limits_type;
 211
 212 public:
 213     BOOST_STATIC_CONSTANT(bool, is_specialized = limits_type::is_specialized);
 214
 215     static MyUnsigned1 min BOOST_NO_MACRO_EXPAND() throw()  { return (limits_type::min)(); }
 216     static MyUnsigned1 max BOOST_NO_MACRO_EXPAND() throw()  { return (limits_type::max)(); }
 217
 218     BOOST_STATIC_CONSTANT(int, digits      = limits_type::digits);
 219     BOOST_STATIC_CONSTANT(int, digits10    = limits_type::digits10);
 220 #ifndef BOOST_NO_CXX11_NUMERIC_LIMITS
 221     BOOST_STATIC_CONSTANT(int, max_digits10    = limits_type::max_digits10);
 222 #endif
 223     BOOST_STATIC_CONSTANT(bool, is_signed  = limits_type::is_signed);
 224     BOOST_STATIC_CONSTANT(bool, is_integer = limits_type::is_integer);
 225     BOOST_STATIC_CONSTANT(bool, is_exact   = limits_type::is_exact);
 226     BOOST_STATIC_CONSTANT(int, radix       = limits_type::radix);
 227     static MyUnsigned1 epsilon() throw()      { return limits_type::epsilon(); }
 228     static MyUnsigned1 round_error() throw(){return limits_type::round_error();}
 229
 230     BOOST_STATIC_CONSTANT(int, min_exponent   = limits_type::min_exponent);
 231     BOOST_STATIC_CONSTANT(int, min_exponent10 = limits_type::min_exponent10);
 232     BOOST_STATIC_CONSTANT(int, max_exponent   = limits_type::max_exponent);
 233     BOOST_STATIC_CONSTANT(int, max_exponent10 = limits_type::max_exponent10);
 234
 235     BOOST_STATIC_CONSTANT(bool, has_infinity             = limits_type::has_infinity);
 236     BOOST_STATIC_CONSTANT(bool, has_quiet_NaN            = limits_type::has_quiet_NaN);
 237     BOOST_STATIC_CONSTANT(bool, has_signaling_NaN        = limits_type::has_signaling_NaN);
 238     BOOST_STATIC_CONSTANT(float_denorm_style, has_denorm = limits_type::has_denorm);
 239     BOOST_STATIC_CONSTANT(bool, has_denorm_loss          = limits_type::has_denorm_loss);
 240
 241     static MyUnsigned1 infinity() throw()    { return limits_type::infinity(); }
 242     static MyUnsigned1 quiet_NaN() throw()  { return limits_type::quiet_NaN(); }
 243     static MyUnsigned1 signaling_NaN() throw()
 244         { return limits_type::signaling_NaN(); }
 245     static MyUnsigned1 denorm_min() throw(){ return limits_type::denorm_min(); }
 246
 247     BOOST_STATIC_CONSTANT(bool, is_iec559  = limits_type::is_iec559);
 248     BOOST_STATIC_CONSTANT(bool, is_bounded = limits_type::is_bounded);
 249     BOOST_STATIC_CONSTANT(bool, is_modulo  = limits_type::is_modulo);
 250
 251     BOOST_STATIC_CONSTANT(bool, traps                    = limits_type::traps);
 252     BOOST_STATIC_CONSTANT(bool, tinyness_before          = limits_type::tinyness_before);
 253     BOOST_STATIC_CONSTANT(float_round_style, round_style = limits_type::round_style);
 254
 255 };  // std::numeric_limits<MyUnsigned1>
 256
 257 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
 258 // MSVC 6.0 lacks operator<< for __int64, see
 259 // http://support.microsoft.com/default.aspx?scid=kb;en-us;168440
 260
 261 inline ostream& operator<<(ostream& os, __int64 i)
 262 {
 263     char buf[20];
 264     sprintf(buf,"%I64d", i);
 265     os << buf;
 266     return os;
 267 }
 268
 269 inline ostream& operator<<(ostream& os, unsigned __int64 i)
 270 {
 271     char buf[20];
 272     sprintf(buf,"%I64u", i);
 273     os << buf;
 274     return os;
 275 }
 276 #endif
 277
 278 }  // namespace std
 279
 280 // GCD tests
 281
 282 // GCD on signed integer types
 283 template< class T > void gcd_int_test() // signed_test_types
 284 {
 285 #ifndef BOOST_MSVC
 286     using boost::integer::gcd;
 287     using boost::integer::gcd_evaluator;
 288 #else
 289     using namespace boost::integer;
 290 #endif
 291
 292     // Originally from Boost.Rational tests
 293     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(1), static_cast<T>(-1)), static_cast<T>( 1) );
 294     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-1), static_cast<T>(1)), static_cast<T>( 1) );
 295     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(1), static_cast<T>(1)), static_cast<T>( 1) );
 296     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-1), static_cast<T>(-1)), static_cast<T>( 1) );
 297     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0), static_cast<T>(0)), static_cast<T>( 0) );
 298     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(7), static_cast<T>(0)), static_cast<T>( 7) );
 299     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0), static_cast<T>(9)), static_cast<T>( 9) );
 300     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-7), static_cast<T>(0)), static_cast<T>( 7) );
 301     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0), static_cast<T>(-9)), static_cast<T>( 9) );
 302     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(42), static_cast<T>(30)), static_cast<T>( 6) );
 303     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(6), static_cast<T>(-9)), static_cast<T>( 3) );
 304     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-10), static_cast<T>(-10)), static_cast<T>(10) );
 305     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-25), static_cast<T>(-10)), static_cast<T>( 5) );
 306     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(3), static_cast<T>(7)), static_cast<T>( 1) );
 307     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(8), static_cast<T>(9)), static_cast<T>( 1) );
 308     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(7), static_cast<T>(49)), static_cast<T>( 7) );
 309     // Again with function object:
 310     BOOST_TEST_EQ(gcd_evaluator<T>()(1, -1), static_cast<T>(1));
 311     BOOST_TEST_EQ(gcd_evaluator<T>()(-1, 1), static_cast<T>(1));
 312     BOOST_TEST_EQ(gcd_evaluator<T>()(1, 1), static_cast<T>(1));
 313     BOOST_TEST_EQ(gcd_evaluator<T>()(-1, -1), static_cast<T>(1));
 314     BOOST_TEST_EQ(gcd_evaluator<T>()(0, 0), static_cast<T>(0));
 315     BOOST_TEST_EQ(gcd_evaluator<T>()(7, 0), static_cast<T>(7));
 316     BOOST_TEST_EQ(gcd_evaluator<T>()(0, 9), static_cast<T>(9));
 317     BOOST_TEST_EQ(gcd_evaluator<T>()(-7, 0), static_cast<T>(7));
 318     BOOST_TEST_EQ(gcd_evaluator<T>()(0, -9), static_cast<T>(9));
 319     BOOST_TEST_EQ(gcd_evaluator<T>()(42, 30), static_cast<T>(6));
 320     BOOST_TEST_EQ(gcd_evaluator<T>()(6, -9), static_cast<T>(3));
 321     BOOST_TEST_EQ(gcd_evaluator<T>()(-10, -10), static_cast<T>(10));
 322     BOOST_TEST_EQ(gcd_evaluator<T>()(-25, -10), static_cast<T>(5));
 323     BOOST_TEST_EQ(gcd_evaluator<T>()(3, 7), static_cast<T>(1));
 324     BOOST_TEST_EQ(gcd_evaluator<T>()(8, 9), static_cast<T>(1));
 325     BOOST_TEST_EQ(gcd_evaluator<T>()(7, 49), static_cast<T>(7));
 326 }
 327
 328 // GCD on unmarked signed integer type
 329 void gcd_unmarked_int_test()
 330 {
 331 #ifndef BOOST_MSVC
 332     using boost::integer::gcd;
 333 #else
 334     using namespace boost::integer;
 335 #endif
 336
 337     // The regular signed-integer GCD function performs the unsigned version,
 338     // then does an absolute-value on the result.  Signed types that are not
 339     // marked as such (due to no std::numeric_limits specialization) may be off
 340     // by a sign.
 341     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(1), static_cast<MyInt2>(-1) )), MyInt2( 1) );
 342     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-1), static_cast<MyInt2>(1) )), MyInt2( 1) );
 343     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(1), static_cast<MyInt2>(1) )), MyInt2( 1) );
 344     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-1), static_cast<MyInt2>(-1) )), MyInt2( 1) );
 345     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(0), static_cast<MyInt2>(0) )), MyInt2( 0) );
 346     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(7), static_cast<MyInt2>(0) )), MyInt2( 7) );
 347     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(0), static_cast<MyInt2>(9) )), MyInt2( 9) );
 348     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-7), static_cast<MyInt2>(0) )), MyInt2( 7) );
 349     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(0), static_cast<MyInt2>(-9) )), MyInt2( 9) );
 350     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(42), static_cast<MyInt2>(30))), MyInt2( 6) );
 351     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(6), static_cast<MyInt2>(-9) )), MyInt2( 3) );
 352     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-10), static_cast<MyInt2>(-10) )), MyInt2(10) );
 353     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-25), static_cast<MyInt2>(-10) )), MyInt2( 5) );
 354     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(3), static_cast<MyInt2>(7) )), MyInt2( 1) );
 355     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(8), static_cast<MyInt2>(9) )), MyInt2( 1) );
 356     BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(7), static_cast<MyInt2>(49) )), MyInt2( 7) );
 357 }
 358
 359 // GCD on unsigned integer types
 360 template< class T > void gcd_unsigned_test() // unsigned_test_types
 361 {
 362 #ifndef BOOST_MSVC
 363     using boost::integer::gcd;
 364 #else
 365     using namespace boost::integer;
 366 #endif
 367
 368     // Note that unmarked types (i.e. have no std::numeric_limits
 369     // specialization) are treated like non/unsigned types
 370     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(1u), static_cast<T>(1u)), static_cast<T>( 1u) );
 371     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0u), static_cast<T>(0u)), static_cast<T>( 0u) );
 372     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(7u), static_cast<T>(0u)), static_cast<T>( 7u) );
 373     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0u), static_cast<T>(9u)), static_cast<T>( 9u) );
 374     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(42u), static_cast<T>(30u)), static_cast<T>( 6u) );
 375     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(3u), static_cast<T>(7u)), static_cast<T>( 1u) );
 376     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(8u), static_cast<T>(9u)), static_cast<T>( 1u) );
 377     BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(7u), static_cast<T>(49u)), static_cast<T>( 7u) );
 378 }
 379
 380 // GCD at compile-time
 381 void gcd_static_test()
 382 {
 383 #ifndef BOOST_MSVC
 384     using boost::integer::static_gcd;
 385 #else
 386     using namespace boost::integer;
 387 #endif
 388
 389     // Can't use "BOOST_TEST_EQ", otherwise the "value" member will be
 390     // disqualified as compile-time-only constant, needing explicit definition
 391     BOOST_TEST( (static_gcd< 1,  1>::value) == 1 );
 392     BOOST_TEST( (static_gcd< 0,  0>::value) == 0 );
 393     BOOST_TEST( (static_gcd< 7,  0>::value) == 7 );
 394     BOOST_TEST( (static_gcd< 0,  9>::value) == 9 );
 395     BOOST_TEST( (static_gcd<42, 30>::value) == 6 );
 396     BOOST_TEST( (static_gcd< 3,  7>::value) == 1 );
 397     BOOST_TEST( (static_gcd< 8,  9>::value) == 1 );
 398     BOOST_TEST( (static_gcd< 7, 49>::value) == 7 );
 399 }
 400
 401 void gcd_method_test()
 402 {
 403    // Verify that the 3 different methods all yield the same result:
 404    boost::random::mt19937 gen;
 405    boost::random::uniform_int_distribution<int> d(0, ((std::numeric_limits<int>::max)() / 2));
 406
 407    for (unsigned int i = 0; i < 10000; ++i)
 408    {
 409       int v1 = d(gen);
 410       int v2 = d(gen);
 411       int g = boost::integer::gcd_detail::Euclid_gcd(v1, v2);
 412       BOOST_TEST(v1 % g == 0);
 413       BOOST_TEST(v2 % g == 0);
 414       BOOST_TEST_EQ(g, boost::integer::gcd_detail::mixed_binary_gcd(v1, v2));
 415       BOOST_TEST_EQ(g, boost::integer::gcd_detail::Stein_gcd(v1, v2));
 416    }
 417 }
 418
 419 // LCM tests
 420
 421 // LCM on signed integer types
 422 template< class T > void lcm_int_test() // signed_test_types
 423 {
 424 #ifndef BOOST_MSVC
 425     using boost::integer::lcm;
 426     using boost::integer::lcm_evaluator;
 427 #else
 428     using namespace boost::integer;
 429 #endif
 430
 431     // Originally from Boost.Rational tests
 432     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(1), static_cast<T>(-1)), static_cast<T>( 1) );
 433     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-1), static_cast<T>(1)), static_cast<T>( 1) );
 434     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(1), static_cast<T>(1)), static_cast<T>( 1) );
 435     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-1), static_cast<T>(-1)), static_cast<T>( 1) );
 436     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0), static_cast<T>(0)), static_cast<T>( 0) );
 437     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(6), static_cast<T>(0)), static_cast<T>( 0) );
 438     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0), static_cast<T>(7)), static_cast<T>( 0) );
 439     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-5), static_cast<T>(0)), static_cast<T>( 0) );
 440     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0), static_cast<T>(-4)), static_cast<T>( 0) );
 441     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(18), static_cast<T>(30)), static_cast<T>(90) );
 442     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-6), static_cast<T>(9)), static_cast<T>(18) );
 443     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-10), static_cast<T>(-10)), static_cast<T>(10) );
 444     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(25), static_cast<T>(-10)), static_cast<T>(50) );
 445     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(3), static_cast<T>(7)), static_cast<T>(21) );
 446     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(8), static_cast<T>(9)), static_cast<T>(72) );
 447     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(7), static_cast<T>(49)), static_cast<T>(49) );
 448     // Again with function object:
 449     BOOST_TEST_EQ(lcm_evaluator<T>()(1, -1), static_cast<T>(1));
 450     BOOST_TEST_EQ(lcm_evaluator<T>()(-1, 1), static_cast<T>(1));
 451     BOOST_TEST_EQ(lcm_evaluator<T>()(1, 1), static_cast<T>(1));
 452     BOOST_TEST_EQ(lcm_evaluator<T>()(-1, -1), static_cast<T>(1));
 453     BOOST_TEST_EQ(lcm_evaluator<T>()(0, 0), static_cast<T>(0));
 454     BOOST_TEST_EQ(lcm_evaluator<T>()(6, 0), static_cast<T>(0));
 455     BOOST_TEST_EQ(lcm_evaluator<T>()(0, 7), static_cast<T>(0));
 456     BOOST_TEST_EQ(lcm_evaluator<T>()(-5, 0), static_cast<T>(0));
 457     BOOST_TEST_EQ(lcm_evaluator<T>()(0, -4), static_cast<T>(0));
 458     BOOST_TEST_EQ(lcm_evaluator<T>()(18, 30), static_cast<T>(90));
 459     BOOST_TEST_EQ(lcm_evaluator<T>()(-6, 9), static_cast<T>(18));
 460     BOOST_TEST_EQ(lcm_evaluator<T>()(-10, -10), static_cast<T>(10));
 461     BOOST_TEST_EQ(lcm_evaluator<T>()(25, -10), static_cast<T>(50));
 462     BOOST_TEST_EQ(lcm_evaluator<T>()(3, 7), static_cast<T>(21));
 463     BOOST_TEST_EQ(lcm_evaluator<T>()(8, 9), static_cast<T>(72));
 464     BOOST_TEST_EQ(lcm_evaluator<T>()(7, 49), static_cast<T>(49));
 465 }
 466
 467 // LCM on unmarked signed integer type
 468 void lcm_unmarked_int_test()
 469 {
 470 #ifndef BOOST_MSVC
 471     using boost::integer::lcm;
 472 #else
 473     using namespace boost::integer;
 474 #endif
 475
 476     // The regular signed-integer LCM function performs the unsigned version,
 477     // then does an absolute-value on the result.  Signed types that are not
 478     // marked as such (due to no std::numeric_limits specialization) may be off
 479     // by a sign.
 480     BOOST_TEST_EQ( abs(boost::integer::lcm(   static_cast<MyInt2>(1), static_cast<MyInt2>(-1) )), MyInt2( 1) );
 481     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-1), static_cast<MyInt2>(1) )), MyInt2( 1) );
 482     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(1), static_cast<MyInt2>(1) )), MyInt2( 1) );
 483     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-1), static_cast<MyInt2>(-1) )), MyInt2( 1) );
 484     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(0), static_cast<MyInt2>(0) )), MyInt2( 0) );
 485     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(6), static_cast<MyInt2>(0) )), MyInt2( 0) );
 486     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(0), static_cast<MyInt2>(7) )), MyInt2( 0) );
 487     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-5), static_cast<MyInt2>(0) )), MyInt2( 0) );
 488     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(0), static_cast<MyInt2>(-4) )), MyInt2( 0) );
 489     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(18), static_cast<MyInt2>(30) )), MyInt2(90) );
 490     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-6), static_cast<MyInt2>(9) )), MyInt2(18) );
 491     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-10), static_cast<MyInt2>(-10) )), MyInt2(10) );
 492     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(25), static_cast<MyInt2>(-10) )), MyInt2(50) );
 493     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(3), static_cast<MyInt2>(7) )), MyInt2(21) );
 494     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(8), static_cast<MyInt2>(9) )), MyInt2(72) );
 495     BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(7), static_cast<MyInt2>(49) )), MyInt2(49) );
 496 }
 497
 498 // LCM on unsigned integer types
 499 template< class T > void lcm_unsigned_test() // unsigned_test_types
 500 {
 501 #ifndef BOOST_MSVC
 502     using boost::integer::lcm;
 503 #else
 504     using namespace boost::integer;
 505 #endif
 506
 507     // Note that unmarked types (i.e. have no std::numeric_limits
 508     // specialization) are treated like non/unsigned types
 509     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(1u), static_cast<T>(1u)), static_cast<T>( 1u) );
 510     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0u), static_cast<T>(0u)), static_cast<T>( 0u) );
 511     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(6u), static_cast<T>(0u)), static_cast<T>( 0u) );
 512     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0u), static_cast<T>(7u)), static_cast<T>( 0u) );
 513     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(18u), static_cast<T>(30u)), static_cast<T>(90u) );
 514     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(3u), static_cast<T>(7u)), static_cast<T>(21u) );
 515     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(8u), static_cast<T>(9u)), static_cast<T>(72u) );
 516     BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(7u), static_cast<T>(49u)), static_cast<T>(49u) );
 517 }
 518
 519 // LCM at compile-time
 520 void lcm_static_test()
 521 {
 522 #ifndef BOOST_MSVC
 523     using boost::integer::static_lcm;
 524 #else
 525     using namespace boost::integer;
 526 #endif
 527
 528     // Can't use "BOOST_TEST_EQ", otherwise the "value" member will be
 529     // disqualified as compile-time-only constant, needing explicit definition
 530     BOOST_TEST( (static_lcm< 1,  1>::value) ==  1 );
 531     BOOST_TEST( (static_lcm< 0,  0>::value) ==  0 );
 532     BOOST_TEST( (static_lcm< 6,  0>::value) ==  0 );
 533     BOOST_TEST( (static_lcm< 0,  7>::value) ==  0 );
 534     BOOST_TEST( (static_lcm<18, 30>::value) == 90 );
 535     BOOST_TEST( (static_lcm< 3,  7>::value) == 21 );
 536     BOOST_TEST( (static_lcm< 8,  9>::value) == 72 );
 537     BOOST_TEST( (static_lcm< 7, 49>::value) == 49 );
 538 }
 539
 540 void variadics()
 541 {
 542    unsigned i[] = { 44, 56, 76, 88 };
 543    BOOST_TEST_EQ(boost::integer::gcd_range(i, i + 4).first, 4);
 544    BOOST_TEST_EQ(boost::integer::gcd_range(i, i + 4).second, i + 4);
 545    BOOST_TEST_EQ(boost::integer::lcm_range(i, i + 4).first, 11704);
 546    BOOST_TEST_EQ(boost::integer::lcm_range(i, i + 4).second, i + 4);
 547 #ifndef BOOST_NO_CXX11_VARIADIC_TEMPLATES
 548    BOOST_TEST_EQ(boost::integer::gcd(i[0], i[1], i[2], i[3]), 4);
 549    BOOST_TEST_EQ(boost::integer::lcm(i[0], i[1], i[2], i[3]), 11704);
 550 #endif
 551 }
 552
 553 // Test case from Boost.Rational, need to make sure we don't break the rational lib:
 554 template <class T> void gcd_and_lcm_on_rationals()
 555 {
 556    typedef boost::rational<T> rational;
 557    BOOST_TEST_EQ(boost::integer::gcd(rational(1, 4), rational(1, 3)),
 558       rational(1, 12));
 559    BOOST_TEST_EQ(boost::integer::lcm(rational(1, 4), rational(1, 3)),
 560       rational(1));
 561 }
 562
 563 #ifndef DISABLE_MP_TESTS
 564 #define TEST_SIGNED_( test ) \
 565     test<signed char>(); \
 566     test<short>(); \
 567     test<int>(); \
 568     test<long>(); \
 569     test<MyInt1>(); \
 570     test<boost::multiprecision::cpp_int>(); \
 571     test<boost::multiprecision::int512_t>();
 572 #else
 573 #define TEST_SIGNED_( test ) \
 574     test<signed char>(); \
 575     test<short>(); \
 576     test<int>(); \
 577     test<long>(); \
 578     test<MyInt1>();
 579 #endif
 580
 581 #ifdef BOOST_HAS_LONG_LONG
 582 # define TEST_SIGNED__( test ) \
 583     TEST_SIGNED_( test ) \
 584     test<boost::long_long_type>();
 585 #elif defined(BOOST_HAS_MS_INT64)
 586 # define TEST_SIGNED__( test ) \
 587     TEST_SIGNED_( test ) \
 588     test<__int64>();
 589 #endif
 590 #ifndef DISABLE_MP_TESTS
 591 #define TEST_UNSIGNED_( test ) \
 592     test<unsigned char>(); \
 593     test<unsigned short>(); \
 594     test<unsigned>(); \
 595     test<unsigned long>(); \
 596     test<MyUnsigned1>(); \
 597     test<MyUnsigned2>(); \
 598     test<boost::multiprecision::uint512_t>();
 599 #else
 600 #define TEST_UNSIGNED_( test ) \
 601     test<unsigned char>(); \
 602     test<unsigned short>(); \
 603     test<unsigned>(); \
 604     test<unsigned long>(); \
 605     test<MyUnsigned1>(); \
 606     test<MyUnsigned2>();
 607 #endif
 608
 609 #ifdef BOOST_HAS_LONG_LONG
 610 # define TEST_UNSIGNED( test ) \
 611     TEST_UNSIGNED_( test ) \
 612     test<boost::ulong_long_type>();
 613 #elif defined(BOOST_HAS_MS_INT64)
 614 # define TEST_UNSIGNED( test ) \
 615     TEST_UNSIGNED_( test ) \
 616     test<unsigned __int64>();
 617 #endif
 618
 619 #ifdef BOOST_INTEGER_HAS_GMPXX_H
 620 #  define TEST_SIGNED(test)\
 621       TEST_SIGNED__(test)\
 622       test<mpz_class>();
 623 #  define TEST_SIGNED_NO_GMP(test) TEST_SIGNED__(test)
 624 #else
 625 #  define TEST_SIGNED(test) TEST_SIGNED__(test)
 626 #  define TEST_SIGNED_NO_GMP(test) TEST_SIGNED__(test)
 627 #endif
 628
 629 int main()
 630 {
 631    TEST_SIGNED(gcd_int_test)
 632    gcd_unmarked_int_test();
 633    TEST_UNSIGNED(gcd_unsigned_test)
 634    gcd_static_test();
 635    gcd_method_test();
 636
 637    TEST_SIGNED(lcm_int_test)
 638    lcm_unmarked_int_test();
 639    TEST_UNSIGNED(lcm_unsigned_test)
 640    lcm_static_test();
 641    variadics();
 642    TEST_SIGNED_NO_GMP(gcd_and_lcm_on_rationals)
 643
 644    return boost::report_errors();
 645 }