00001
00002
00003 #include <stdlib.h>
00004 #include "matrices.h"
00005 #include "powerest.h"
00006
00007 #ifndef GCD_H_
00008 #define GCD_H_
00009
00016
00017
00022
00023 template <class item_class>
00024 item_class gcd(const item_class & a, const item_class & b)
00025 {
00026 item_class r;
00027 item_class u = absolute_value(a);
00028 item_class v = absolute_value(b);
00029 while (v != 0)
00030 {
00031 r = u % v;
00032 u = v;
00033 v = r;
00034 }
00035 return u;
00036 }
00037
00038
00043
00044 template <class T>
00045 T gcd_bezout(const T & a, const T & b, T & u, T & v)
00046 {
00047 u = 1;
00048 T u_new = 0;
00049
00050 v = 0;
00051 T v_new = 1;
00052
00053 T r = a;
00054 T r_new = b;
00055
00056 while (r_new != (T)0)
00057 {
00058 T q = quotient (r, r_new);
00059
00060 T aux = u_new;
00061 u_new = u - q * u_new;
00062 u = aux;
00063
00064 aux = v_new;
00065 v_new = v - q * v_new;
00066 v = aux;
00067
00068 aux = r_new;
00069 r_new = r - q * r_new;
00070 r = aux;
00071 }
00072 return r;
00073 }
00074
00075
00080 template <class item_class>
00081 item_class gcd(const vector<item_class> & v)
00082 {
00083 item_class d = v.at(v.get_n() - 1);
00084 index j = v.get_n() - 2;
00085 while ((d != 1) && (j >= 0))
00086 {
00087 d = gcd(v.at(j), d);
00088 j--;
00089 }
00090 return d;
00091 }
00092
00093 #endif