895 changes: 501 additions & 394 deletions include/boost/integer/common_factor_rt.hpp
View file

Large diffs are not rendered by default.

1 change: 1 addition & 0 deletions test/Jamfile.v2
View file
Expand Up @@ -20,6 +20,7 @@ test-suite integer
[ compile static_min_max_include_test.cpp ]
[ compile integer_fwd_include_test.cpp ]
[ compile gcd_constexpr14_test.cpp ]
[ compile gcd_noexcept_test.cpp ]
[ compile-fail fail_int_exact.cpp ]
[ compile-fail fail_int_fast.cpp ]
[ compile-fail fail_int_least.cpp ]
Expand Down
205 changes: 166 additions & 39 deletions test/common_factor_test.cpp
View file
Expand Up @@ -15,14 +15,17 @@
// 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.Math GCD & LCM unit tests"
#define BOOST_TEST_MAIN "Boost.integer GCD & LCM unit tests"

#include <boost/integer/common_factor.hpp>

#include <boost/config.hpp> // for BOOST_MSVC, etc.
#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/multiprecision/cpp_int.hpp>
#include <boost/random.hpp>
#include <boost/rational.hpp>

#include <istream> // for std::basic_istream
#include <limits> // for std::numeric_limits
Expand Down Expand Up @@ -109,6 +112,25 @@ 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, boost::multiprecision::cpp_int> 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 /**/
Expand Down Expand Up @@ -246,7 +268,12 @@ inline ostream& operator<<(ostream& os, unsigned __int64 i)
// 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( gcd<T>( 1, -1), static_cast<T>( 1) );
Expand All @@ -265,12 +292,33 @@ template< class T > void gcd_int_test() // signed_test_types
BOOST_TEST_EQ( gcd<T>( 3, 7), static_cast<T>( 1) );
BOOST_TEST_EQ( gcd<T>( 8, 9), static_cast<T>( 1) );
BOOST_TEST_EQ( gcd<T>( 7, 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
Expand All @@ -297,7 +345,11 @@ void gcd_unmarked_int_test()
// 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
Expand All @@ -314,29 +366,53 @@ template< class T > void gcd_unsigned_test() // unsigned_test_types
// GCD at compile-time
void gcd_static_test()
{
#ifndef BOOST_MSVC
using boost::integer::static_gcd;
#else
using namespace boost::integer;
#endif

BOOST_TEST_EQ( (static_gcd< 1, 1>::value), 1 );
BOOST_TEST_EQ( (static_gcd< 0, 0>::value), 0 );
BOOST_TEST_EQ( (static_gcd< 7, 0>::value), 7 );
BOOST_TEST_EQ( (static_gcd< 0, 9>::value), 9 );
BOOST_TEST_EQ( (static_gcd<42, 30>::value), 6 );
BOOST_TEST_EQ( (static_gcd< 3, 7>::value), 1 );
BOOST_TEST_EQ( (static_gcd< 8, 9>::value), 1 );
BOOST_TEST_EQ( (static_gcd< 7, 49>::value), 7 );
// 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 );
}

// TODO: non-built-in signed and unsigned integer tests, with and without
// numeric_limits specialization; polynominal tests; note any changes if
// built-ins switch to binary-GCD algorithm

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( lcm<T>( 1, -1), static_cast<T>( 1) );
Expand All @@ -355,12 +431,33 @@ template< class T > void lcm_int_test() // signed_test_types
BOOST_TEST_EQ( lcm<T>( 3, 7), static_cast<T>(21) );
BOOST_TEST_EQ( lcm<T>( 8, 9), static_cast<T>(72) );
BOOST_TEST_EQ( lcm<T>( 7, 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
Expand All @@ -387,7 +484,11 @@ void lcm_unmarked_int_test()
// 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
Expand All @@ -404,23 +505,46 @@ template< class T > void lcm_unsigned_test() // unsigned_test_types
// LCM at compile-time
void lcm_static_test()
{
#ifndef BOOST_MSVC
using boost::integer::static_lcm;
#else
using namespace boost::integer;
#endif

BOOST_TEST_EQ( (static_lcm< 1, 1>::value), 1 );
BOOST_TEST_EQ( (static_lcm< 0, 0>::value), 0 );
BOOST_TEST_EQ( (static_lcm< 6, 0>::value), 0 );
BOOST_TEST_EQ( (static_lcm< 0, 7>::value), 0 );
BOOST_TEST_EQ( (static_lcm<18, 30>::value), 90 );
BOOST_TEST_EQ( (static_lcm< 3, 7>::value), 21 );
BOOST_TEST_EQ( (static_lcm< 8, 9>::value), 72 );
BOOST_TEST_EQ( (static_lcm< 7, 49>::value), 49 );
// 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 );
}

// TODO: see GCD to-do

// main
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);
#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
}

// Various types to test with each GCD/LCM
// 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));
}

#define TEST_SIGNED_( test ) \
test<signed char>(); \
Expand Down Expand Up @@ -459,15 +583,18 @@ void lcm_static_test()

int main()
{
TEST_SIGNED( gcd_int_test )
gcd_unmarked_int_test();
TEST_UNSIGNED( gcd_unsigned_test )
gcd_static_test();

TEST_SIGNED( lcm_int_test )
lcm_unmarked_int_test();
TEST_UNSIGNED( lcm_unsigned_test )
lcm_static_test();

return boost::report_errors();
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(gcd_and_lcm_on_rationals)

return boost::report_errors();
}
61 changes: 41 additions & 20 deletions test/gcd_constexpr14_test.cpp
View file
Expand Up @@ -8,38 +8,59 @@

#ifndef BOOST_NO_CXX14_CONSTEXPR

void test_constexpr()
void test_constexpr1()
{
constexpr const boost::int64_t i = 347 * 463 * 727;
constexpr const boost::int64_t j = 191 * 347 * 281;

constexpr const boost::int64_t k = boost::integer::gcd(i, j);
constexpr const boost::int64_t l = boost::integer::lcm(i, j);

static_assert(k == 347, "Expected result not found in constexpr gcd.");
static_assert(l == 6268802158037, "Expected result not found in constexpr lcm.");
static_assert(k == 347, "Expected result not integer in constexpr gcd.");
static_assert(l == 6268802158037, "Expected result not integer in constexpr lcm.");
}

#endif
void test_constexpr2()
{
constexpr const boost::uint64_t i = 347 * 463 * 727;
constexpr const boost::uint64_t j = 191 * 347 * 281;

#ifndef BOOST_NO_CXX11_NOEXCEPT
constexpr const boost::uint64_t k = boost::integer::gcd(i, j);
constexpr const boost::uint64_t l = boost::integer::lcm(i, j);

void test_noexcept()
static_assert(k == 347, "Expected result not integer in constexpr gcd.");
static_assert(l == 6268802158037, "Expected result not integer in constexpr lcm.");
}

void test_constexpr3()
{
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned char>(2), static_cast<unsigned char>(4))), "Expected a noexcept function.");
#ifndef _MSC_VER
// This generates an internal compiler error if enabled as well as the following test:
static_assert(noexcept(boost::integer::gcd(static_cast<char>(2), static_cast<char>(4))), "Expected a noexcept function.");
#endif
static_assert(noexcept(boost::integer::gcd(static_cast<signed char>(2), static_cast<signed char>(4))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<short>(2), static_cast<short>(4))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned short>(2), static_cast<unsigned short>(4))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<int>(2), static_cast<int>(4))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned int>(2), static_cast<unsigned int>(4))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<long>(2), static_cast<long>(4))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned long>(2), static_cast<unsigned long>(4))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<long long>(2), static_cast<long long>(4))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned long long>(2), static_cast<unsigned long long>(4))), "Expected a noexcept function.");
constexpr const boost::uint64_t i = 347 * 463 * 727;
constexpr const boost::uint64_t j = 191 * 347 * 281;

