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