Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_GCD_EXTENDED_GCD_LOOP 00002 #define H_MATH_GCD_EXTENDED_GCD_LOOP 00003 00008 #include "utils/static_assert/static_assert.h" 00009 #include "utils/preconditions/preconditions.h" 00010 #include <utility> 00011 00012 namespace math { 00013 namespace gcd { 00014 00018 class ExtendedGCDLoop { 00019 public: 00035 template<typename T> 00036 static std::pair<T, T> extended_gcd_positive(T a, T b) { 00037 STATIC_ASSERT(std::numeric_limits<T>::is_integer, ""); 00038 STATIC_ASSERT(std::numeric_limits<T>::is_signed, ""); 00039 Preconditions::check(a >= 0, "a should be non-negative"); 00040 Preconditions::check(b >= 0, "b should be non-negative"); 00041 00042 if ((a == 0) && (b == 0)) { 00043 return std::make_pair(0, 0); // special case 00044 } 00045 00046 T x = 0; 00047 T lastx = 1; 00048 T y = 1; 00049 T lasty = 0; 00050 00051 while (b) { 00052 T q = a / b; 00053 T tmp; 00054 00055 tmp = b; b = a % b; a = tmp; 00056 00057 tmp = x; x = lastx - q * x; lastx = tmp; 00058 tmp = y; y = lasty - q * y; lasty = tmp; 00059 } 00060 return std::make_pair(lastx, lasty); 00061 } 00062 }; 00063 00064 } // namespace gcd 00065 } // namespace math 00066 #endif