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