Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members   Examples  

gcd.h

Go to the documentation of this file.
00001 //N.Yu.Zolotykh 1999
00002 //University of Nizhni Novgorod, Russia
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

Generated at Tue Jan 22 20:37:04 2002 for Arageli by doxygen1.2.9.1 written by Dimitri van Heesch, © 1997-2001