constexpr const boost::uint64_t k = boost::integer::gcd_detail::Euclid_gcd(i, j);

static_assert(k == 347, "Expected result not integer in constexpr gcd.");
}

void test_constexpr4()
{
constexpr const boost::uint64_t i = 347 * 463 * 727;
constexpr const boost::uint64_t j = 191 * 347 * 281;

constexpr const boost::uint64_t k = boost::integer::gcd_detail::mixed_binary_gcd(i, j);

static_assert(k == 347, "Expected result not integer in constexpr gcd.");
}

void test_constexpr5()
{
constexpr const boost::uint64_t i = 347 * 463 * 727;
constexpr const boost::uint64_t j = 191 * 347 * 281;

constexpr const boost::uint64_t k = boost::integer::gcd_detail::Stein_gcd(i, j);

static_assert(k == 347, "Expected result not integer in constexpr gcd.");
}
#endif


35 changes: 35 additions & 0 deletions test/gcd_noexcept_test.cpp
View file
@@ -0,0 +1,35 @@

// (C) Copyright John Maddock 2017.
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#include <boost/integer/common_factor.hpp>

#if !defined(BOOST_NO_CXX11_NOEXCEPT) && !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
//
// These tests don't pass with GCC-4.x:
//
#if !defined(BOOST_GCC) || (BOOST_GCC >= 50000)

void test_noexcept(unsigned char a, unsigned char b)
{
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned char>(a), static_cast<unsigned char>(b))), "Expected a noexcept function.");
#ifndef _MSC_VER
// This generates an internal compiler error if enabled as well as the following test:
static_assert(noexcept(boost::integer::gcd(static_cast<char>(a), static_cast<char>(b))), "Expected a noexcept function.");
#endif
static_assert(noexcept(boost::integer::gcd(static_cast<signed char>(a), static_cast<signed char>(b))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<short>(a), static_cast<short>(b))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned short>(a), static_cast<unsigned short>(b))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<int>(a), static_cast<int>(b))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned int>(a), static_cast<unsigned int>(b))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<long>(a), static_cast<long>(b))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned long>(a), static_cast<unsigned long>(b))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<long long>(a), static_cast<long long>(b))), "Expected a noexcept function.");
static_assert(noexcept(boost::integer::gcd(static_cast<unsigned long long>(a), static_cast<unsigned long long>(b))), "Expected a noexcept function.");
}

#endif
#endif