Arageli: gcd.hpp Source File

00001 /*****************************************************************************
00002     
00003     gcd.hpp -- GCD, LCM and relative implementation.
00004 
00005     This file is a part of Arageli library.
00006 
00007     Some functions in this file are part of Anna Bestaeva degree work 2006.
00008     They have been integrated into Arageli by Sergey Lyalin.
00009 
00010     Copyright (C) Nikolai Yu. Zolotykh, 1999--2006
00011     Copyright (C) Anna Bestaeva, 2006
00012 
00013     University of Nizhni Novgorod, Russia
00014 
00015 *****************************************************************************/
00016 
00017 #ifndef _ARAGELI_gcd_hpp_
00018 #define _ARAGELI_gcd_hpp_
00019 
00020 #include "config.hpp"
00021 #include "type_traits.hpp"
00022 #include "factory.hpp"
00023 #include "cmp.hpp"
00024 #include "vector.hpp"
00025 
00026 #include "std_import.hpp"
00027 
00028 
00029 namespace Arageli
00030 {
00031 
00032 // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
00034 
00036 
00038 
00039 template <typename T, typename T_factory>
00040 T euclid (T a, T b, const T_factory& tfctr);
00041 
00042 
00044 template <typename T>
00045 inline T euclid (const T& a, const T& b)
00046 { return euclid(a, b, factory<T>()); }
00047 
00048 
00050 
00051 template <typename T, typename T_factory>
00052 T euclid_binary (T a, T b, const T_factory& tfctr);
00053 
00054 
00056 template <typename T>
00057 inline T euclid_binary (const T& a, const T& b)
00058 { return euclid_binary(a, b, factory<T>()); }
00059 
00060 
00062 
00064 template <typename T, bool REFCNT, typename T_factory, typename T1, bool REFCNT1>
00065 vector<T, REFCNT> euclid
00066 (
00067     const vector<T, REFCNT>& a,
00068     const vector<T1, REFCNT1>& b,
00069     const T_factory& tfctr
00070 );
00071 
00072 
00074 template <typename T, bool REFCNT, typename T1, bool REFCNT1>
00075 inline vector<T, REFCNT> euclid
00076 (
00077     const vector<T, REFCNT>& a,
00078     const vector<T1, REFCNT1>& b
00079 )
00080 { return euclid(a, b, factory<T>()); }
00081 
00082 
00084 /*  Function returns the greatest common divisor
00085     of two integers a and b and returns Bezout's coefficients 
00086     u and v such that gcd = a * u + b * v. */
00087 template <typename T, typename T_factory>
00088 T euclid_bezout
00089 (
00090     const T& a, const T& b, T& u, T& v,
00091     const T_factory& tfctr
00092 );
00093 
00094 
00096 /*  Function returns the greatest common divisor
00097     of two integers a and b and returns Bezout's coefficients 
00098     u and v such that gcd = a * u + b * v. */
00099 template <typename T>
00100 inline T euclid_bezout (const T& a, const T& b, T& u, T& v)
00101 { return euclid_bezout(a, b, u, v, factory<T>()); }
00102 
00104 
00105 
00106 // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
00108 
00110 
00111 template <typename T, typename T_factory>
00112 inline T gcd (const T& a, const T& b, const T_factory& tfctr, const type_category::type&)
00113 { return euclid(a, b, tfctr); }
00114 
00115 template <typename T, typename T_factory>
00116 inline T gcd (const T& a, const T& b, const T_factory& tfctr, const type_category::integer&)
00117 { return euclid/*_binary*/(a, b, tfctr); }
00118 
00120 template <typename T, typename T_factory>
00121 inline T gcd (const T& a, const T& b, const T_factory& tfctr)
00122 { return gcd(a, b, tfctr, type_traits<T>::category_value); }
00123 
00125 template <typename T>
00126 inline T gcd (const T& a, const T& b)
00127 { return gcd(a, b, factory<T>()); }
00128 
00130 template <typename T1, typename T2>
00131 inline T1 gcd (const T1& a, const T2& b)
00132 { return gcd(a, T1(b)); }
00133 
00135 template <typename T, bool REFCNT, typename T_factory>
00136 T gcd (const vector<T, REFCNT>& x, const T_factory& tfctr);
00137 
00139 template <typename T, bool REFCNT>
00140 inline T gcd (const vector<T, REFCNT>& x)
00141 { return gcd(x, factory<T>()); }
00142 
00143 
00145 template <typename T>
00146 inline T gcd3 (const T& a, const T& b, const T& c)
00147 { return gcd(gcd(a, b), c); }
00148 
00149 
00151 template <typename T>
00152 T gcdex (const T& a, const T& b, T&u, T& v, T& w, T& z);
00153 
00154 
00155 // TODO: Document it!
00156 template <typename T>
00157 T gcdex (const T& a, const T& b, const T& N, T&u, T& v, T& w, T& z);
00158 
00159 
00161 template
00162 <
00163     typename T, bool REFCNT, typename T_factory,
00164     typename T1, bool REFCNT1
00165 >
00166 vector<T, REFCNT> gcd_vec
00167 (
00168     const vector<T, REFCNT>& a,
00169     const vector<T1, REFCNT1>& b,
00170     const T_factory& tfctr
00171 );
00172 
00173 
00175 template
00176 <
00177     typename T, bool REFCNT, typename T_factory,
00178     typename T1, bool REFCNT1
00179 >
00180 inline vector<T, REFCNT> gcd
00181 (
00182     const vector<T, REFCNT>& a,
00183     const vector<T1, REFCNT1>& b,
00184     const T_factory& tfctr
00185 )
00186 { return gcd_vec(a, b, tfctr); }
00187 
00188 
00190 template <typename T, bool REFCNT, typename T_factory>
00191 inline vector<T, REFCNT> gcd
00192 (
00193     const vector<T, REFCNT>& a,
00194     const vector<T, REFCNT>& b,
00195     const T_factory& tfctr
00196 )
00197 { return gcd_vec(a, b, tfctr); }
00198 
00199 
00201 template <typename T, bool REFCNT, typename T1, bool REFCNT1>
00202 inline vector<T, REFCNT> gcd
00203 (
00204     const vector<T, REFCNT>& a,
00205     const vector<T1, REFCNT1>& b
00206 )
00207 { return gcd(a, b, factory<T>()); }
00208 
00209 
00211 template <typename T, bool REFCNT>
00212 inline vector<T, REFCNT> gcd
00213 (
00214     const vector<T, REFCNT>& a,
00215     const vector<T, REFCNT>& b
00216 )
00217 { return gcd(a, b, factory<T>()); }
00218 
00219 
00221 template <typename T, typename T_factory>
00222 inline T lcm (const T& a, const T& b, const T_factory& tfctr)
00223 { return a*b/gcd(a, b, tfctr); }
00224 
00226 template <typename T>
00227 inline T lcm (const T& a, const T& b)
00228 { return lcm(a, b, factory<T>()); }
00229 
00231 template <typename T, bool REFCNT, typename T_factory>
00232 T lcm (const vector<T, REFCNT>& x, const T_factory& tfctr);
00233 
00235 template <typename T, bool REFCNT>
00236 inline T lcm (const vector<T, REFCNT>& x)
00237 { return lcm(x, factory<T>()); }
00238 
00239 
00241 template
00242 <
00243     typename T, bool REFCNT, typename T_factory,
00244     typename T1, bool REFCNT1
00245 >
00246 vector<T, REFCNT> lcm_vec
00247 (
00248     const vector<T, REFCNT>& a,
00249     const vector<T1, REFCNT1>& b,
00250     const T_factory& tfctr
00251 );
00252 
00253 
00255 template
00256 <
00257     typename T, bool REFCNT, typename T_factory,
00258     typename T1, bool REFCNT1
00259 >
00260 inline vector<T, REFCNT> lcm
00261 (
00262     const vector<T, REFCNT>& a,
00263     const vector<T1, REFCNT1>& b,
00264     const T_factory& tfctr
00265 )
00266 { return lcm_vec(a, b, tfctr); }
00267 
00268 
00270 template <typename T, bool REFCNT, typename T_factory>
00271 inline vector<T, REFCNT> lcm
00272 (
00273     const vector<T, REFCNT>& a,
00274     const vector<T, REFCNT>& b,
00275     const T_factory& tfctr
00276 )
00277 { return lcm_vec(a, b, tfctr); }
00278 
00279 
00281 template <typename T, bool REFCNT, typename T1, bool REFCNT1>
00282 inline vector<T, REFCNT> lcm
00283 (
00284     const vector<T, REFCNT>& a,
00285     const vector<T1, REFCNT1>& b
00286 )
00287 { return lcm(a, b, factory<T>()); }
00288 
00289 
00290 template <typename T, bool REFCNT>
00291 inline vector<T, REFCNT> lcm
00292 (
00293     const vector<T, REFCNT>& a,
00294     const vector<T, REFCNT>& b
00295 )
00296 { return lcm(a, b, factory<T>()); }
00297 
00299 
00300 
00301 // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
00303 
00305 
00307 template <typename T, typename T_factory>
00308 inline bool is_coprime (const T& a, const T& b, const T_factory& tfctr)
00309 { return is_unit(gcd(a, b, tfctr)); }
00310 
00312 template <typename T>
00313 inline bool is_coprime (const T& a, const T& b)
00314 { return is_coprime(a, b, factory<T>()); }
00315 
00317 template <typename T, bool REFCNT, typename T_factory>
00318 inline bool is_coprime (const vector<T, REFCNT>& x, const T_factory& tfctr)
00319 { return is_unit(gcd(x, tfctr)); }
00320 
00322 template <typename T, bool REFCNT>
00323 inline bool is_coprime (const vector<T, REFCNT>& x)
00324 { return is_coprime(x, factory<T>()); }
00325 
00327 
00328 
00329 } // namespace Arageli
00330 
00331 
00332 #ifdef ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE
00333     #define ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_GCD
00334     #include "gcd.cpp"
00335     #undef  ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_GCD
00336 #endif
00337 
00338 
00339 #endif  //  #ifndef _ARAGELI_gcd_hpp_