1 /* 2 * (C) Copyright Nick Thompson 2018. 3 * Use, modification and distribution are subject to the 4 * Boost Software License, Version 1.0. (See accompanying file 5 * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 */ 7 8 #include "multiprecision_config.hpp" 9 10 #ifndef DISABLE_MP_TESTS 11 #include <boost/integer/extended_euclidean.hpp> 12 #include <boost/cstdint.hpp> 13 #include <boost/core/lightweight_test.hpp> 14 #include <boost/multiprecision/cpp_int.hpp> 15 #include <boost/integer/common_factor.hpp> 16 17 using boost::multiprecision::int128_t; 18 using boost::multiprecision::int256_t; 19 using boost::integer::extended_euclidean; 20 using boost::integer::gcd; 21 22 template<class Z> test_extended_euclidean()23void test_extended_euclidean() 24 { 25 // Stress test: 26 //Z max_arg = std::numeric_limits<Z>::max(); 27 Z max_arg = 500; 28 for (Z m = max_arg; m > 0; --m) 29 { 30 for (Z n = max_arg; n > 0; --n) 31 { 32 boost::integer::euclidean_result_t<Z> u = extended_euclidean(m, n); 33 int256_t gcdmn = gcd(m, n); 34 int256_t x = u.x; 35 int256_t y = u.y; 36 BOOST_TEST_EQ(u.gcd, gcdmn); 37 BOOST_TEST_EQ(m*x + n*y, gcdmn); 38 } 39 } 40 } 41 42 43 main()44int main() 45 { 46 test_extended_euclidean<boost::int16_t>(); 47 test_extended_euclidean<boost::int32_t>(); 48 test_extended_euclidean<boost::int64_t>(); 49 test_extended_euclidean<int128_t>(); 50 51 return boost::report_errors();; 52 } 53 #else main()54int main() 55 { 56 return 0; 57 } 58 #endif 59