]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | |
1e59de90 | 6 | // https://www.boost.org/LICENSE_1_0.txt) |
7c673cae | 7 | |
1e59de90 | 8 | // See https://www.boost.org for most recent version including documentation. |
7c673cae FG |
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 | ||
b32b8144 | 18 | #define BOOST_TEST_MAIN "Boost.integer GCD & LCM unit tests" |
7c673cae | 19 | |
b32b8144 | 20 | #include <boost/config.hpp> // for BOOST_MSVC, etc. |
7c673cae | 21 | #include <boost/detail/workaround.hpp> |
b32b8144 FG |
22 | #include <boost/integer/common_factor.hpp> // for boost::integer::gcd, etc. |
23 | #include <boost/mpl/list.hpp> // for boost::mpl::list | |
7c673cae FG |
24 | #include <boost/operators.hpp> |
25 | #include <boost/core/lightweight_test.hpp> | |
1e59de90 TL |
26 | #include <boost/random/mersenne_twister.hpp> |
27 | #include <boost/random/uniform_int.hpp> | |
b32b8144 | 28 | #include <boost/rational.hpp> |
7c673cae FG |
29 | |
30 | #include <istream> // for std::basic_istream | |
31 | #include <limits> // for std::numeric_limits | |
32 | #include <ostream> // for std::basic_ostream | |
33 | ||
b32b8144 FG |
34 | #ifdef BOOST_INTEGER_HAS_GMPXX_H |
35 | #include <gmpxx.h> | |
36 | #endif | |
37 | ||
92f5a8d4 | 38 | #include "multiprecision_config.hpp" |
b32b8144 FG |
39 | |
40 | #ifndef DISABLE_MP_TESTS | |
41 | #include <boost/multiprecision/cpp_int.hpp> | |
42 | #endif | |
7c673cae FG |
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) | |
69 | my_wrapped_integer( int_type const &v = int_type() ) : v_( v ) {} | |
70 | ||
71 | // Accessors | |
72 | int_type value() const { return this->v_; } | |
73 | ||
74 | // Operators (use automatic copy assignment) | |
75 | operator bool_type() const { return this->v_ ? &self_type::v_ : 0; } | |
76 | ||
77 | self_type & operator ++() { ++this->v_; return *this; } | |
78 | self_type & operator --() { --this->v_; return *this; } | |
79 | ||
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 | self_type operator -() const { return self_type( -this->v_ ); } | |
84 | ||
85 | bool operator <( self_type const &r ) const { return this->v_ < r.v_; } | |
86 | bool operator ==( self_type const &r ) const { return this->v_ == r.v_; } | |
87 | ||
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 | self_type &operator ^=(self_type const &r) {this->v_ ^= r.v_; return *this;} | |
98 | ||
99 | // Input & output | |
100 | friend std::istream & operator >>( std::istream &i, self_type &x ) | |
101 | { return i >> x.v_; } | |
102 | ||
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 > | |
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 | ||
b32b8144 FG |
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 | ||
7c673cae FG |
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 | ||
164 | static MyInt1 min BOOST_NO_MACRO_EXPAND() throw() { return (limits_type::min)(); } | |
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); | |
176 | static MyInt1 epsilon() throw() { return limits_type::epsilon(); } | |
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 | ||
190 | static MyInt1 infinity() throw() { return limits_type::infinity(); } | |
191 | static MyInt1 quiet_NaN() throw() { return limits_type::quiet_NaN(); } | |
192 | static MyInt1 signaling_NaN() throw() {return limits_type::signaling_NaN();} | |
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 | ||
214 | static MyUnsigned1 min BOOST_NO_MACRO_EXPAND() throw() { return (limits_type::min)(); } | |
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); | |
226 | static MyUnsigned1 epsilon() throw() { return limits_type::epsilon(); } | |
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 | ||
240 | static MyUnsigned1 infinity() throw() { return limits_type::infinity(); } | |
241 | static MyUnsigned1 quiet_NaN() throw() { return limits_type::quiet_NaN(); } | |
242 | static MyUnsigned1 signaling_NaN() throw() | |
243 | { return limits_type::signaling_NaN(); } | |
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 | |
92f5a8d4 | 258 | // https://support.microsoft.com/kb/168440/ |
7c673cae FG |
259 | |
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 | ||
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 | |
282 | template< class T > void gcd_int_test() // signed_test_types | |
283 | { | |
b32b8144 | 284 | #ifndef BOOST_MSVC |
7c673cae | 285 | using boost::integer::gcd; |
b32b8144 FG |
286 | using boost::integer::gcd_evaluator; |
287 | #else | |
288 | using namespace boost::integer; | |
289 | #endif | |
7c673cae FG |
290 | |
291 | // Originally from Boost.Rational tests | |
b32b8144 FG |
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)); | |
7c673cae FG |
325 | } |
326 | ||
327 | // GCD on unmarked signed integer type | |
328 | void gcd_unmarked_int_test() | |
329 | { | |
b32b8144 | 330 | #ifndef BOOST_MSVC |
7c673cae | 331 | using boost::integer::gcd; |
b32b8144 FG |
332 | #else |
333 | using namespace boost::integer; | |
334 | #endif | |
7c673cae FG |
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. | |
b32b8144 FG |
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) ); | |
7c673cae FG |
356 | } |
357 | ||
358 | // GCD on unsigned integer types | |
359 | template< class T > void gcd_unsigned_test() // unsigned_test_types | |
360 | { | |
b32b8144 | 361 | #ifndef BOOST_MSVC |
7c673cae | 362 | using boost::integer::gcd; |
b32b8144 FG |
363 | #else |
364 | using namespace boost::integer; | |
365 | #endif | |
7c673cae FG |
366 | |
367 | // Note that unmarked types (i.e. have no std::numeric_limits | |
368 | // specialization) are treated like non/unsigned types | |
b32b8144 FG |
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) ); | |
7c673cae FG |
377 | } |
378 | ||
379 | // GCD at compile-time | |
380 | void gcd_static_test() | |
381 | { | |
b32b8144 | 382 | #ifndef BOOST_MSVC |
7c673cae | 383 | using boost::integer::static_gcd; |
b32b8144 FG |
384 | #else |
385 | using namespace boost::integer; | |
386 | #endif | |
7c673cae | 387 | |
b32b8144 FG |
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 ); | |
7c673cae FG |
398 | } |
399 | ||
b32b8144 FG |
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 | } | |
7c673cae FG |
417 | |
418 | // LCM tests | |
419 | ||
420 | // LCM on signed integer types | |
421 | template< class T > void lcm_int_test() // signed_test_types | |
422 | { | |
b32b8144 | 423 | #ifndef BOOST_MSVC |
7c673cae | 424 | using boost::integer::lcm; |
b32b8144 FG |
425 | using boost::integer::lcm_evaluator; |
426 | #else | |
427 | using namespace boost::integer; | |
428 | #endif | |
7c673cae FG |
429 | |
430 | // Originally from Boost.Rational tests | |
b32b8144 FG |
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)); | |
7c673cae FG |
464 | } |
465 | ||
466 | // LCM on unmarked signed integer type | |
467 | void lcm_unmarked_int_test() | |
468 | { | |
b32b8144 | 469 | #ifndef BOOST_MSVC |
7c673cae | 470 | using boost::integer::lcm; |
b32b8144 FG |
471 | #else |
472 | using namespace boost::integer; | |
473 | #endif | |
7c673cae FG |
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. | |
b32b8144 FG |
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) ); | |
7c673cae FG |
495 | } |
496 | ||
497 | // LCM on unsigned integer types | |
498 | template< class T > void lcm_unsigned_test() // unsigned_test_types | |
499 | { | |
b32b8144 | 500 | #ifndef BOOST_MSVC |
7c673cae | 501 | using boost::integer::lcm; |
b32b8144 FG |
502 | #else |
503 | using namespace boost::integer; | |
504 | #endif | |
7c673cae FG |
505 | |
506 | // Note that unmarked types (i.e. have no std::numeric_limits | |
507 | // specialization) are treated like non/unsigned types | |
b32b8144 FG |
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) ); | |
7c673cae FG |
516 | } |
517 | ||
518 | // LCM at compile-time | |
519 | void lcm_static_test() | |
520 | { | |
b32b8144 | 521 | #ifndef BOOST_MSVC |
7c673cae | 522 | using boost::integer::static_lcm; |
b32b8144 FG |
523 | #else |
524 | using namespace boost::integer; | |
525 | #endif | |
7c673cae | 526 | |
b32b8144 FG |
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 ); | |
7c673cae FG |
537 | } |
538 | ||
b32b8144 FG |
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); | |
92f5a8d4 TL |
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 | ||
b32b8144 FG |
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 | } | |
7c673cae | 560 | |
b32b8144 FG |
561 | // Test case from Boost.Rational, need to make sure we don't break the rational lib: |
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 | } | |
7c673cae | 570 | |
b32b8144 FG |
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 | |
7c673cae FG |
581 | #define TEST_SIGNED_( test ) \ |
582 | test<signed char>(); \ | |
583 | test<short>(); \ | |
584 | test<int>(); \ | |
585 | test<long>(); \ | |
586 | test<MyInt1>(); | |
b32b8144 | 587 | #endif |
7c673cae FG |
588 | |
589 | #ifdef BOOST_HAS_LONG_LONG | |
b32b8144 | 590 | # define TEST_SIGNED__( test ) \ |
7c673cae FG |
591 | TEST_SIGNED_( test ) \ |
592 | test<boost::long_long_type>(); | |
593 | #elif defined(BOOST_HAS_MS_INT64) | |
b32b8144 | 594 | # define TEST_SIGNED__( test ) \ |
7c673cae FG |
595 | TEST_SIGNED_( test ) \ |
596 | test<__int64>(); | |
597 | #endif | |
b32b8144 FG |
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 | |
7c673cae FG |
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>(); | |
b32b8144 | 615 | #endif |
7c673cae FG |
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 | ||
b32b8144 FG |
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 | ||
7c673cae FG |
637 | int main() |
638 | { | |
b32b8144 FG |
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(); | |
7c673cae | 653 | } |