| // Boost GCD & LCM common_factor.hpp test program --------------------------// |
| |
| // (C) Copyright Daryle Walker 2001, 2006. |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // https://www.boost.org/LICENSE_1_0.txt) |
| |
| // See https://www.boost.org for most recent version including documentation. |
| |
| // Revision History |
| // 01 Dec 2006 Various fixes for old compilers (Joaquin M Lopez Munoz) |
| // 10 Nov 2006 Make long long and __int64 mutually exclusive (Daryle Walker) |
| // 04 Nov 2006 Use more built-in numeric types, binary-GCD (Daryle Walker) |
| // 03 Nov 2006 Use custom numeric types (Daryle Walker) |
| // 02 Nov 2006 Change to Boost.Test's unit test system (Daryle Walker) |
| // 07 Nov 2001 Initial version (Daryle Walker) |
| |
| #define BOOST_TEST_MAIN "Boost.integer GCD & LCM unit tests" |
| |
| #include <boost/config.hpp> // for BOOST_MSVC, etc. |
| #include <boost/detail/workaround.hpp> |
| #include <boost/integer/common_factor.hpp> // for boost::integer::gcd, etc. |
| #include <boost/mpl/list.hpp> // for boost::mpl::list |
| #include <boost/operators.hpp> |
| #include <boost/core/lightweight_test.hpp> |
| #include <boost/random/mersenne_twister.hpp> |
| #include <boost/random/uniform_int.hpp> |
| #include <boost/rational.hpp> |
| |
| #include <istream> // for std::basic_istream |
| #include <limits> // for std::numeric_limits |
| #include <ostream> // for std::basic_ostream |
| |
| #ifdef BOOST_INTEGER_HAS_GMPXX_H |
| #include <gmpxx.h> |
| #endif |
| |
| #include "multiprecision_config.hpp" |
| |
| #ifndef DISABLE_MP_TESTS |
| #include <boost/multiprecision/cpp_int.hpp> |
| #endif |
| |
| namespace { |
| |
| // TODO: add polynominal/non-real type; especially after any switch to the |
| // binary-GCD algorithm for built-in types |
| |
| // Custom integer class (template) |
| template < typename IntType, int ID = 0 > |
| class my_wrapped_integer |
| : private ::boost::shiftable1<my_wrapped_integer<IntType, ID>, |
| ::boost::operators<my_wrapped_integer<IntType, ID> > > |
| { |
| // Helper type-aliases |
| typedef my_wrapped_integer self_type; |
| typedef IntType self_type::* bool_type; |
| |
| // Member data |
| IntType v_; |
| |
| public: |
| // Template parameters |
| typedef IntType int_type; |
| |
| BOOST_STATIC_CONSTANT(int,id = ID); |
| |
| // Lifetime management (use automatic destructor and copy constructor) |
| my_wrapped_integer( int_type const &v = int_type() ) : v_( v ) {} |
| |
| // Accessors |
| int_type value() const { return this->v_; } |
| |
| // Operators (use automatic copy assignment) |
| operator bool_type() const { return this->v_ ? &self_type::v_ : 0; } |
| |
| self_type & operator ++() { ++this->v_; return *this; } |
| self_type & operator --() { --this->v_; return *this; } |
| |
| self_type operator ~() const { return self_type( ~this->v_ ); } |
| self_type operator !() const { return self_type( !this->v_ ); } |
| self_type operator +() const { return self_type( +this->v_ ); } |
| self_type operator -() const { return self_type( -this->v_ ); } |
| |
| bool operator <( self_type const &r ) const { return this->v_ < r.v_; } |
| bool operator ==( self_type const &r ) const { return this->v_ == r.v_; } |
| |
| self_type &operator *=(self_type const &r) {this->v_ *= r.v_; return *this;} |
| self_type &operator /=(self_type const &r) {this->v_ /= r.v_; return *this;} |
| self_type &operator %=(self_type const &r) {this->v_ %= r.v_; return *this;} |
| self_type &operator +=(self_type const &r) {this->v_ += r.v_; return *this;} |
| self_type &operator -=(self_type const &r) {this->v_ -= r.v_; return *this;} |
| self_type &operator<<=(self_type const &r){this->v_ <<= r.v_; return *this;} |
| self_type &operator>>=(self_type const &r){this->v_ >>= r.v_; return *this;} |
| self_type &operator &=(self_type const &r) {this->v_ &= r.v_; return *this;} |
| self_type &operator |=(self_type const &r) {this->v_ |= r.v_; return *this;} |
| self_type &operator ^=(self_type const &r) {this->v_ ^= r.v_; return *this;} |
| |
| // Input & output |
| friend std::istream & operator >>( std::istream &i, self_type &x ) |
| { return i >> x.v_; } |
| |
| friend std::ostream & operator <<( std::ostream &o, self_type const &x ) |
| { return o << x.v_; } |
| |
| }; // my_wrapped_integer |
| |
| template < typename IntType, int ID > |
| my_wrapped_integer<IntType, ID> abs( my_wrapped_integer<IntType, ID> const &x ) |
| { return ( x < my_wrapped_integer<IntType, ID>(0) ) ? -x : +x; } |
| |
| typedef my_wrapped_integer<int> MyInt1; |
| typedef my_wrapped_integer<unsigned> MyUnsigned1; |
| typedef my_wrapped_integer<int, 1> MyInt2; |
| typedef my_wrapped_integer<unsigned, 1> MyUnsigned2; |
| |
| // Without these explicit instantiations, MSVC++ 6.5/7.0 does not find |
| // some friend operators in certain contexts. |
| MyInt1 dummy1; |
| MyUnsigned1 dummy2; |
| MyInt2 dummy3; |
| MyUnsigned2 dummy4; |
| |
| // Various types to test with each GCD/LCM |
| typedef ::boost::mpl::list<signed char, short, int, long, |
| #if BOOST_WORKAROUND(BOOST_MSVC, <= 1500) |
| #elif defined(BOOST_HAS_LONG_LONG) |
| boost::long_long_type, |
| #elif defined(BOOST_HAS_MS_INT64) |
| __int64, |
| #endif |
| MyInt1 |
| #ifndef DISABLE_MP_TESTS |
| , boost::multiprecision::cpp_int |
| #endif |
| > signed_test_types; |
| typedef ::boost::mpl::list<unsigned char, unsigned short, unsigned, |
| unsigned long, |
| #if BOOST_WORKAROUND(BOOST_MSVC, <= 1500) |
| #elif defined(BOOST_HAS_LONG_LONG) |
| boost::ulong_long_type, |
| #elif defined(BOOST_HAS_MS_INT64) |
| unsigned __int64, |
| #endif |
| MyUnsigned1, MyUnsigned2 /*, boost::multiprecision::uint256_t*/> unsigned_test_types; |
| |
| } // namespace |
| |
| #define BOOST_NO_MACRO_EXPAND /**/ |
| |
| // Specialize numeric_limits for _some_ of our types |
| namespace std |
| { |
| |
| template < > |
| class numeric_limits< MyInt1 > |
| { |
| typedef MyInt1::int_type int_type; |
| typedef numeric_limits<int_type> limits_type; |
| |
| public: |
| BOOST_STATIC_CONSTANT(bool, is_specialized = limits_type::is_specialized); |
| |
| static MyInt1 min BOOST_NO_MACRO_EXPAND() throw() { return (limits_type::min)(); } |
| static MyInt1 max BOOST_NO_MACRO_EXPAND() throw() { return (limits_type::max)(); } |
| |
| BOOST_STATIC_CONSTANT(int, digits = limits_type::digits); |
| BOOST_STATIC_CONSTANT(int, digits10 = limits_type::digits10); |
| #ifndef BOOST_NO_CXX11_NUMERIC_LIMITS |
| BOOST_STATIC_CONSTANT(int, max_digits10 = limits_type::max_digits10); |
| #endif |
| BOOST_STATIC_CONSTANT(bool, is_signed = limits_type::is_signed); |
| BOOST_STATIC_CONSTANT(bool, is_integer = limits_type::is_integer); |
| BOOST_STATIC_CONSTANT(bool, is_exact = limits_type::is_exact); |
| BOOST_STATIC_CONSTANT(int, radix = limits_type::radix); |
| static MyInt1 epsilon() throw() { return limits_type::epsilon(); } |
| static MyInt1 round_error() throw() { return limits_type::round_error(); } |
| |
| BOOST_STATIC_CONSTANT(int, min_exponent = limits_type::min_exponent); |
| BOOST_STATIC_CONSTANT(int, min_exponent10 = limits_type::min_exponent10); |
| BOOST_STATIC_CONSTANT(int, max_exponent = limits_type::max_exponent); |
| BOOST_STATIC_CONSTANT(int, max_exponent10 = limits_type::max_exponent10); |
| |
| BOOST_STATIC_CONSTANT(bool, has_infinity = limits_type::has_infinity); |
| BOOST_STATIC_CONSTANT(bool, has_quiet_NaN = limits_type::has_quiet_NaN); |
| BOOST_STATIC_CONSTANT(bool, has_signaling_NaN = limits_type::has_signaling_NaN); |
| BOOST_STATIC_CONSTANT(float_denorm_style, has_denorm = limits_type::has_denorm); |
| BOOST_STATIC_CONSTANT(bool, has_denorm_loss = limits_type::has_denorm_loss); |
| |
| static MyInt1 infinity() throw() { return limits_type::infinity(); } |
| static MyInt1 quiet_NaN() throw() { return limits_type::quiet_NaN(); } |
| static MyInt1 signaling_NaN() throw() {return limits_type::signaling_NaN();} |
| static MyInt1 denorm_min() throw() { return limits_type::denorm_min(); } |
| |
| BOOST_STATIC_CONSTANT(bool, is_iec559 = limits_type::is_iec559); |
| BOOST_STATIC_CONSTANT(bool, is_bounded = limits_type::is_bounded); |
| BOOST_STATIC_CONSTANT(bool, is_modulo = limits_type::is_modulo); |
| |
| BOOST_STATIC_CONSTANT(bool, traps = limits_type::traps); |
| BOOST_STATIC_CONSTANT(bool, tinyness_before = limits_type::tinyness_before); |
| BOOST_STATIC_CONSTANT(float_round_style, round_style = limits_type::round_style); |
| |
| }; // std::numeric_limits<MyInt1> |
| |
| template < > |
| class numeric_limits< MyUnsigned1 > |
| { |
| typedef MyUnsigned1::int_type int_type; |
| typedef numeric_limits<int_type> limits_type; |
| |
| public: |
| BOOST_STATIC_CONSTANT(bool, is_specialized = limits_type::is_specialized); |
| |
| static MyUnsigned1 min BOOST_NO_MACRO_EXPAND() throw() { return (limits_type::min)(); } |
| static MyUnsigned1 max BOOST_NO_MACRO_EXPAND() throw() { return (limits_type::max)(); } |
| |
| BOOST_STATIC_CONSTANT(int, digits = limits_type::digits); |
| BOOST_STATIC_CONSTANT(int, digits10 = limits_type::digits10); |
| #ifndef BOOST_NO_CXX11_NUMERIC_LIMITS |
| BOOST_STATIC_CONSTANT(int, max_digits10 = limits_type::max_digits10); |
| #endif |
| BOOST_STATIC_CONSTANT(bool, is_signed = limits_type::is_signed); |
| BOOST_STATIC_CONSTANT(bool, is_integer = limits_type::is_integer); |
| BOOST_STATIC_CONSTANT(bool, is_exact = limits_type::is_exact); |
| BOOST_STATIC_CONSTANT(int, radix = limits_type::radix); |
| static MyUnsigned1 epsilon() throw() { return limits_type::epsilon(); } |
| static MyUnsigned1 round_error() throw(){return limits_type::round_error();} |
| |
| BOOST_STATIC_CONSTANT(int, min_exponent = limits_type::min_exponent); |
| BOOST_STATIC_CONSTANT(int, min_exponent10 = limits_type::min_exponent10); |
| BOOST_STATIC_CONSTANT(int, max_exponent = limits_type::max_exponent); |
| BOOST_STATIC_CONSTANT(int, max_exponent10 = limits_type::max_exponent10); |
| |
| BOOST_STATIC_CONSTANT(bool, has_infinity = limits_type::has_infinity); |
| BOOST_STATIC_CONSTANT(bool, has_quiet_NaN = limits_type::has_quiet_NaN); |
| BOOST_STATIC_CONSTANT(bool, has_signaling_NaN = limits_type::has_signaling_NaN); |
| BOOST_STATIC_CONSTANT(float_denorm_style, has_denorm = limits_type::has_denorm); |
| BOOST_STATIC_CONSTANT(bool, has_denorm_loss = limits_type::has_denorm_loss); |
| |
| static MyUnsigned1 infinity() throw() { return limits_type::infinity(); } |
| static MyUnsigned1 quiet_NaN() throw() { return limits_type::quiet_NaN(); } |
| static MyUnsigned1 signaling_NaN() throw() |
| { return limits_type::signaling_NaN(); } |
| static MyUnsigned1 denorm_min() throw(){ return limits_type::denorm_min(); } |
| |
| BOOST_STATIC_CONSTANT(bool, is_iec559 = limits_type::is_iec559); |
| BOOST_STATIC_CONSTANT(bool, is_bounded = limits_type::is_bounded); |
| BOOST_STATIC_CONSTANT(bool, is_modulo = limits_type::is_modulo); |
| |
| BOOST_STATIC_CONSTANT(bool, traps = limits_type::traps); |
| BOOST_STATIC_CONSTANT(bool, tinyness_before = limits_type::tinyness_before); |
| BOOST_STATIC_CONSTANT(float_round_style, round_style = limits_type::round_style); |
| |
| }; // std::numeric_limits<MyUnsigned1> |
| |
| #if BOOST_WORKAROUND(BOOST_MSVC,<1300) |
| // MSVC 6.0 lacks operator<< for __int64, see |
| // https://support.microsoft.com/kb/168440/ |
| |
| inline ostream& operator<<(ostream& os, __int64 i) |
| { |
| char buf[20]; |
| sprintf(buf,"%I64d", i); |
| os << buf; |
| return os; |
| } |
| |
| inline ostream& operator<<(ostream& os, unsigned __int64 i) |
| { |
| char buf[20]; |
| sprintf(buf,"%I64u", i); |
| os << buf; |
| return os; |
| } |
| #endif |
| |
| } // namespace std |
| |
| // GCD tests |
| |
| // GCD on signed integer types |
| template< class T > void gcd_int_test() // signed_test_types |
| { |
| #ifndef BOOST_MSVC |
| using boost::integer::gcd; |
| using boost::integer::gcd_evaluator; |
| #else |
| using namespace boost::integer; |
| #endif |
| |
| // Originally from Boost.Rational tests |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(1), static_cast<T>(-1)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-1), static_cast<T>(1)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(1), static_cast<T>(1)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-1), static_cast<T>(-1)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0), static_cast<T>(0)), static_cast<T>( 0) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(7), static_cast<T>(0)), static_cast<T>( 7) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0), static_cast<T>(9)), static_cast<T>( 9) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-7), static_cast<T>(0)), static_cast<T>( 7) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0), static_cast<T>(-9)), static_cast<T>( 9) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(42), static_cast<T>(30)), static_cast<T>( 6) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(6), static_cast<T>(-9)), static_cast<T>( 3) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-10), static_cast<T>(-10)), static_cast<T>(10) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(-25), static_cast<T>(-10)), static_cast<T>( 5) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(3), static_cast<T>(7)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(8), static_cast<T>(9)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(7), static_cast<T>(49)), static_cast<T>( 7) ); |
| // Again with function object: |
| BOOST_TEST_EQ(gcd_evaluator<T>()(1, -1), static_cast<T>(1)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(-1, 1), static_cast<T>(1)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(1, 1), static_cast<T>(1)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(-1, -1), static_cast<T>(1)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(0, 0), static_cast<T>(0)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(7, 0), static_cast<T>(7)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(0, 9), static_cast<T>(9)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(-7, 0), static_cast<T>(7)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(0, -9), static_cast<T>(9)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(42, 30), static_cast<T>(6)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(6, -9), static_cast<T>(3)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(-10, -10), static_cast<T>(10)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(-25, -10), static_cast<T>(5)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(3, 7), static_cast<T>(1)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(8, 9), static_cast<T>(1)); |
| BOOST_TEST_EQ(gcd_evaluator<T>()(7, 49), static_cast<T>(7)); |
| } |
| |
| // GCD on unmarked signed integer type |
| void gcd_unmarked_int_test() |
| { |
| #ifndef BOOST_MSVC |
| using boost::integer::gcd; |
| #else |
| using namespace boost::integer; |
| #endif |
| |
| // The regular signed-integer GCD function performs the unsigned version, |
| // then does an absolute-value on the result. Signed types that are not |
| // marked as such (due to no std::numeric_limits specialization) may be off |
| // by a sign. |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(1), static_cast<MyInt2>(-1) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-1), static_cast<MyInt2>(1) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(1), static_cast<MyInt2>(1) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-1), static_cast<MyInt2>(-1) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(0), static_cast<MyInt2>(0) )), MyInt2( 0) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(7), static_cast<MyInt2>(0) )), MyInt2( 7) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(0), static_cast<MyInt2>(9) )), MyInt2( 9) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-7), static_cast<MyInt2>(0) )), MyInt2( 7) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(0), static_cast<MyInt2>(-9) )), MyInt2( 9) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(42), static_cast<MyInt2>(30))), MyInt2( 6) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(6), static_cast<MyInt2>(-9) )), MyInt2( 3) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-10), static_cast<MyInt2>(-10) )), MyInt2(10) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(-25), static_cast<MyInt2>(-10) )), MyInt2( 5) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(3), static_cast<MyInt2>(7) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(8), static_cast<MyInt2>(9) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::gcd(static_cast<MyInt2>(7), static_cast<MyInt2>(49) )), MyInt2( 7) ); |
| } |
| |
| // GCD on unsigned integer types |
| template< class T > void gcd_unsigned_test() // unsigned_test_types |
| { |
| #ifndef BOOST_MSVC |
| using boost::integer::gcd; |
| #else |
| using namespace boost::integer; |
| #endif |
| |
| // Note that unmarked types (i.e. have no std::numeric_limits |
| // specialization) are treated like non/unsigned types |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(1u), static_cast<T>(1u)), static_cast<T>( 1u) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0u), static_cast<T>(0u)), static_cast<T>( 0u) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(7u), static_cast<T>(0u)), static_cast<T>( 7u) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(0u), static_cast<T>(9u)), static_cast<T>( 9u) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(42u), static_cast<T>(30u)), static_cast<T>( 6u) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(3u), static_cast<T>(7u)), static_cast<T>( 1u) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(8u), static_cast<T>(9u)), static_cast<T>( 1u) ); |
| BOOST_TEST_EQ( boost::integer::gcd(static_cast<T>(7u), static_cast<T>(49u)), static_cast<T>( 7u) ); |
| } |
| |
| // GCD at compile-time |
| void gcd_static_test() |
| { |
| #ifndef BOOST_MSVC |
| using boost::integer::static_gcd; |
| #else |
| using namespace boost::integer; |
| #endif |
| |
| // Can't use "BOOST_TEST_EQ", otherwise the "value" member will be |
| // disqualified as compile-time-only constant, needing explicit definition |
| BOOST_TEST( (static_gcd< 1, 1>::value) == 1 ); |
| BOOST_TEST( (static_gcd< 0, 0>::value) == 0 ); |
| BOOST_TEST( (static_gcd< 7, 0>::value) == 7 ); |
| BOOST_TEST( (static_gcd< 0, 9>::value) == 9 ); |
| BOOST_TEST( (static_gcd<42, 30>::value) == 6 ); |
| BOOST_TEST( (static_gcd< 3, 7>::value) == 1 ); |
| BOOST_TEST( (static_gcd< 8, 9>::value) == 1 ); |
| BOOST_TEST( (static_gcd< 7, 49>::value) == 7 ); |
| } |
| |
| void gcd_method_test() |
| { |
| // Verify that the 3 different methods all yield the same result: |
| boost::random::mt19937 gen; |
| boost::random::uniform_int_distribution<int> d(0, ((std::numeric_limits<int>::max)() / 2)); |
| |
| for (unsigned int i = 0; i < 10000; ++i) |
| { |
| int v1 = d(gen); |
| int v2 = d(gen); |
| int g = boost::integer::gcd_detail::Euclid_gcd(v1, v2); |
| BOOST_TEST(v1 % g == 0); |
| BOOST_TEST(v2 % g == 0); |
| BOOST_TEST_EQ(g, boost::integer::gcd_detail::mixed_binary_gcd(v1, v2)); |
| BOOST_TEST_EQ(g, boost::integer::gcd_detail::Stein_gcd(v1, v2)); |
| } |
| } |
| |
| // LCM tests |
| |
| // LCM on signed integer types |
| template< class T > void lcm_int_test() // signed_test_types |
| { |
| #ifndef BOOST_MSVC |
| using boost::integer::lcm; |
| using boost::integer::lcm_evaluator; |
| #else |
| using namespace boost::integer; |
| #endif |
| |
| // Originally from Boost.Rational tests |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(1), static_cast<T>(-1)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-1), static_cast<T>(1)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(1), static_cast<T>(1)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-1), static_cast<T>(-1)), static_cast<T>( 1) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0), static_cast<T>(0)), static_cast<T>( 0) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(6), static_cast<T>(0)), static_cast<T>( 0) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0), static_cast<T>(7)), static_cast<T>( 0) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-5), static_cast<T>(0)), static_cast<T>( 0) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0), static_cast<T>(-4)), static_cast<T>( 0) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(18), static_cast<T>(30)), static_cast<T>(90) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-6), static_cast<T>(9)), static_cast<T>(18) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(-10), static_cast<T>(-10)), static_cast<T>(10) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(25), static_cast<T>(-10)), static_cast<T>(50) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(3), static_cast<T>(7)), static_cast<T>(21) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(8), static_cast<T>(9)), static_cast<T>(72) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(7), static_cast<T>(49)), static_cast<T>(49) ); |
| // Again with function object: |
| BOOST_TEST_EQ(lcm_evaluator<T>()(1, -1), static_cast<T>(1)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(-1, 1), static_cast<T>(1)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(1, 1), static_cast<T>(1)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(-1, -1), static_cast<T>(1)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(0, 0), static_cast<T>(0)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(6, 0), static_cast<T>(0)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(0, 7), static_cast<T>(0)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(-5, 0), static_cast<T>(0)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(0, -4), static_cast<T>(0)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(18, 30), static_cast<T>(90)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(-6, 9), static_cast<T>(18)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(-10, -10), static_cast<T>(10)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(25, -10), static_cast<T>(50)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(3, 7), static_cast<T>(21)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(8, 9), static_cast<T>(72)); |
| BOOST_TEST_EQ(lcm_evaluator<T>()(7, 49), static_cast<T>(49)); |
| } |
| |
| // LCM on unmarked signed integer type |
| void lcm_unmarked_int_test() |
| { |
| #ifndef BOOST_MSVC |
| using boost::integer::lcm; |
| #else |
| using namespace boost::integer; |
| #endif |
| |
| // The regular signed-integer LCM function performs the unsigned version, |
| // then does an absolute-value on the result. Signed types that are not |
| // marked as such (due to no std::numeric_limits specialization) may be off |
| // by a sign. |
| BOOST_TEST_EQ( abs(boost::integer::lcm( static_cast<MyInt2>(1), static_cast<MyInt2>(-1) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-1), static_cast<MyInt2>(1) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(1), static_cast<MyInt2>(1) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-1), static_cast<MyInt2>(-1) )), MyInt2( 1) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(0), static_cast<MyInt2>(0) )), MyInt2( 0) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(6), static_cast<MyInt2>(0) )), MyInt2( 0) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(0), static_cast<MyInt2>(7) )), MyInt2( 0) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-5), static_cast<MyInt2>(0) )), MyInt2( 0) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(0), static_cast<MyInt2>(-4) )), MyInt2( 0) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(18), static_cast<MyInt2>(30) )), MyInt2(90) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-6), static_cast<MyInt2>(9) )), MyInt2(18) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(-10), static_cast<MyInt2>(-10) )), MyInt2(10) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(25), static_cast<MyInt2>(-10) )), MyInt2(50) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(3), static_cast<MyInt2>(7) )), MyInt2(21) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(8), static_cast<MyInt2>(9) )), MyInt2(72) ); |
| BOOST_TEST_EQ( abs(boost::integer::lcm(static_cast<MyInt2>(7), static_cast<MyInt2>(49) )), MyInt2(49) ); |
| } |
| |
| // LCM on unsigned integer types |
| template< class T > void lcm_unsigned_test() // unsigned_test_types |
| { |
| #ifndef BOOST_MSVC |
| using boost::integer::lcm; |
| #else |
| using namespace boost::integer; |
| #endif |
| |
| // Note that unmarked types (i.e. have no std::numeric_limits |
| // specialization) are treated like non/unsigned types |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(1u), static_cast<T>(1u)), static_cast<T>( 1u) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0u), static_cast<T>(0u)), static_cast<T>( 0u) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(6u), static_cast<T>(0u)), static_cast<T>( 0u) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(0u), static_cast<T>(7u)), static_cast<T>( 0u) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(18u), static_cast<T>(30u)), static_cast<T>(90u) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(3u), static_cast<T>(7u)), static_cast<T>(21u) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(8u), static_cast<T>(9u)), static_cast<T>(72u) ); |
| BOOST_TEST_EQ( boost::integer::lcm(static_cast<T>(7u), static_cast<T>(49u)), static_cast<T>(49u) ); |
| } |
| |
| // LCM at compile-time |
| void lcm_static_test() |
| { |
| #ifndef BOOST_MSVC |
| using boost::integer::static_lcm; |
| #else |
| using namespace boost::integer; |
| #endif |
| |
| // Can't use "BOOST_TEST_EQ", otherwise the "value" member will be |
| // disqualified as compile-time-only constant, needing explicit definition |
| BOOST_TEST( (static_lcm< 1, 1>::value) == 1 ); |
| BOOST_TEST( (static_lcm< 0, 0>::value) == 0 ); |
| BOOST_TEST( (static_lcm< 6, 0>::value) == 0 ); |
| BOOST_TEST( (static_lcm< 0, 7>::value) == 0 ); |
| BOOST_TEST( (static_lcm<18, 30>::value) == 90 ); |
| BOOST_TEST( (static_lcm< 3, 7>::value) == 21 ); |
| BOOST_TEST( (static_lcm< 8, 9>::value) == 72 ); |
| BOOST_TEST( (static_lcm< 7, 49>::value) == 49 ); |
| } |
| |
| void variadics() |
| { |
| unsigned i[] = { 44, 56, 76, 88 }; |
| BOOST_TEST_EQ(boost::integer::gcd_range(i, i + 4).first, 4); |
| BOOST_TEST_EQ(boost::integer::gcd_range(i, i + 4).second, i + 4); |
| BOOST_TEST_EQ(boost::integer::lcm_range(i, i + 4).first, 11704); |
| BOOST_TEST_EQ(boost::integer::lcm_range(i, i + 4).second, i + 4); |
| |
| unsigned i_gcd_unity[] = { 44, 56, 1, 88 }; |
| BOOST_TEST_EQ(boost::integer::gcd_range(i_gcd_unity, i_gcd_unity + 4).first, 1); |
| BOOST_TEST_EQ(boost::integer::gcd_range(i_gcd_unity, i_gcd_unity + 4).second, i_gcd_unity + 3); |
| |
| unsigned i_lcm_unity[] = { 44, 56, 0, 88 }; |
| BOOST_TEST_EQ(boost::integer::lcm_range(i_lcm_unity, i_lcm_unity + 4).first, 0); |
| BOOST_TEST_EQ(boost::integer::lcm_range(i_lcm_unity, i_lcm_unity + 4).second, i_lcm_unity + 3); |
| |
| #ifndef BOOST_NO_CXX11_VARIADIC_TEMPLATES |
| BOOST_TEST_EQ(boost::integer::gcd(i[0], i[1], i[2], i[3]), 4); |
| BOOST_TEST_EQ(boost::integer::lcm(i[0], i[1], i[2], i[3]), 11704); |
| #endif |
| } |
| |
| // Test case from Boost.Rational, need to make sure we don't break the rational lib: |
| template <class T> void gcd_and_lcm_on_rationals() |
| { |
| typedef boost::rational<T> rational; |
| BOOST_TEST_EQ(boost::integer::gcd(rational(1, 4), rational(1, 3)), |
| rational(1, 12)); |
| BOOST_TEST_EQ(boost::integer::lcm(rational(1, 4), rational(1, 3)), |
| rational(1)); |
| } |
| |
| #ifndef DISABLE_MP_TESTS |
| #define TEST_SIGNED_( test ) \ |
| test<signed char>(); \ |
| test<short>(); \ |
| test<int>(); \ |
| test<long>(); \ |
| test<MyInt1>(); \ |
| test<boost::multiprecision::cpp_int>(); \ |
| test<boost::multiprecision::int512_t>(); |
| #else |
| #define TEST_SIGNED_( test ) \ |
| test<signed char>(); \ |
| test<short>(); \ |
| test<int>(); \ |
| test<long>(); \ |
| test<MyInt1>(); |
| #endif |
| |
| #ifdef BOOST_HAS_LONG_LONG |
| # define TEST_SIGNED__( test ) \ |
| TEST_SIGNED_( test ) \ |
| test<boost::long_long_type>(); |
| #elif defined(BOOST_HAS_MS_INT64) |
| # define TEST_SIGNED__( test ) \ |
| TEST_SIGNED_( test ) \ |
| test<__int64>(); |
| #endif |
| #ifndef DISABLE_MP_TESTS |
| #define TEST_UNSIGNED_( test ) \ |
| test<unsigned char>(); \ |
| test<unsigned short>(); \ |
| test<unsigned>(); \ |
| test<unsigned long>(); \ |
| test<MyUnsigned1>(); \ |
| test<MyUnsigned2>(); \ |
| test<boost::multiprecision::uint512_t>(); |
| #else |
| #define TEST_UNSIGNED_( test ) \ |
| test<unsigned char>(); \ |
| test<unsigned short>(); \ |
| test<unsigned>(); \ |
| test<unsigned long>(); \ |
| test<MyUnsigned1>(); \ |
| test<MyUnsigned2>(); |
| #endif |
| |
| #ifdef BOOST_HAS_LONG_LONG |
| # define TEST_UNSIGNED( test ) \ |
| TEST_UNSIGNED_( test ) \ |
| test<boost::ulong_long_type>(); |
| #elif defined(BOOST_HAS_MS_INT64) |
| # define TEST_UNSIGNED( test ) \ |
| TEST_UNSIGNED_( test ) \ |
| test<unsigned __int64>(); |
| #endif |
| |
| #ifdef BOOST_INTEGER_HAS_GMPXX_H |
| # define TEST_SIGNED(test)\ |
| TEST_SIGNED__(test)\ |
| test<mpz_class>(); |
| # define TEST_SIGNED_NO_GMP(test) TEST_SIGNED__(test) |
| #else |
| # define TEST_SIGNED(test) TEST_SIGNED__(test) |
| # define TEST_SIGNED_NO_GMP(test) TEST_SIGNED__(test) |
| #endif |
| |
| int main() |
| { |
| TEST_SIGNED(gcd_int_test) |
| gcd_unmarked_int_test(); |
| TEST_UNSIGNED(gcd_unsigned_test) |
| gcd_static_test(); |
| gcd_method_test(); |
| |
| TEST_SIGNED(lcm_int_test) |
| lcm_unmarked_int_test(); |
| TEST_UNSIGNED(lcm_unsigned_test) |
| lcm_static_test(); |
| variadics(); |
| TEST_SIGNED_NO_GMP(gcd_and_lcm_on_rationals) |
| |
| return boost::report_errors(); |
| } |
