algebramix: include/algebramix/algebraic.hpp Source File

00001 
00002 /******************************************************************************
00003 * MODULE     : algebraic.hpp
00004 * DESCRIPTION: Algebraic extensions based on a primitive element
00005 * COPYRIGHT  : (C) 2007  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license and comes WITHOUT
00008 * ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
00009 * If you don't have this file, write to the Free Software Foundation, Inc.,
00010 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00011 ******************************************************************************/
00012 
00013 #ifndef __MMX_ALGEBRAIC_HPP
00014 #define __MMX_ALGEBRAIC_HPP
00015 #include <algebramix/algebraic_extension.hpp>
00016 namespace mmx {
00017 #define TMPL_DEF template<typename C, typename Extension=algebraic_extension<C> >
00018 #define TMPL template<typename C, typename Extension>
00019 #define Polynomial polynomial<C>
00020 #define Algebraic algebraic<C,Extension>
00021 #define Element typename Extension::El
00022 TMPL class algebraic;
00023 TMPL class primitive_element;
00024 
00025 /******************************************************************************
00026 * Trivial extensions
00027 ******************************************************************************/
00028 
00029 template<typename FT, typename C, typename Extension>
00030 struct trivial_extension_helper {
00031   static inline Extension ext () {
00032     return Extension (); }
00033   static inline Extension ext (const format<C>& fm) {
00034     return Extension (fm); }
00035 };
00036 
00037 template<typename C, typename Extension>
00038 struct trivial_extension_helper<empty_format,C,Extension> {
00039   static inline Extension ext () {
00040     static Extension ext= Extension (format<C> ());
00041     return ext; }
00042   static inline Extension ext (const format<C>& fm) {
00043     static Extension ext= Extension (format<C> ());
00044     return ext; }
00045 };
00046 
00047 TMPL inline Extension
00048 trivial_extension () {
00049   typedef typename format<C>::FT FT;
00050   return trivial_extension_helper<FT,C,Extension>::ext ();
00051 }
00052 
00053 TMPL inline Extension
00054 trivial_extension (const format<C>& fm) {
00055   typedef typename format<C>::FT FT;
00056   return trivial_extension_helper<FT,C,Extension>::ext (fm);
00057 }
00058 
00059 /******************************************************************************
00060 * The algebraic type
00061 ******************************************************************************/
00062 
00063 TMPL_DEF
00064 class algebraic {
00065 MMX_ALLOCATORS;
00066 public:
00067   Extension ext;
00068   Element p;
00069 public:
00070   inline algebraic ():
00071     ext (trivial_extension<C,Extension> ()) {}
00072   template<typename T> inline algebraic (const T& c):
00073     ext (trivial_extension<C,Extension> (get_format (as<C> (c)))), p (c) {}
00074   inline algebraic (const Extension ext2, const Polynomial& p2):
00075     ext (ext2), p (p2) {}
00076   inline algebraic (const Polynomial& mp):
00077     ext (mp), p (vec<C> (promote (0, CF(mp)), promote (1, CF(mp)))) {}
00078   template<typename X> inline
00079   algebraic (const Polynomial& mp, const X& x):
00080     ext (mp, x), p (vec<C> (promote (0, CF(mp)), promote (1, CF(mp)))) {}
00081   inline algebraic (const Polynomial& mp, const Polynomial& p2):
00082     ext (mp), p (deg (p2) < deg (mp)? p2: rem (p2, mp)) {}
00083   template<typename X> inline
00084   algebraic (const Polynomial& mp, const Polynomial& p2, const X& x):
00085     ext (mp, x), p (deg (p2) < deg (mp)? p2: rem (p2, mp)) {}
00086   template<typename C2, typename Extension2> inline
00087   algebraic (const algebraic<C2,Extension2>& x2):
00088     ext (field (x2)), p (as<Element > (value (x2))) {}
00089 };
00090 
00091 STYPE_TO_TYPE(TMPL,scalar_type,Algebraic,C);
00092 
00093 TMPL inline format<C> CF (const Algebraic& x) { return CF(x.p); }
00094 TMPL inline Extension field (const Algebraic& x) { return x.ext; }
00095 TMPL inline Element value (const Algebraic& x) { return x.p; }
00096 TMPL inline Polynomial field_modulus (const Algebraic& x) { return x.ext.mp; }
00097 
00098 /******************************************************************************
00099 * Basic routines
00100 ******************************************************************************/
00101 
00102 TMPL inline nat hash (const Algebraic& x) {
00103   nat h= hash (value (x));
00104   return (h<<1) ^ (h<<5) ^ (h>>29) ^ hash (field (x)); }
00105 TMPL inline nat exact_hash (const Algebraic& x) {
00106   nat h= exact_hash (value (x));
00107   return (h<<1) ^ (h<<5) ^ (h>>29) ^ exact_hash (field (x)); }
00108 TMPL inline nat hard_hash (const Algebraic& x) {
00109   nat h= hard_hash (value (x));
00110   return (h<<1) ^ (h<<5) ^ (h>>29) ^ hard_hash (field (x)); }
00111 TMPL inline bool exact_eq (const Algebraic& x1, const Algebraic& x2) {
00112   return exact_eq (value (x1), value (x2)) &&
00113          exact_eq (field (x1), field (x2)); }
00114 TMPL inline bool exact_neq (const Algebraic& x1, const Algebraic& x2) {
00115   return !exact_eq (x1, x2); }
00116 TMPL inline bool hard_eq (const Algebraic& x1, const Algebraic& x2) {
00117   return hard_eq (value (x1), value (x2)) &&
00118          hard_eq (field (x1), field (x2)); }
00119 TMPL inline bool hard_neq (const Algebraic& x1, const Algebraic& x2) {
00120   return !hard_eq (x1, x2); }
00121 
00122 TMPL inline bool is_zero (const Algebraic& x) {
00123   return is_zero (field (x), value (x)); }
00124 TMPL inline int sign (const Algebraic& x) {
00125   return sign (field (x), value (x)); }
00126 TMPL inline bool operator == (const Algebraic& x1, const Algebraic& x2) {
00127   return is_zero (x1 - x2); }
00128 TMPL inline bool operator != (const Algebraic& x1, const Algebraic& x2) {
00129   return !is_zero (x1 - x2); }
00130 
00131 EQUAL_INT_SUGAR(TMPL,Algebraic);
00132 EQUAL_SCALAR_SUGAR(TMPL,Algebraic,C);
00133 EQUAL_SCALAR_SUGAR_BIS(TMPL,Algebraic,C);
00134 COMPARE_SUGAR(TMPL,Algebraic);
00135 COMPARE_INT_SUGAR(TMPL,Algebraic);
00136 COMPARE_SCALAR_SUGAR(TMPL,Algebraic,C);
00137 COMPARE_SCALAR_SUGAR_BIS(TMPL,Algebraic,C);
00138 
00139 TMPL syntactic
00140 flatten (const Algebraic& x) {
00141   return apply ("algebraic", flatten (value (x)), flatten (field (x)));
00142 }
00143 
00144 TMPL
00145 struct binary_helper<Algebraic >: public void_binary_helper<Algebraic > {
00146   static inline string short_type_name () {
00147     return "A" * Short_type_name (C); }
00148   static inline generic full_type_name () {
00149     return gen ("Algebraic", Full_type_name (C)); }
00150   static inline generic disassemble (const Algebraic& x) {
00151     return gen_vec (as<generic> (field (x)),
00152                     as<generic> (value (x))); }
00153   static inline Algebraic assemble (const generic& v) {
00154     return Algebraic (as<Extension > (vector_access (v, 0)),
00155                       as<Element > (vector_access (v, 1))); }
00156   static inline void write (const port& out, const Algebraic& p) {
00157     binary_write<Extension > (out, field (p));
00158     binary_write<Element > (out, value (p)); }
00159   static inline Algebraic read (const port& in) {
00160     Extension ext= binary_read<Extension > (in);
00161     Element p= binary_read<Element > (in);
00162     return Algebraic (ext, p); }
00163 };
00164 
00165 /******************************************************************************
00166 * Joining algebraic extensions and minimal annihilators
00167 ******************************************************************************/
00168 
00169 TMPL inline void
00170 upgrade (Algebraic& a1, Algebraic& a2) {
00171   if (hard_neq (field (a1), field (a2))) {
00172     Element p1= value (a1), p2= value (a2);
00173     Extension ext= upgrade (field (a1), field (a2), p1, p2);
00174     a1= Algebraic (ext, p1);
00175     a2= Algebraic (ext, p2);
00176   }
00177 }
00178 
00179 TMPL Algebraic
00180 lcommon (const Algebraic& a1b, const Algebraic& a2b) {
00181   Algebraic a1= a1b, a2= a2b;
00182   upgrade (a1, a2);
00183   return a1;
00184 }
00185 
00186 TMPL Algebraic
00187 rcommon (const Algebraic& a1b, const Algebraic& a2b) {
00188   Algebraic a1= a1b, a2= a2b;
00189   upgrade (a1, a2);
00190   return a2;
00191 }
00192 
00193 TMPL inline Polynomial
00194 annihilator (const Algebraic& a) {
00195   return annihilator (field (a), value (a));
00196 }
00197 
00198 TMPL inline Algebraic
00199 normalize (const Algebraic& a) {
00200   Extension  ext= normalize (field (a), value (a));
00201   Polynomial pri (vec<C> (promote (0, CF(a)), promote (1, CF(a))));
00202   return Algebraic (ext, pri);
00203 }
00204 
00205 /******************************************************************************
00206 * Basic arithmetic
00207 ******************************************************************************/
00208 
00209 TMPL Algebraic
00210 operator + (const Algebraic& x1b, const Algebraic& x2b) {
00211   Algebraic x1= x1b, x2= x2b;
00212   upgrade (x1, x2);
00213   return Algebraic (field (x1), value (x1) + value (x2));
00214 }
00215 
00216 TMPL inline Algebraic
00217 operator + (const Algebraic& x1, const C& x2) {
00218   return Algebraic (field (x1), value (x1) + x2);
00219 }
00220 
00221 TMPL inline Algebraic
00222 operator + (const C& x1, const Algebraic& x2) {
00223   return Algebraic (field (x2), x1 + value (x2));
00224 }
00225 
00226 TMPL inline Algebraic
00227 operator - (const Algebraic& x) {
00228   return Algebraic (field (x), -value (x));
00229 }
00230 
00231 TMPL Algebraic
00232 operator - (const Algebraic& x1b, const Algebraic& x2b) {
00233   Algebraic x1= x1b, x2= x2b;
00234   upgrade (x1, x2);
00235   return Algebraic (field (x1), value (x1) - value (x2));
00236 }
00237 
00238 TMPL inline Algebraic
00239 operator - (const Algebraic& x1, const C& x2) {
00240   return Algebraic (field (x1), value (x1) - x2);
00241 }
00242 
00243 TMPL inline Algebraic
00244 operator - (const C& x1, const Algebraic& x2) {
00245   return Algebraic (field (x2), x1 - value (x2));
00246 }
00247 
00248 TMPL inline Algebraic
00249 square (const Algebraic& x1) {
00250   return Algebraic (field (x1), square (field (x1), value (x1)));
00251 }
00252 
00253 TMPL Algebraic
00254 operator * (const Algebraic& x1b, const Algebraic& x2b) {
00255   Algebraic x1= x1b, x2= x2b;
00256   upgrade (x1, x2);
00257   return Algebraic (field (x1), mul (field (x1), value (x1), value (x2)));
00258 }
00259 
00260 TMPL inline Algebraic
00261 operator * (const Algebraic& x1, const C& x2) {
00262   return Algebraic (field (x1), value (x1) * x2);
00263 }
00264 
00265 TMPL inline Algebraic
00266 operator * (const C& x1, const Algebraic& x2) {
00267   return Algebraic (field (x2), x1 * value (x2));
00268 }
00269 
00270 TMPL inline Algebraic
00271 invert (const Algebraic& x1) {
00272   return Algebraic (field (x1), invert (field (x1), value (x1)));
00273 }
00274 
00275 TMPL Algebraic
00276 operator / (const C& x1, const Algebraic& x2) {
00277   return Algebraic (field (x2), div (field (x2), x1, value (x2)));
00278 }
00279 
00280 TMPL inline Algebraic
00281 operator / (const Algebraic& x1, const C& x2) {
00282   return Algebraic (field (x1), value (x1) / x2);
00283 }
00284 
00285 TMPL inline Algebraic
00286 operator / (const Algebraic& x1b, const Algebraic& x2b) {
00287   Algebraic x1= x1b, x2= x2b;
00288   upgrade (x1, x2);
00289   return Algebraic (field (x1), div (field (x1), value (x1), value (x2)));
00290 }
00291 
00292 ARITH_SCALAR_INT_SUGAR(TMPL,Algebraic);
00293 
00294 /******************************************************************************
00295 * Roots
00296 ******************************************************************************/
00297 
00298 TMPL inline Algebraic
00299 root (const Algebraic& x, const int& p) {
00300   if (p < 0) return 1 / root (x, -p);
00301   ASSERT (p != 0, "cannot take zero-th roots");
00302   Algebraic  y= normalize (x);
00303   Polynomial z (vec<C> (promote (0, CF(x)), promote (1, CF(x))));
00304   return Algebraic (ramify (field (y), p), z);
00305 }
00306 
00307 TMPL inline Algebraic
00308 sqrt (const Algebraic& x) {
00309   return root (x, 2);
00310 }
00311 
00312 #undef TMPL_DEF
00313 #undef TMPL
00314 #undef Polynomial
00315 #undef Algebraic
00316 #undef Element
00317 } // namespace mmx
00318 #endif // __MMX_ALGEBRAIC_HPP