Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_GCD_EXTENDED_GCD 00002 #define H_MATH_GCD_EXTENDED_GCD 00003 00008 #include <utility> 00009 #include <limits> 00010 #include "utils/static_assert/static_assert.h" 00011 #include "utils/preconditions/preconditions.h" 00012 00013 00014 namespace math { 00015 namespace gcd { 00016 00020 class ExtendedGCD { 00021 public: 00039 template <typename T> 00040 static std::pair<T, T> extended_gcd_positive(T a, T b) { 00041 STATIC_ASSERT(std::numeric_limits<T>::is_integer, ""); 00042 STATIC_ASSERT(std::numeric_limits<T>::is_signed, ""); 00043 Preconditions::check(a >= 0); 00044 Preconditions::check(b >= 0); 00045 if (a == 0 && b == 0) { 00046 return std::make_pair(0, 0); // special case 00047 } 00048 if (b == 0) { 00049 return std::make_pair(1, 0); 00050 } 00051 std::pair<T, T> tmp = extended_gcd_positive(b, a % b); 00052 //FIXME(nemoze to tu pretiect?) 00053 return std::make_pair(tmp.second, tmp.first - tmp.second * (a / b)); 00054 } 00055 00073 template <typename T> 00074 static std::pair<T, T> extended_gcd(T a, T b) { 00075 STATIC_ASSERT(std::numeric_limits<T>::is_integer, ""); 00076 STATIC_ASSERT(std::numeric_limits<T>::is_signed, ""); 00077 if (a < 0) { 00078 if (a == std::numeric_limits<T>::min()) { 00079 throw std::overflow_error("Overflow in GCD computation."); 00080 } 00081 std::pair<T, T> tmp = extended_gcd(-a, b); 00082 return std::make_pair(-tmp.first, tmp.second); 00083 } 00084 if (b < 0) { 00085 if (b == std::numeric_limits<T>::min()) { 00086 throw std::overflow_error("Overflow in GCD computation."); 00087 } 00088 std::pair<T, T> tmp = extended_gcd(a, -b); 00089 return std::make_pair(tmp.first, -tmp.second); 00090 } 00091 return extended_gcd_positive(a, b); 00092 } 00093 }; 00094 00095 } // namespace gcd 00096 } // namespace math 00097 #endif