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