source: git/libpolys/coeffs/coeffs.h @ 141342

spielwiese
Last change on this file since 141342 was 141342, checked in by Frank Seelisch <seelisch@…>, 12 years ago
nExt replaced by n_algExt and n_transExt
  • Property mode set to 100644
File size: 18.7 KB
Line 
1#ifndef COEFFS_H
2#define COEFFS_H
3/****************************************
4*  Computer Algebra System SINGULAR     *
5****************************************/
6/* $Id$ */
7/*
8* ABSTRACT
9*/
10
11#include <misc/auxiliary.h>
12/* for assume: */
13#include <reporter/reporter.h>
14
15#include <coeffs/si_gmp.h>
16
17#ifdef HAVE_FACTORY
18class CanonicalForm;
19#endif
20
21enum n_coeffType
22{
23  n_unknown=0,
24  n_Zp,
25  n_Q,
26  n_R,
27  n_GF,
28  n_long_R,
29  n_algExt,  /* used for all algebraic extensions, i.e.,
30                the top-most extension in an extension tower
31                is algebraic */
32  n_transExt,  /* used for all transcendental extensions, i.e.,
33                  the top-most extension in an extension tower
34                  is transcendental */
35  n_long_C,
36  // only used if HAVE_RINGS is defined:
37  n_Z,
38  n_Zn,
39  n_Zpn, // does no longer exist?
40  n_Z2m,
41  n_CF
42};
43
44struct snumber;
45typedef struct snumber *   number;
46
47struct snumber;
48typedef struct snumber *   number;
49
50/* standard types */
51#ifdef HAVE_RINGS
52typedef unsigned long NATNUMBER;
53typedef mpz_ptr int_number;
54#endif
55
56struct ip_sring;
57typedef struct ip_sring *         ring;
58
59struct n_Procs_s;
60typedef struct  n_Procs_s  n_Procs_s;
61typedef struct  n_Procs_s  *coeffs;
62
63typedef number (*numberfunc)(number a, number b, const coeffs r);
64
65/// maps "a", which lives in src, into dst
66typedef number (*nMapFunc)(number a, const coeffs src, const coeffs dst);
67
68struct n_Procs_s
69{
70   coeffs next;
71   unsigned int ringtype;  /* =0 => coefficient field,
72                             !=0 => coeffs from one of the rings */
73
74   // general properties:
75   /// TRUE, if nNew/nDelete/nCopy are dummies
76   BOOLEAN has_simple_Alloc;
77   /// TRUE, if std should make polynomials monic (if nInvers is cheap)
78   /// if false, then a gcd routine is used for a content computation
79   BOOLEAN has_simple_Inverse;
80
81   // tests for numbers.cc:
82   BOOLEAN (*nCoeffIsEqual)(const coeffs r, n_coeffType n, void * parameter);
83
84   /// output of coeff description via Print
85   void (*cfCoeffWrite)(const coeffs r);
86
87   // the union stuff
88
89   // Zp:
90   int npPrimeM;
91   int npPminus1M;
92   #ifdef HAVE_DIV_MOD
93   unsigned short *npInvTable;
94   #endif
95   #if !defined(HAVE_DIV_MOD) || !defined(HAVE_MULT_MOD)
96   unsigned short *npExpTable;
97   unsigned short *npLogTable;
98   #endif
99
100   // ?
101   // initialisation:
102   //void (*cfInitChar)(coeffs r, int parameter); // do one-time initialisations
103   void (*cfKillChar)(coeffs r); //  undo all initialisations
104                                // or NULL
105   void (*cfSetChar)(const coeffs r); // initialisations after each ring change
106                                // or NULL
107   // general stuff
108   numberfunc cfMult, cfSub ,cfAdd ,cfDiv, cfIntDiv, cfIntMod, cfExactDiv;
109   /// init with an integer
110   number  (*cfInit)(int i,const coeffs r);
111   number  (*cfPar)(int i, const coeffs r);
112   int     (*cfParDeg)(number n, const coeffs r);
113   /// how complicated, (0) => 0, or positive
114   int     (*cfSize)(number n, const coeffs r);
115   /// convertion, 0 if impossible
116   int     (*cfInt)(number &n, const coeffs r);
117
118#ifdef HAVE_RINGS
119   int     (*cfDivComp)(number a,number b,const coeffs r);
120   BOOLEAN (*cfIsUnit)(number a,const coeffs r);
121   number  (*cfGetUnit)(number a,const coeffs r);
122   number  (*cfExtGcd)(number a, number b, number *s, number *t,const coeffs r);
123#endif
124
125   /// changes argument  inline: a:= -a
126   number  (*cfNeg)(number a, const coeffs r);
127   /// return 1/a
128   number  (*cfInvers)(number a, const coeffs r);
129   /// return a copy of a
130   number  (*cfCopy)(number a, const coeffs r);
131   number  (*cfRePart)(number a, const coeffs r);
132   number  (*cfImPart)(number a, const coeffs r);
133   void    (*cfWrite)(number &a, const coeffs r);
134   const char *  (*cfRead)(const char * s, number * a, const coeffs r);
135   void    (*cfNormalize)(number &a, const coeffs r);
136   BOOLEAN (*cfGreater)(number a,number b, const coeffs r),
137#ifdef HAVE_RINGS
138           (*cfDivBy)(number a, number b, const coeffs r),
139#endif
140            /// tests
141           (*cfEqual)(number a,number b, const coeffs r),
142           (*cfIsZero)(number a, const coeffs r),
143           (*cfIsOne)(number a, const coeffs r),
144           (*cfIsMOne)(number a, const coeffs r),
145           (*cfGreaterZero)(number a, const coeffs r);
146
147   void    (*cfPower)(number a, int i, number * result, const coeffs r);
148   number  (*cfGetDenom)(number &n, const coeffs r);
149   number  (*cfGetNumerator)(number &n, const coeffs r);
150   number  (*cfGcd)(number a, number b, const coeffs r);
151   number  (*cfLcm)(number a, number b, const coeffs r);
152   void    (*cfDelete)(number * a, const coeffs r);
153   nMapFunc (*cfSetMap)(const coeffs src, const coeffs dst);
154
155   /// For extensions (writes into global string buffer)
156   char *  (*cfName)(number n, const coeffs r);
157
158   /// Inplace: a *= b
159   void    (*cfInpMult)(number &a, number b, const coeffs r);
160   /// maps the bigint i (from dummy) into the coeffs dst
161   number  (*cfInit_bigint)(number i, const coeffs dummy, const coeffs dst);
162
163#ifdef HAVE_FACTORY
164   number (*convFactoryNSingN)( const CanonicalForm n, const coeffs r);
165   CanonicalForm (*convSingNFactoryN)( number n, BOOLEAN setChar, const coeffs r );
166#endif
167
168
169#ifdef LDEBUG
170   /// Test: is "a" a correct number?
171   BOOLEAN (*cfDBTest)(number a, const char *f, const int l, const coeffs r);
172#endif
173
174   number nNULL; /* the 0 as constant */
175   int     char_flag;
176   int     ref;
177   n_coeffType type;
178//-------------------------------------------
179
180  /// For Zp_a, Q_a we need polynomials (due to polys)
181  ring          algring; //< implementation of extensions needs polynomials...
182  /// for Q_a/Zp_a, rInit
183  ///number     minpoly;  //< no longer needed: replaced by
184                          //  algring->minideal->[0]
185
186
187//-------------------------------------------
188  char* complex_parameter; //< the name of sqrt(-1), i.e. 'i' or 'j' etc...?
189
190#ifdef HAVE_RINGS
191  /* The following members are for representing the ring Z/n,
192     where n is not a prime. We distinguish four cases:
193     1.) n has at least two distinct prime factors. Then
194         modBase stores n, modExponent stores 1, modNumber
195         stores n, and mod2mMask is not used;
196     2.) n = p^k for some odd prime p and k > 1. Then
197         modBase stores p, modExponent stores k, modNumber
198         stores n, and mod2mMask is not used;
199     3.) n = 2^k for some k > 1; moreover, 2^k - 1 fits in
200         an unsigned long. Then modBase stores 2, modExponent
201         stores k, modNumber is not used, and mod2mMask stores
202         2^k - 1, i.e., the bit mask '111..1' of length k.
203     4.) n = 2^k for some k > 1; but 2^k - 1 does not fit in
204         an unsigned long. Then modBase stores 2, modExponent
205         stores k, modNumber stores n, and mod2mMask is not
206         used;
207     Cases 1.), 2.), and 4.) are covered by the implementation
208     in the files rmodulon.h and rmodulon.cc, whereas case 3.)
209     is implemented in the files rmodulo2m.h and rmodulo2m.cc. */
210  int_number    modBase;
211  unsigned long modExponent;
212  int_number    modNumber;
213  unsigned long mod2mMask;
214#endif
215  int        ch;  /* characteristic, rInit */
216
217  short      float_len; /* additional char-flags, rInit */
218  short      float_len2; /* additional char-flags, rInit */
219
220  BOOLEAN   ShortOut; /// ffields need this.
221
222// ---------------------------------------------------
223  // for n_GF
224
225  int m_nfCharQ;  ///< the number of elemts: q
226  int m_nfM1;       ///< representation of -1
227  int m_nfCharP;  ///< the characteristic: p
228  int m_nfCharQ1; ///< q-1
229  unsigned short *m_nfPlus1Table;
230  int *m_nfMinPoly;
231  char * m_nfParameter;
232};
233//
234// test properties and type
235/// Returns the type of coeffs domain
236static inline n_coeffType getCoeffType(const coeffs r)
237{
238  assume(r != NULL);
239  return r->type;
240}
241
242static inline int nInternalChar(const coeffs r)
243{
244  assume(r != NULL);
245  return r->ch;
246}
247
248/// one-time initialisations for new coeffs
249/// in case of an error return NULL
250coeffs nInitChar(n_coeffType t, void * parameter);
251
252/// undo all initialisations
253void nKillChar(coeffs r);
254
255/// initialisations after each ring change
256static inline void nSetChar(const coeffs r)
257{
258  assume(r!=NULL); // r==NULL is an error
259  if (r->cfSetChar!=NULL) r->cfSetChar(r);
260}
261
262void           nNew(number * a);
263#define n_New(n, r)           nNew(n)
264
265
266// the access methods (part 2):
267
268/// return a copy of a
269static inline number n_Copy(number n,    const coeffs r)
270{   assume(r != NULL); assume(r->cfCopy!=NULL); return r->cfCopy(n, r); }
271
272static inline void   n_Delete(number* p, const coeffs r)
273{   assume(r != NULL); assume(r->cfDelete!= NULL); r->cfDelete(p, r); }
274
275static inline BOOLEAN n_Equal(number a, number b, const coeffs r)
276{ assume(r != NULL); assume(r->cfEqual!=NULL); return r->cfEqual(a, b, r); }
277
278static inline BOOLEAN n_IsZero(number n, const coeffs r)
279{ assume(r != NULL); assume(r->cfIsZero!=NULL); return r->cfIsZero(n,r); }
280
281static inline BOOLEAN n_IsOne(number n,  const coeffs r)
282{ assume(r != NULL); assume(r->cfIsOne!=NULL); return r->cfIsOne(n,r); }
283
284static inline BOOLEAN n_IsMOne(number n, const coeffs r)
285{ assume(r != NULL); assume(r->cfIsMOne!=NULL); return r->cfIsMOne(n,r); }
286
287static inline BOOLEAN n_GreaterZero(number n, const coeffs r)
288{ assume(r != NULL); assume(r->cfGreaterZero!=NULL); return r->cfGreaterZero(n,r); }
289static inline BOOLEAN n_Greater(number a, number b, const coeffs r)
290{ assume(r != NULL); assume(r->cfGreater!=NULL); return r->cfGreater(a,b,r); }
291
292#ifdef HAVE_RINGS
293static inline BOOLEAN n_IsUnit(number n, const coeffs r)
294{ assume(r != NULL); assume(r->cfIsUnit!=NULL); return r->cfIsUnit(n,r); }
295
296static inline number n_GetUnit(number n, const coeffs r)
297{ assume(r != NULL); assume(r->cfGetUnit!=NULL); return r->cfGetUnit(n,r); }
298
299static inline BOOLEAN n_DivBy(number a, number b, const coeffs r)
300{ assume(r != NULL); assume(r->cfDivBy!=NULL); return r->cfDivBy(a,b,r); }
301#endif
302
303/// init with an integer
304static inline number n_Init(int i,       const coeffs r)
305{ assume(r != NULL); assume(r->cfInit!=NULL); return r->cfInit(i,r); }
306
307/// conversion to int; 0 if not possible
308static inline int n_Int(number n,        const coeffs r)
309{ assume(r != NULL); assume(r->cfInt!=NULL); return r->cfInt(n,r); }
310
311/// changes argument  inline: a:= -a
312static inline number n_Neg(number n,     const coeffs r)
313{ assume(r != NULL); assume(r->cfNeg!=NULL); return r->cfNeg(n,r); }
314
315/// return 1/a
316static inline number n_Invers(number a,  const coeffs r)
317{ assume(r != NULL); assume(r->cfInvers!=NULL); return r->cfInvers(a,r); }
318
319/// use for pivot strategies, (0) => 0, otherwise positive
320static inline int    n_Size(number n,    const coeffs r)
321{ assume(r != NULL); assume(r->cfSize!=NULL); return r->cfSize(n,r); }
322
323/// normalize the number. i.e. go to some canonnical representation (inplace)
324static inline void   n_Normalize(number& n, const coeffs r)
325{ assume(r != NULL); assume(r->cfNormalize!=NULL); r->cfNormalize(n,r); }
326
327/// Normalize and Write to the output buffer of reporter
328static inline void   n_Write(number& n,  const coeffs r)
329{ assume(r != NULL); assume(r->cfWrite!=NULL); r->cfWrite(n,r); }
330
331/// Normalize and get denomerator
332static inline number n_GetDenom(number& n, const coeffs r)
333{ assume(r != NULL); assume(r->cfGetDenom!=NULL); return r->cfGetDenom(n, r); }
334
335/// Normalize and get numerator
336static inline number n_GetNumerator(number& n, const coeffs r)
337{ assume(r != NULL); assume(r->cfGetNumerator!=NULL); return r->cfGetNumerator(n, r); }
338
339static inline void   n_Power(number a, int b, number *res, const coeffs r)
340{ assume(r != NULL); assume(r->cfPower!=NULL); r->cfPower(a,b,res,r); }
341
342static inline number n_Mult(number a, number b, const coeffs r)
343{ assume(r != NULL); assume(r->cfMult!=NULL); return r->cfMult(a, b, r); }
344
345/// Inplace multiplication: a := a * b
346static inline void n_InpMult(number &a, number b, const coeffs r)
347{ assume(r != NULL); assume(r->cfInpMult!=NULL); r->cfInpMult(a,b,r); }
348
349static inline number n_Sub(number a, number b, const coeffs r)
350{ assume(r != NULL); assume(r->cfSub!=NULL); return r->cfSub(a, b, r); }
351
352static inline number n_Add(number a, number b, const coeffs r)
353{ assume(r != NULL); assume(r->cfAdd!=NULL); return r->cfAdd(a, b, r); }
354
355static inline number n_Div(number a, number b, const coeffs r)
356{ assume(r != NULL); assume(r->cfDiv!=NULL); return r->cfDiv(a,b,r); }
357
358static inline number n_IntDiv(number a, number b, const coeffs r)
359{ assume(r != NULL); assume(r->cfIntDiv!=NULL); return r->cfIntDiv(a,b,r); }
360
361static inline number n_ExactDiv(number a, number b, const coeffs r)
362{ assume(r != NULL); assume(r->cfExactDiv!=NULL); return r->cfExactDiv(a,b,r); }
363
364static inline number n_Gcd(number a, number b, const coeffs r)
365{ assume(r != NULL); assume(r->cfGcd!=NULL); return r->cfGcd(a,b,r); }
366
367static inline number n_Lcm(number a, number b, const coeffs r)
368{ assume(r != NULL); assume(r->cfLcm!=NULL); return r->cfLcm(a,b,r); }
369
370static inline nMapFunc n_SetMap(const coeffs src, const coeffs dst)
371{ assume(src != NULL && dst != NULL); assume(dst->cfSetMap!=NULL); return dst->cfSetMap(src,dst); }
372
373static inline number n_Par(int n, const coeffs r)
374{ assume(r != NULL); assume(r->cfPar!=NULL); return r->cfPar(n,r); }
375
376static inline int n_ParDeg(number n, const coeffs r)
377{ assume(r != NULL); assume(r->cfParDeg!=NULL); return r->cfParDeg(n,r); }
378
379/// Tests whether n is a correct number: only used if LDEBUG is defined
380static inline BOOLEAN n_DBTest(number n, const char *filename, const int linenumber, const coeffs r)
381{
382  assume(r != NULL); 
383#ifdef LDEBUG
384  assume(r->cfDBTest != NULL); 
385  return r->cfDBTest(n, filename, linenumber, r);
386#else
387  return TRUE;
388#endif
389}
390
391/// output the coeff description
392static inline void   n_CoeffWrite(const coeffs r)
393{ assume(r != NULL); assume(r->cfCoeffWrite != NULL); r->cfCoeffWrite(r); }
394
395// Tests:
396static inline BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
397{ assume(r != NULL); return (r->ringtype == 1); }
398
399static inline BOOLEAN nCoeff_is_Ring_ModN(const coeffs r)
400{ assume(r != NULL); return (r->ringtype == 2); }
401
402static inline BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
403{ assume(r != NULL); return (r->ringtype == 3); }
404
405static inline BOOLEAN nCoeff_is_Ring_Z(const coeffs r)
406{ assume(r != NULL); return (r->ringtype == 4); }
407
408static inline BOOLEAN nCoeff_is_Ring(const coeffs r)
409{ assume(r != NULL); return (r->ringtype != 0); }
410
411/// returns TRUE, if r is not a field and r has no zero divisors (i.e is a domain)
412static inline BOOLEAN nCoeff_is_Domain(const coeffs r)
413{
414  assume(r != NULL); 
415#ifdef HAVE_RINGS
416  return (r->ringtype == 4 || r->ringtype == 0);
417#else
418  return TRUE;
419#endif
420}
421
422/// returns TRUE, if r is not a field and r has non-trivial units
423static inline BOOLEAN nCoeff_has_Units(const coeffs r)
424{ assume(r != NULL); return ((r->ringtype == 1) || (r->ringtype == 2) || (r->ringtype == 3)); }
425
426static inline BOOLEAN nCoeff_is_Zp(const coeffs r)
427{ assume(r != NULL); return getCoeffType(r)==n_Zp; }
428
429static inline BOOLEAN nCoeff_is_Zp(const coeffs r, int p)
430{ assume(r != NULL); return (getCoeffType(r)  && (r->ch == ABS(p))); }
431
432static inline BOOLEAN nCoeff_is_Q(const coeffs r)
433{ assume(r != NULL); return getCoeffType(r)==n_Q; }
434
435static inline BOOLEAN nCoeff_is_numeric(const coeffs r) /* R, long R, long C */
436{ assume(r != NULL);  return (getCoeffType(r)==n_R) || (getCoeffType(r)==n_long_R) || (getCoeffType(r)==n_long_C); }
437// (r->ringtype == 0) && (r->ch ==  -1); ??
438
439
440static inline BOOLEAN nCoeff_is_R(const coeffs r)
441{ assume(r != NULL); return getCoeffType(r)==n_R; }
442
443static inline BOOLEAN nCoeff_is_GF(const coeffs r)
444{ assume(r != NULL); return getCoeffType(r)==n_GF; }
445
446static inline BOOLEAN nCoeff_is_GF(const coeffs r, int q)
447{ assume(r != NULL); return (getCoeffType(r)==n_GF) && (r->ch == q); }
448
449/* TRUE iff an extension tower is build upon some Zp, i.e., the bottom
450   field in this tower is Zp */
451static inline BOOLEAN nCoeff_is_Zp_a(const coeffs r)
452{
453  assume(r != NULL);
454printf("###### %d, %d\n", r->ringtype, r->ch);
455printf("###### %d, %d, %d\n", getCoeffType(r), n_algExt, n_transExt);
456  return (r->ringtype == 0) &&
457         ((getCoeffType(r)==n_algExt) || (getCoeffType(r)==n_transExt)) &&
458         (r->ch < -1);
459}
460
461/* TRUE iff an extension tower is build upon Zp (p as provided), i.e.,
462   the bottom field in this tower is Zp */
463static inline BOOLEAN nCoeff_is_Zp_a(const coeffs r, int p)
464{
465  assume(r != NULL);
466  return (r->ringtype == 0) &&
467         ((getCoeffType(r)==n_algExt) || (getCoeffType(r)==n_transExt)) &&
468         (r->ch < -1 ) && (-(r->ch) == p);
469}
470
471/* TRUE iff an extension tower is build upon Q, i.e.,
472   the bottom field in this tower is Q */
473static inline BOOLEAN nCoeff_is_Q_a(const coeffs r)
474{
475  assume(r != NULL);
476  return (r->ringtype == 0) &&
477         ((getCoeffType(r)==n_algExt) || (getCoeffType(r)==n_transExt)) &&
478         (r->ch == 0);
479}
480
481static inline BOOLEAN nCoeff_is_long_R(const coeffs r)
482{ assume(r != NULL); return getCoeffType(r)==n_long_R; }
483
484static inline BOOLEAN nCoeff_is_long_C(const coeffs r)
485{ assume(r != NULL); return getCoeffType(r)==n_long_C; }
486
487static inline BOOLEAN nCoeff_is_CF(const coeffs r)
488{ assume(r != NULL); return getCoeffType(r)==n_CF; }
489
490/// TRUE, if the computation of the inverse is fast (i.e. prefer leading coeff. 1 over content)
491static inline BOOLEAN nCoeff_has_simple_inverse(const coeffs r)
492{ assume(r != NULL); return r->has_simple_Inverse; }
493/* Z/2^n, Z/p, GF(p,n), R, long_R, long_C*/
494// /* { return (r->ch>1) || (r->ch== -1); } *//* Z/p, GF(p,n), R, long_R, long_C*/
495// #ifdef HAVE_RINGS
496// { return (r->ringtype > 0) || (r->ch>1) || ((r->ch== -1) && (r->float_len < 10)); } /* Z/2^n, Z/p, GF(p,n), R, long_R, long_C*/
497// #else
498// { return (r->ch>1) || ((r->ch== -1) && (r->float_len < 10)); } /* Z/p, GF(p,n), R, long_R, long_C*/
499// #endif
500
501
502
503/// TRUE if n_Delete/n_New are empty operations
504static inline BOOLEAN nCoeff_has_simple_Alloc(const coeffs r)
505{ assume(r != NULL); return r->has_simple_Alloc; }
506/* Z/p, GF(p,n), R, Ring_2toM: nCopy, nNew, nDelete are dummies*/
507// return (rField_is_Zp(r)
508//         || rField_is_GF(r)
509// #ifdef HAVE_RINGS
510//             || rField_is_Ring_2toM(r)
511// #endif
512//             || rField_is_R(r)); }
513
514/* TRUE iff r represents an algebraic or transcendental extension field */
515static inline BOOLEAN nCoeff_is_Extension(const coeffs r)
516{
517  assume(r != NULL);
518  return (getCoeffType(r)==n_algExt) || (getCoeffType(r)==n_transExt);
519}
520
521/* TRUE iff r represents an algebraic extension field */
522static inline BOOLEAN nCoeff_is_algExt(const coeffs r)
523{ assume(r != NULL); return (getCoeffType(r)==n_algExt); }
524
525/* TRUE iff r represents a transcendental extension field */
526static inline BOOLEAN nCoeff_is_transExt(const coeffs r)
527{ assume(r != NULL); return (getCoeffType(r)==n_transExt); }
528
529/// BOOLEAN n_Test(number a, const coeffs r)
530#define n_Test(a,r)  n_DBTest(a, __FILE__, __LINE__, r)
531
532// Missing wrappers for:
533// cfIntMod, cfRePart, cfImPart, cfRead, cfName, cfInit_bigint
534// HAVE_RINGS: cfDivComp, cfExtGcd... cfDivBy
535
536
537// Deprecated:
538static inline int n_GetChar(const coeffs r)
539{ assume(r != NULL); return nInternalChar(r); }
540
541#endif
542
Note: See TracBrowser for help on using the repository browser.