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