Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/math/gcd/extended_gcd.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines