My Project  debian-1:4.1.1-p2+ds-4build1
algext.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /**
5  * ABSTRACT: numbers in an algebraic extension field K[a] / < f(a) >
6  * Assuming that we have a coeffs object cf, then these numbers
7  * are polynomials in the polynomial ring K[a] represented by
8  * cf->extRing.
9  * IMPORTANT ASSUMPTIONS:
10  * 1.) So far we assume that cf->extRing is a valid polynomial
11  * ring in exactly one variable, i.e., K[a], where K is allowed
12  * to be any field (representable in SINGULAR and which may
13  * itself be some extension field, thus allowing for extension
14  * towers).
15  * 2.) Moreover, this implementation assumes that
16  * cf->extRing->qideal is not NULL but an ideal with at
17  * least one non-zero generator which may be accessed by
18  * cf->extRing->qideal->m[0] and which represents the minimal
19  * polynomial f(a) of the extension variable 'a' in K[a].
20  * 3.) As soon as an std method for polynomial rings becomes
21  * availabe, all reduction steps modulo f(a) should be replaced
22  * by a call to std. Moreover, in this situation one can finally
23  * move from K[a] / < f(a) > to
24  * K[a_1, ..., a_s] / I, with I some zero-dimensional ideal
25  * in K[a_1, ..., a_s] given by a lex
26  * Gröbner basis.
27  * The code in algext.h and algext.cc is then capable of
28  * computing in K[a_1, ..., a_s] / I.
29  **/
30 
31 #include "misc/auxiliary.h"
32 
33 #include "omalloc/omalloc.h"
34 
35 #include "reporter/reporter.h"
36 
37 #include "coeffs/coeffs.h"
38 #include "coeffs/numbers.h"
39 #include "coeffs/longrat.h"
40 
41 #include "polys/monomials/ring.h"
43 #include "polys/simpleideals.h"
44 #include "polys/PolyEnumerator.h"
45 
46 #include "factory/factory.h"
47 #include "polys/clapconv.h"
48 #include "polys/clapsing.h"
49 #include "polys/prCopy.h"
50 
52 #define TRANSEXT_PRIVATES 1
54 
55 #ifdef LDEBUG
56 #define naTest(a) naDBTest(a,__FILE__,__LINE__,cf)
57 BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs r);
58 #else
59 #define naTest(a) do {} while (0)
60 #endif
61 
62 /* polynomial ring in which our numbers live */
63 #define naRing cf->extRing
64 
65 /* coeffs object in which the coefficients of our numbers live;
66  * methods attached to naCoeffs may be used to compute with the
67  * coefficients of our numbers, e.g., use naCoeffs->nAdd to add
68  * coefficients of our numbers */
69 #define naCoeffs cf->extRing->cf
70 
71 /* minimal polynomial */
72 #define naMinpoly naRing->qideal->m[0]
73 
74 /// forward declarations
75 BOOLEAN naGreaterZero(number a, const coeffs cf);
76 BOOLEAN naGreater(number a, number b, const coeffs cf);
77 BOOLEAN naEqual(number a, number b, const coeffs cf);
78 BOOLEAN naIsOne(number a, const coeffs cf);
79 BOOLEAN naIsMOne(number a, const coeffs cf);
80 number naInit(long i, const coeffs cf);
81 number naNeg(number a, const coeffs cf);
82 number naInvers(number a, const coeffs cf);
83 number naAdd(number a, number b, const coeffs cf);
84 number naSub(number a, number b, const coeffs cf);
85 number naMult(number a, number b, const coeffs cf);
86 number naDiv(number a, number b, const coeffs cf);
87 void naPower(number a, int exp, number *b, const coeffs cf);
88 number naCopy(number a, const coeffs cf);
89 void naWriteLong(number a, const coeffs cf);
90 void naWriteShort(number a, const coeffs cf);
91 number naGetDenom(number &a, const coeffs cf);
92 number naGetNumerator(number &a, const coeffs cf);
93 number naGcd(number a, number b, const coeffs cf);
94 void naDelete(number *a, const coeffs cf);
95 void naCoeffWrite(const coeffs cf, BOOLEAN details);
96 //number naIntDiv(number a, number b, const coeffs cf);
97 const char * naRead(const char *s, number *a, const coeffs cf);
98 
99 static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param);
100 
101 
102 /// returns NULL if p == NULL, otherwise makes p monic by dividing
103 /// by its leading coefficient (only done if this is not already 1);
104 /// this assumes that we are over a ground field so that division
105 /// is well-defined;
106 /// modifies p
107 // void p_Monic(poly p, const ring r);
108 
109 /// assumes that p and q are univariate polynomials in r,
110 /// mentioning the same variable;
111 /// assumes a global monomial ordering in r;
112 /// assumes that not both p and q are NULL;
113 /// returns the gcd of p and q;
114 /// leaves p and q unmodified
115 // poly p_Gcd(const poly p, const poly q, const ring r);
116 
117 /* returns NULL if p == NULL, otherwise makes p monic by dividing
118  by its leading coefficient (only done if this is not already 1);
119  this assumes that we are over a ground field so that division
120  is well-defined;
121  modifies p */
122 static inline void p_Monic(poly p, const ring r)
123 {
124  if (p == NULL) return;
125  number n = n_Init(1, r->cf);
126  if (p->next==NULL) { p_SetCoeff(p,n,r); return; }
127  poly pp = p;
128  number lc = p_GetCoeff(p, r);
129  if (n_IsOne(lc, r->cf)) return;
130  number lcInverse = n_Invers(lc, r->cf);
131  p_SetCoeff(p, n, r); // destroys old leading coefficient!
132  pIter(p);
133  while (p != NULL)
134  {
135  number n = n_Mult(p_GetCoeff(p, r), lcInverse, r->cf);
136  n_Normalize(n,r->cf);
137  p_SetCoeff(p, n, r); // destroys old leading coefficient!
138  pIter(p);
139  }
140  n_Delete(&lcInverse, r->cf);
141  p = pp;
142 }
143 
144 /// see p_Gcd;
145 /// additional assumption: deg(p) >= deg(q);
146 /// must destroy p and q (unless one of them is returned)
147 static inline poly p_GcdHelper(poly &p, poly &q, const ring r)
148 {
149  while (q != NULL)
150  {
151  p_PolyDiv(p, q, FALSE, r);
152  // swap p and q:
153  poly& t = q;
154  q = p;
155  p = t;
156 
157  }
158  return p;
159 }
160 
161 /* assumes that p and q are univariate polynomials in r,
162  mentioning the same variable;
163  assumes a global monomial ordering in r;
164  assumes that not both p and q are NULL;
165  returns the gcd of p and q;
166  leaves p and q unmodified */
167 static inline poly p_Gcd(const poly p, const poly q, const ring r)
168 {
169  assume((p != NULL) || (q != NULL));
170 
171  poly a = p; poly b = q;
172  if (p_Deg(a, r) < p_Deg(b, r)) { a = q; b = p; }
173  a = p_Copy(a, r); b = p_Copy(b, r);
174 
175  /* We have to make p monic before we return it, so that if the
176  gcd is a unit in the ground field, we will actually return 1. */
177  a = p_GcdHelper(a, b, r);
178  p_Monic(a, r);
179  return a;
180 }
181 
182 /* see p_ExtGcd;
183  additional assumption: deg(p) >= deg(q);
184  must destroy p and q (unless one of them is returned) */
185 static inline poly p_ExtGcdHelper(poly &p, poly &pFactor, poly &q, poly &qFactor,
186  ring r)
187 {
188  if (q == NULL)
189  {
190  qFactor = NULL;
191  pFactor = p_ISet(1, r);
192  p_SetCoeff(pFactor, n_Invers(p_GetCoeff(p, r), r->cf), r);
193  p_Monic(p, r);
194  return p;
195  }
196  else
197  {
198  poly pDivQ = p_PolyDiv(p, q, TRUE, r);
199  poly ppFactor = NULL; poly qqFactor = NULL;
200  poly theGcd = p_ExtGcdHelper(q, qqFactor, p, ppFactor, r);
201  pFactor = ppFactor;
202  qFactor = p_Add_q(qqFactor,
203  p_Neg(p_Mult_q(pDivQ, p_Copy(ppFactor, r), r), r),
204  r);
205  return theGcd;
206  }
207 }
208 
209 
210 /* assumes that p and q are univariate polynomials in r,
211  mentioning the same variable;
212  assumes a global monomial ordering in r;
213  assumes that not both p and q are NULL;
214  returns the gcd of p and q;
215  moreover, afterwards pFactor and qFactor contain appropriate
216  factors such that gcd(p, q) = p * pFactor + q * qFactor;
217  leaves p and q unmodified */
218 poly p_ExtGcd(poly p, poly &pFactor, poly q, poly &qFactor, ring r)
219 {
220  assume((p != NULL) || (q != NULL));
221  poly a = p; poly b = q; BOOLEAN aCorrespondsToP = TRUE;
222  if (p_Deg(a, r) < p_Deg(b, r))
223  { a = q; b = p; aCorrespondsToP = FALSE; }
224  a = p_Copy(a, r); b = p_Copy(b, r);
225  poly aFactor = NULL; poly bFactor = NULL;
226  poly theGcd = p_ExtGcdHelper(a, aFactor, b, bFactor, r);
227  if (aCorrespondsToP) { pFactor = aFactor; qFactor = bFactor; }
228  else { pFactor = bFactor; qFactor = aFactor; }
229  return theGcd;
230 }
231 
232 
233 
234 #ifdef LDEBUG
235 BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs cf)
236 {
237  if (a == NULL) return TRUE;
238  p_Test((poly)a, naRing);
239  if (getCoeffType(cf)==n_algExt)
240  {
241  if((((poly)a)!=naMinpoly)
243  && (p_Totaldegree((poly)a, naRing)> 1)) // allow to output par(1)
244  {
245  dReportError("deg >= deg(minpoly) in %s:%d\n",f,l);
246  return FALSE;
247  }
248  }
249  return TRUE;
250 }
251 #endif
252 
253 void heuristicReduce(poly &p, poly reducer, const coeffs cf);
254 void definiteReduce(poly &p, poly reducer, const coeffs cf);
255 
256 /* returns the bottom field in this field extension tower; if the tower
257  is flat, i.e., if there is no extension, then r itself is returned;
258  as a side-effect, the counter 'height' is filled with the height of
259  the extension tower (in case the tower is flat, 'height' is zero) */
260 static coeffs nCoeff_bottom(const coeffs r, int &height)
261 {
262  assume(r != NULL);
263  coeffs cf = r;
264  height = 0;
265  while (nCoeff_is_Extension(cf))
266  {
267  assume(cf->extRing != NULL); assume(cf->extRing->cf != NULL);
268  cf = cf->extRing->cf;
269  height++;
270  }
271  return cf;
272 }
273 
274 BOOLEAN naIsZero(number a, const coeffs cf)
275 {
276  naTest(a);
277  return (a == NULL);
278 }
279 
280 void naDelete(number * a, const coeffs cf)
281 {
282  if (*a == NULL) return;
283  if (((poly)*a)==naMinpoly) { *a=NULL;return;}
284  poly aAsPoly = (poly)(*a);
285  p_Delete(&aAsPoly, naRing);
286  *a = NULL;
287 }
288 
289 BOOLEAN naEqual(number a, number b, const coeffs cf)
290 {
291  naTest(a); naTest(b);
292  /// simple tests
293  if (a == NULL) return (b == NULL);
294  if (b == NULL) return (a == NULL);
295  return p_EqualPolys((poly)a,(poly)b,naRing);
296 }
297 
298 number naCopy(number a, const coeffs cf)
299 {
300  naTest(a);
301  if (a == NULL) return NULL;
302  if (((poly)a)==naMinpoly) return a;
303  return (number)p_Copy((poly)a, naRing);
304 }
305 
306 number naGetNumerator(number &a, const coeffs cf)
307 {
308  return naCopy(a, cf);
309 }
310 
311 number naGetDenom(number &a, const coeffs cf)
312 {
313  naTest(a);
314  return naInit(1, cf);
315 }
316 
317 BOOLEAN naIsOne(number a, const coeffs cf)
318 {
319  naTest(a);
320  poly aAsPoly = (poly)a;
321  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
322  return n_IsOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
323 }
324 
325 BOOLEAN naIsMOne(number a, const coeffs cf)
326 {
327  naTest(a);
328  poly aAsPoly = (poly)a;
329  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
330  return n_IsMOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
331 }
332 
333 /// this is in-place, modifies a
334 number naNeg(number a, const coeffs cf)
335 {
336  naTest(a);
337  if (a != NULL) a = (number)p_Neg((poly)a, naRing);
338  return a;
339 }
340 
341 number naInit(long i, const coeffs cf)
342 {
343  if (i == 0) return NULL;
344  else return (number)p_ISet(i, naRing);
345 }
346 
347 long naInt(number &a, const coeffs cf)
348 {
349  naTest(a);
350  poly aAsPoly = (poly)a;
351  if(aAsPoly == NULL)
352  return 0;
353  if (!p_IsConstant(aAsPoly, naRing))
354  return 0;
355  assume( aAsPoly != NULL );
356  return n_Int(p_GetCoeff(aAsPoly, naRing), naCoeffs);
357 }
358 
359 /* TRUE iff (a != 0 and (b == 0 or deg(a) > deg(b) or (deg(a)==deg(b) && lc(a)>lc(b))) */
360 BOOLEAN naGreater(number a, number b, const coeffs cf)
361 {
362  naTest(a); naTest(b);
363  if (naIsZero(a, cf))
364  {
365  if (naIsZero(b, cf)) return FALSE;
366  return !n_GreaterZero(pGetCoeff((poly)b),naCoeffs);
367  }
368  if (naIsZero(b, cf))
369  {
370  return n_GreaterZero(pGetCoeff((poly)a),naCoeffs);
371  }
372  int aDeg = p_Totaldegree((poly)a, naRing);
373  int bDeg = p_Totaldegree((poly)b, naRing);
374  if (aDeg>bDeg) return TRUE;
375  if (aDeg<bDeg) return FALSE;
376  return n_Greater(pGetCoeff((poly)a),pGetCoeff((poly)b),naCoeffs);
377 }
378 
379 /* TRUE iff a != 0 and (LC(a) > 0 or deg(a) > 0) */
380 BOOLEAN naGreaterZero(number a, const coeffs cf)
381 {
382  naTest(a);
383  if (a == NULL) return FALSE;
384  if (n_GreaterZero(p_GetCoeff((poly)a, naRing), naCoeffs)) return TRUE;
385  if (p_Totaldegree((poly)a, naRing) > 0) return TRUE;
386  return FALSE;
387 }
388 
389 void naCoeffWrite(const coeffs cf, BOOLEAN details)
390 {
391  assume( cf != NULL );
392 
393  const ring A = cf->extRing;
394 
395  assume( A != NULL );
396  assume( A->cf != NULL );
397 
398  n_CoeffWrite(A->cf, details);
399 
400 // rWrite(A);
401 
402  const int P = rVar(A);
403  assume( P > 0 );
404 
405  PrintS("[");
406 
407  for (int nop=0; nop < P; nop ++)
408  {
409  Print("%s", rRingVar(nop, A));
410  if (nop!=P-1) PrintS(", ");
411  }
412 
413  PrintS("]/(");
414 
415  const ideal I = A->qideal;
416 
417  assume( I != NULL );
418  assume( IDELEMS(I) == 1 );
419 
420 
421  if ( details )
422  {
423  p_Write0( I->m[0], A);
424  PrintS(")");
425  }
426  else
427  PrintS("...)");
428 
429 /*
430  char *x = rRingVar(0, A);
431 
432  Print("// Coefficients live in the extension field K[%s]/<f(%s)>\n", x, x);
433  Print("// with the minimal polynomial f(%s) = %s\n", x,
434  p_String(A->qideal->m[0], A));
435  PrintS("// and K: ");
436 */
437 }
438 
439 number naAdd(number a, number b, const coeffs cf)
440 {
441  naTest(a); naTest(b);
442  if (a == NULL) return naCopy(b, cf);
443  if (b == NULL) return naCopy(a, cf);
444  poly aPlusB = p_Add_q(p_Copy((poly)a, naRing),
445  p_Copy((poly)b, naRing), naRing);
446  //definiteReduce(aPlusB, naMinpoly, cf);
447  return (number)aPlusB;
448 }
449 
450 number naSub(number a, number b, const coeffs cf)
451 {
452  naTest(a); naTest(b);
453  if (b == NULL) return naCopy(a, cf);
454  poly minusB = p_Neg(p_Copy((poly)b, naRing), naRing);
455  if (a == NULL) return (number)minusB;
456  poly aMinusB = p_Add_q(p_Copy((poly)a, naRing), minusB, naRing);
457  //definiteReduce(aMinusB, naMinpoly, cf);
458  return (number)aMinusB;
459 }
460 
461 number naMult(number a, number b, const coeffs cf)
462 {
463  naTest(a); naTest(b);
464  if ((a == NULL)||(b == NULL)) return NULL;
465  poly aTimesB = pp_Mult_qq((poly)a, (poly)b, naRing);
466  definiteReduce(aTimesB, naMinpoly, cf);
467  p_Normalize(aTimesB,naRing);
468  return (number)aTimesB;
469 }
470 
471 number naDiv(number a, number b, const coeffs cf)
472 {
473  naTest(a); naTest(b);
474  if (b == NULL) WerrorS(nDivBy0);
475  if (a == NULL) return NULL;
476  poly bInverse = (poly)naInvers(b, cf);
477  if(bInverse != NULL) // b is non-zero divisor!
478  {
479  poly aDivB = p_Mult_q(p_Copy((poly)a, naRing), bInverse, naRing);
480  definiteReduce(aDivB, naMinpoly, cf);
481  p_Normalize(aDivB,naRing);
482  return (number)aDivB;
483  }
484  return NULL;
485 }
486 
487 /* 0^0 = 0;
488  for |exp| <= 7 compute power by a simple multiplication loop;
489  for |exp| >= 8 compute power along binary presentation of |exp|, e.g.
490  p^13 = p^1 * p^4 * p^8, where we utilise that
491  p^(2^(k+1)) = p^(2^k) * p^(2^k);
492  intermediate reduction modulo the minimal polynomial is controlled by
493  the in-place method heuristicReduce(poly, poly, coeffs); see there.
494 */
495 void naPower(number a, int exp, number *b, const coeffs cf)
496 {
497  naTest(a);
498 
499  /* special cases first */
500  if (a == NULL)
501  {
502  if (exp >= 0) *b = NULL;
503  else WerrorS(nDivBy0);
504  return;
505  }
506  else if (exp == 0) { *b = naInit(1, cf); return; }
507  else if (exp == 1) { *b = naCopy(a, cf); return; }
508  else if (exp == -1) { *b = naInvers(a, cf); return; }
509 
510  int expAbs = exp; if (expAbs < 0) expAbs = -expAbs;
511 
512  /* now compute a^expAbs */
513  poly pow; poly aAsPoly = (poly)a;
514  if (expAbs <= 7)
515  {
516  pow = p_Copy(aAsPoly, naRing);
517  for (int i = 2; i <= expAbs; i++)
518  {
519  pow = p_Mult_q(pow, p_Copy(aAsPoly, naRing), naRing);
521  }
523  }
524  else
525  {
526  pow = p_ISet(1, naRing);
527  poly factor = p_Copy(aAsPoly, naRing);
528  while (expAbs != 0)
529  {
530  if (expAbs & 1)
531  {
534  }
535  expAbs = expAbs / 2;
536  if (expAbs != 0)
537  {
540  }
541  }
544  }
545 
546  /* invert if original exponent was negative */
547  number n = (number)pow;
548  if (exp < 0)
549  {
550  number m = naInvers(n, cf);
551  naDelete(&n, cf);
552  n = m;
553  }
554  *b = n;
555 }
556 
557 /* may reduce p modulo the reducer by calling definiteReduce;
558  the decision is made based on the following heuristic
559  (which should also only be changed here in this method):
560  if (deg(p) > 10*deg(reducer) then perform reduction;
561  modifies p */
562 void heuristicReduce(poly &p, poly reducer, const coeffs cf)
563 {
564  #ifdef LDEBUG
565  p_Test((poly)p, naRing);
566  p_Test((poly)reducer, naRing);
567  #endif
568  if (p_Totaldegree(p, naRing) > 10 * p_Totaldegree(reducer, naRing))
569  definiteReduce(p, reducer, cf);
570 }
571 
572 void naWriteLong(number a, const coeffs cf)
573 {
574  naTest(a);
575  if (a == NULL)
576  StringAppendS("0");
577  else
578  {
579  poly aAsPoly = (poly)a;
580  /* basically, just write aAsPoly using p_Write,
581  but use brackets around the output, if a is not
582  a constant living in naCoeffs = cf->extRing->cf */
583  BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
584  if (useBrackets) StringAppendS("(");
585  p_String0Long(aAsPoly, naRing, naRing);
586  if (useBrackets) StringAppendS(")");
587  }
588 }
589 
590 void naWriteShort(number a, const coeffs cf)
591 {
592  naTest(a);
593  if (a == NULL)
594  StringAppendS("0");
595  else
596  {
597  poly aAsPoly = (poly)a;
598  /* basically, just write aAsPoly using p_Write,
599  but use brackets around the output, if a is not
600  a constant living in naCoeffs = cf->extRing->cf */
601  BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
602  if (useBrackets) StringAppendS("(");
603  p_String0Short(aAsPoly, naRing, naRing);
604  if (useBrackets) StringAppendS(")");
605  }
606 }
607 
608 const char * naRead(const char *s, number *a, const coeffs cf)
609 {
610  poly aAsPoly;
611  const char * result = p_Read(s, aAsPoly, naRing);
612  if (aAsPoly!=NULL) definiteReduce(aAsPoly, naMinpoly, cf);
613  *a = (number)aAsPoly;
614  return result;
615 }
616 
617 #if 0
618 /* implemented by the rule lcm(a, b) = a * b / gcd(a, b) */
619 number naLcm(number a, number b, const coeffs cf)
620 {
621  naTest(a); naTest(b);
622  if (a == NULL) return NULL;
623  if (b == NULL) return NULL;
624  number theProduct = (number)pp_Mult_qq((poly)a, (poly)b, naRing);
625  /* note that theProduct needs not be reduced w.r.t. naMinpoly;
626  but the final division will take care of the necessary reduction */
627  number theGcd = naGcd(a, b, cf);
628  return naDiv(theProduct, theGcd, cf);
629 }
630 #endif
631 number napNormalizeHelper(number b, const coeffs cf)
632 {
633  number h=n_Init(1,naRing->cf);
634  poly bb=(poly)b;
635  number d;
636  while(bb!=NULL)
637  {
638  d=n_NormalizeHelper(h,pGetCoeff(bb), naRing->cf);
639  n_Delete(&h,naRing->cf);
640  h=d;
641  pIter(bb);
642  }
643  return h;
644 }
645 number naLcmContent(number a, number b, const coeffs cf)
646 {
647  if (nCoeff_is_Zp(naRing->cf)) return naCopy(a,cf);
648 #if 0
649  else {
650  number g = ndGcd(a, b, cf);
651  return g;
652  }
653 #else
654  {
655  a=(number)p_Copy((poly)a,naRing);
656  number t=napNormalizeHelper(b,cf);
657  if(!n_IsOne(t,naRing->cf))
658  {
659  number bt, rr;
660  poly xx=(poly)a;
661  while (xx!=NULL)
662  {
663  bt = n_SubringGcd(t, pGetCoeff(xx), naRing->cf);
664  rr = n_Mult(t, pGetCoeff(xx), naRing->cf);
665  n_Delete(&pGetCoeff(xx),naRing->cf);
666  pGetCoeff(xx) = n_Div(rr, bt, naRing->cf);
667  n_Normalize(pGetCoeff(xx),naRing->cf);
668  n_Delete(&bt,naRing->cf);
669  n_Delete(&rr,naRing->cf);
670  pIter(xx);
671  }
672  }
673  n_Delete(&t,naRing->cf);
674  return (number) a;
675  }
676 #endif
677 }
678 
679 /* expects *param to be castable to AlgExtInfo */
680 static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param)
681 {
682  if (n_algExt != n) return FALSE;
683  AlgExtInfo *e = (AlgExtInfo *)param;
684  /* for extension coefficient fields we expect the underlying
685  polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
686  this expectation is based on the assumption that we have properly
687  registered cf and perform reference counting rather than creating
688  multiple copies of the same coefficient field/domain/ring */
689  if (naRing == e->r)
690  return TRUE;
691  /* (Note that then also the minimal ideals will necessarily be
692  the same, as they are attached to the ring.) */
693 
694  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
695  if( rEqual(naRing, e->r, TRUE) ) // also checks the equality of qideals
696  {
697  const ideal mi = naRing->qideal;
698  assume( IDELEMS(mi) == 1 );
699  const ideal ii = e->r->qideal;
700  assume( IDELEMS(ii) == 1 );
701 
702  // TODO: the following should be extended for 2 *equal* rings...
703  assume( p_EqualPolys(mi->m[0], ii->m[0], naRing, e->r) );
704 
705  rDelete(e->r);
706 
707  return TRUE;
708  }
709 
710  return FALSE;
711 
712 }
713 
714 int naSize(number a, const coeffs cf)
715 {
716  if (a == NULL) return 0;
717  poly aAsPoly = (poly)a;
718  int theDegree = 0; int noOfTerms = 0;
719  while (aAsPoly != NULL)
720  {
721  noOfTerms++;
722  int d = p_GetExp(aAsPoly, 1, naRing);
723  if (d > theDegree) theDegree = d;
724  pIter(aAsPoly);
725  }
726  return (theDegree +1) * noOfTerms;
727 }
728 
729 /* performs polynomial division and overrides p by the remainder
730  of division of p by the reducer;
731  modifies p */
732 void definiteReduce(poly &p, poly reducer, const coeffs cf)
733 {
734  #ifdef LDEBUG
735  p_Test((poly)p, naRing);
736  p_Test((poly)reducer, naRing);
737  #endif
738  if ((p!=NULL) && (p_GetExp(p,1,naRing)>=p_GetExp(reducer,1,naRing)))
739  {
740  p_PolyDiv(p, reducer, FALSE, naRing);
741  }
742 }
743 
744 void naNormalize(number &a, const coeffs cf)
745 {
746  poly aa=(poly)a;
747  if (aa!=naMinpoly)
749  a=(number)aa;
750 }
751 
753 {
754  if (n.isZero()) return NULL;
755  poly p=convFactoryPSingP(n,naRing);
756  return (number)p;
757 }
758 CanonicalForm naConvSingNFactoryN( number n, BOOLEAN /*setChar*/, const coeffs cf )
759 {
760  naTest(n);
761  if (n==NULL) return CanonicalForm(0);
762 
763  return convSingPFactoryP((poly)n,naRing);
764 }
765 
766 /* IMPORTANT NOTE: Since an algebraic field extension is again a field,
767  the gcd of two elements is not very interesting. (It
768  is actually any unit in the field, i.e., any non-
769  zero element.) Note that the below method does not operate
770  in this strong sense but rather computes the gcd of
771  two given elements in the underlying polynomial ring. */
772 number naGcd(number a, number b, const coeffs cf)
773 {
774  if (a==NULL) return naCopy(b,cf);
775  if (b==NULL) return naCopy(a,cf);
776 
777  poly ax=(poly)a;
778  poly bx=(poly)b;
779  if (pNext(ax)!=NULL)
780  return (number)p_Copy(ax, naRing);
781  else
782  {
783  if(nCoeff_is_Zp(naRing->cf))
784  return naInit(1,cf);
785  else
786  {
787  number x = n_Copy(pGetCoeff((poly)a),naRing->cf);
788  if (n_IsOne(x,naRing->cf))
789  return (number)p_NSet(x,naRing);
790  while (pNext(ax)!=NULL)
791  {
792  pIter(ax);
793  number y = n_SubringGcd(x, pGetCoeff(ax), naRing->cf);
794  n_Delete(&x,naRing->cf);
795  x = y;
796  if (n_IsOne(x,naRing->cf))
797  return (number)p_NSet(x,naRing);
798  }
799  do
800  {
801  number y = n_SubringGcd(x, pGetCoeff(bx), naRing->cf);
802  n_Delete(&x,naRing->cf);
803  x = y;
804  if (n_IsOne(x,naRing->cf))
805  return (number)p_NSet(x,naRing);
806  pIter(bx);
807  }
808  while (bx!=NULL);
809  return (number)p_NSet(x,naRing);
810  }
811  }
812 #if 0
813  naTest(a); naTest(b);
814  const ring R = naRing;
815  return (number) singclap_gcd(p_Copy((poly)a, R), p_Copy((poly)b, R), R);
816 #endif
817 // return (number)p_Gcd((poly)a, (poly)b, naRing);
818 }
819 
820 number naInvers(number a, const coeffs cf)
821 {
822  naTest(a);
823  if (a == NULL) WerrorS(nDivBy0);
824 
825  poly aFactor = NULL; poly mFactor = NULL; poly theGcd = NULL;
826 // singclap_extgcd!
827  const BOOLEAN ret = singclap_extgcd ((poly)a, naMinpoly, theGcd, aFactor, mFactor, naRing);
828 
829  assume( !ret );
830 
831 // if( ret ) theGcd = p_ExtGcd((poly)a, aFactor, naMinpoly, mFactor, naRing);
832 
833  naTest((number)theGcd); naTest((number)aFactor); naTest((number)mFactor);
834  p_Delete(&mFactor, naRing);
835 
836  // /* the gcd must be 1 since naMinpoly is irreducible and a != NULL: */
837  // assume(naIsOne((number)theGcd, cf));
838 
839  if( !naIsOne((number)theGcd, cf) )
840  {
841  WerrorS("zero divisor found - your minpoly is not irreducible");
842  p_Delete(&aFactor, naRing); aFactor = NULL;
843  }
844  p_Delete(&theGcd, naRing);
845 
846  return (number)(aFactor);
847 }
848 
849 /* assumes that src = Q or Z, dst = Q(a) */
850 number naMap00(number a, const coeffs src, const coeffs dst)
851 {
852  if (n_IsZero(a, src)) return NULL;
853  assume(src->rep == dst->extRing->cf->rep);
854  poly result = p_One(dst->extRing);
855  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
856  return (number)result;
857 }
858 
859 /* assumes that src = Z, dst = K(a) */
860 number naMapZ0(number a, const coeffs src, const coeffs dst)
861 {
862  if (n_IsZero(a, src)) return NULL;
863  poly result = p_One(dst->extRing);
864  nMapFunc nMap=n_SetMap(src,dst->extRing->cf);
865  p_SetCoeff(result, nMap(a, src, dst->extRing->cf), dst->extRing);
866  if (n_IsZero(pGetCoeff(result),dst->extRing->cf))
867  p_Delete(&result,dst->extRing);
868  return (number)result;
869 }
870 
871 /* assumes that src = Z/p, dst = Q(a) */
872 number naMapP0(number a, const coeffs src, const coeffs dst)
873 {
874  if (n_IsZero(a, src)) return NULL;
875  /* mapping via intermediate int: */
876  int n = n_Int(a, src);
877  number q = n_Init(n, dst->extRing->cf);
878  poly result = p_One(dst->extRing);
879  p_SetCoeff(result, q, dst->extRing);
880  return (number)result;
881 }
882 
883 #if 0
884 /* assumes that either src = Q(a), dst = Q(a), or
885  src = Z/p(a), dst = Z/p(a) */
886 number naCopyMap(number a, const coeffs src, const coeffs dst)
887 {
888  return naCopy(a, dst);
889 }
890 #endif
891 
892 number naCopyTrans2AlgExt(number a, const coeffs src, const coeffs dst)
893 {
894  assume (nCoeff_is_transExt (src));
895  assume (nCoeff_is_algExt (dst));
896  fraction fa=(fraction)a;
897  poly p, q;
898  if (rSamePolyRep(src->extRing, dst->extRing))
899  {
900  p = p_Copy(NUM(fa),src->extRing);
901  if (!DENIS1(fa))
902  {
903  q = p_Copy(DEN(fa),src->extRing);
904  assume (q != NULL);
905  }
906  }
907  else
908  {
909  assume ((strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)));
910 
911  nMapFunc nMap= n_SetMap (src->extRing->cf, dst->extRing->cf);
912 
913  assume (nMap != NULL);
914  p= p_PermPoly (NUM (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
915  if (!DENIS1(fa))
916  {
917  q= p_PermPoly (DEN (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
918  assume (q != NULL);
919  }
920  }
921  definiteReduce(p, dst->extRing->qideal->m[0], dst);
922  p_Test (p, dst->extRing);
923  if (!DENIS1(fa))
924  {
925  definiteReduce(q, dst->extRing->qideal->m[0], dst);
926  p_Test (q, dst->extRing);
927  if (q != NULL)
928  {
929  number t= naDiv ((number)p,(number)q, dst);
930  p_Delete (&p, dst->extRing);
931  p_Delete (&q, dst->extRing);
932  return t;
933  }
934  WerrorS ("mapping denominator to zero");
935  }
936  return (number) p;
937 }
938 
939 /* assumes that src = Q, dst = Z/p(a) */
940 number naMap0P(number a, const coeffs src, const coeffs dst)
941 {
942  if (n_IsZero(a, src)) return NULL;
943  // int p = rChar(dst->extRing);
944 
945  number q = nlModP(a, src, dst->extRing->cf); // FIXME? TODO? // extern number nlModP(number q, const coeffs Q, const coeffs Zp); // Map q \in QQ \to pZ
946 
947  poly result = p_NSet(q, dst->extRing);
948 
949  return (number)result;
950 }
951 
952 /* assumes that src = Z/p, dst = Z/p(a) */
953 number naMapPP(number a, const coeffs src, const coeffs dst)
954 {
955  if (n_IsZero(a, src)) return NULL;
956  assume(src == dst->extRing->cf);
957  poly result = p_One(dst->extRing);
958  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
959  return (number)result;
960 }
961 
962 /* assumes that src = Z/u, dst = Z/p(a), where u != p */
963 number naMapUP(number a, const coeffs src, const coeffs dst)
964 {
965  if (n_IsZero(a, src)) return NULL;
966  /* mapping via intermediate int: */
967  int n = n_Int(a, src);
968  number q = n_Init(n, dst->extRing->cf);
969  poly result = p_One(dst->extRing);
970  p_SetCoeff(result, q, dst->extRing);
971  return (number)result;
972 }
973 
974 number naGenMap(number a, const coeffs cf, const coeffs dst)
975 {
976  if (a==NULL) return NULL;
977 
978  const ring rSrc = cf->extRing;
979  const ring rDst = dst->extRing;
980 
981  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
982  poly f = (poly)a;
983  poly g = prMapR(f, nMap, rSrc, rDst);
984 
985  n_Test((number)g, dst);
986  return (number)g;
987 }
988 
989 number naGenTrans2AlgExt(number a, const coeffs cf, const coeffs dst)
990 {
991  if (a==NULL) return NULL;
992 
993  const ring rSrc = cf->extRing;
994  const ring rDst = dst->extRing;
995 
996  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
997  fraction f = (fraction)a;
998  poly g = prMapR(NUM(f), nMap, rSrc, rDst);
999 
1000  number result=NULL;
1001  poly h = NULL;
1002 
1003  if (!DENIS1(f))
1004  h = prMapR(DEN(f), nMap, rSrc, rDst);
1005 
1006  if (h!=NULL)
1007  {
1008  result=naDiv((number)g,(number)h,dst);
1009  p_Delete(&g,dst->extRing);
1010  p_Delete(&h,dst->extRing);
1011  }
1012  else
1013  result=(number)g;
1014 
1015  n_Test((number)result, dst);
1016  return (number)result;
1017 }
1018 
1019 nMapFunc naSetMap(const coeffs src, const coeffs dst)
1020 {
1021  /* dst is expected to be an algebraic field extension */
1022  assume(getCoeffType(dst) == n_algExt);
1023 
1024  if( src == dst ) return ndCopyMap;
1025 
1026  int h = 0; /* the height of the extension tower given by dst */
1027  coeffs bDst = nCoeff_bottom(dst, h); /* the bottom field in the tower dst */
1028  coeffs bSrc = nCoeff_bottom(src, h); /* the bottom field in the tower src */
1029 
1030  /* for the time being, we only provide maps if h = 1 or 0 */
1031  if (h==0)
1032  {
1033  if ((src->rep==n_rep_gap_rat) && nCoeff_is_Q(bDst))
1034  return naMap00; /// Q or Z --> Q(a)
1035  if ((src->rep==n_rep_gap_gmp) && nCoeff_is_Q(bDst))
1036  return naMapZ0; /// Z --> Q(a)
1037  if (nCoeff_is_Zp(src) && nCoeff_is_Q(bDst))
1038  return naMapP0; /// Z/p --> Q(a)
1039  if (nCoeff_is_Q_or_BI(src) && nCoeff_is_Zp(bDst))
1040  return naMap0P; /// Q --> Z/p(a)
1041  if ((src->rep==n_rep_gap_gmp) && nCoeff_is_Zp(bDst))
1042  return naMapZ0; /// Z --> Z/p(a)
1043  if (nCoeff_is_Zp(src) && nCoeff_is_Zp(bDst))
1044  {
1045  if (src->ch == dst->ch) return naMapPP; /// Z/p --> Z/p(a)
1046  else return naMapUP; /// Z/u --> Z/p(a)
1047  }
1048  }
1049  if (h != 1) return NULL;
1050  if ((!nCoeff_is_Zp(bDst)) && (!nCoeff_is_Q(bDst))) return NULL;
1051  if ((!nCoeff_is_Zp(bSrc)) && (!nCoeff_is_Q_or_BI(bSrc))) return NULL;
1052 
1053  nMapFunc nMap=n_SetMap(src->extRing->cf,dst->extRing->cf);
1054  if (rSamePolyRep(src->extRing, dst->extRing) && (strcmp(rRingVar(0, src->extRing), rRingVar(0, dst->extRing)) == 0))
1055  {
1056  if (src->type==n_algExt)
1057  return ndCopyMap; // naCopyMap; /// K(a) --> K(a)
1058  else
1059  return naCopyTrans2AlgExt;
1060  }
1061  else if ((nMap!=NULL) && (strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)))
1062  {
1063  if (src->type==n_algExt)
1064  return naGenMap; // naCopyMap; /// K(a) --> K'(a)
1065  else
1066  return naGenTrans2AlgExt;
1067  }
1068 
1069  return NULL; /// default
1070 }
1071 
1072 int naParDeg(number a, const coeffs cf)
1073 {
1074  if (a == NULL) return -1;
1075  poly aa=(poly)a;
1076  return cf->extRing->pFDeg(aa,cf->extRing);
1077 }
1078 
1079 /// return the specified parameter as a number in the given alg. field
1080 number naParameter(const int iParameter, const coeffs cf)
1081 {
1083 
1084  const ring R = cf->extRing;
1085  assume( R != NULL );
1086  assume( 0 < iParameter && iParameter <= rVar(R) );
1087 
1088  poly p = p_One(R); p_SetExp(p, iParameter, 1, R); p_Setm(p, R);
1089 
1090  return (number) p;
1091 }
1092 
1093 
1094 /// if m == var(i)/1 => return i,
1095 int naIsParam(number m, const coeffs cf)
1096 {
1098 
1099  const ring R = cf->extRing;
1100  assume( R != NULL );
1101 
1102  return p_Var( (poly)m, R );
1103 }
1104 
1105 
1106 void naClearContent(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
1107 {
1108  assume(cf != NULL);
1110  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
1111 
1112  const ring R = cf->extRing;
1113  assume(R != NULL);
1114  const coeffs Q = R->cf;
1115  assume(Q != NULL);
1116  assume(nCoeff_is_Q(Q));
1117 
1118  numberCollectionEnumerator.Reset();
1119 
1120  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
1121  {
1122  c = n_Init(1, cf);
1123  return;
1124  }
1125 
1126  naTest(numberCollectionEnumerator.Current());
1127 
1128  // part 1, find a small candidate for gcd
1129  int s1; int s=2147483647; // max. int
1130 
1131  const BOOLEAN lc_is_pos=naGreaterZero(numberCollectionEnumerator.Current(),cf);
1132 
1133  int normalcount = 0;
1134 
1135  poly cand1, cand;
1136 
1137  do
1138  {
1139  number& n = numberCollectionEnumerator.Current();
1140  naNormalize(n, cf); ++normalcount;
1141 
1142  naTest(n);
1143 
1144  cand1 = (poly)n;
1145 
1146  s1 = p_Deg(cand1, R); // naSize?
1147  if (s>s1)
1148  {
1149  cand = cand1;
1150  s = s1;
1151  }
1152  } while (numberCollectionEnumerator.MoveNext() );
1153 
1154 // assume( nlGreaterZero(cand,cf) ); // cand may be a negative integer!
1155 
1156  cand = p_Copy(cand, R);
1157  // part 2: compute gcd(cand,all coeffs)
1158 
1159  numberCollectionEnumerator.Reset();
1160 
1161  int length = 0;
1162  while (numberCollectionEnumerator.MoveNext() )
1163  {
1164  number& n = numberCollectionEnumerator.Current();
1165  ++length;
1166 
1167  if( (--normalcount) <= 0)
1168  naNormalize(n, cf);
1169 
1170  naTest(n);
1171 
1172 // p_InpGcd(cand, (poly)n, R);
1173 
1174  cand = singclap_gcd(cand, p_Copy((poly)n, R), R);
1175 
1176 // cand1 = p_Gcd(cand,(poly)n, R); p_Delete(&cand, R); cand = cand1;
1177 
1178  assume( naGreaterZero((number)cand, cf) ); // ???
1179 /*
1180  if(p_IsConstant(cand,R))
1181  {
1182  c = cand;
1183 
1184  if(!lc_is_pos)
1185  {
1186  // make the leading coeff positive
1187  c = nlNeg(c, cf);
1188  numberCollectionEnumerator.Reset();
1189 
1190  while (numberCollectionEnumerator.MoveNext() )
1191  {
1192  number& nn = numberCollectionEnumerator.Current();
1193  nn = nlNeg(nn, cf);
1194  }
1195  }
1196  return;
1197  }
1198 */
1199 
1200  }
1201 
1202 
1203  // part3: all coeffs = all coeffs / cand
1204  if (!lc_is_pos)
1205  cand = p_Neg(cand, R);
1206 
1207  c = (number)cand; naTest(c);
1208 
1209  poly cInverse = (poly)naInvers(c, cf);
1210  assume(cInverse != NULL); // c is non-zero divisor!?
1211 
1212 
1213  numberCollectionEnumerator.Reset();
1214 
1215 
1216  while (numberCollectionEnumerator.MoveNext() )
1217  {
1218  number& n = numberCollectionEnumerator.Current();
1219 
1220  assume( length > 0 );
1221 
1222  if( --length > 0 )
1223  {
1224  assume( cInverse != NULL );
1225  n = (number) p_Mult_q(p_Copy(cInverse, R), (poly)n, R);
1226  }
1227  else
1228  {
1229  n = (number) p_Mult_q(cInverse, (poly)n, R);
1230  cInverse = NULL;
1231  assume(length == 0);
1232  }
1233 
1234  definiteReduce((poly &)n, naMinpoly, cf);
1235  }
1236 
1237  assume(length == 0);
1238  assume(cInverse == NULL); // p_Delete(&cInverse, R);
1239 
1240  // Quick and dirty fix for constant content clearing... !?
1241  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1242 
1243  number cc;
1244 
1245  n_ClearContent(itr, cc, Q); // TODO: get rid of (-LC) normalization!?
1246 
1247  // over alg. ext. of Q // takes over the input number
1248  c = (number) __p_Mult_nn( (poly)c, cc, R);
1249 // p_Mult_q(p_NSet(cc, R), , R);
1250 
1251  n_Delete(&cc, Q);
1252 
1253  // TODO: the above is not enough! need GCD's of polynomial coeffs...!
1254 /*
1255  // old and wrong part of p_Content
1256  if (rField_is_Q_a(r) && !CLEARENUMERATORS) // should not be used anymore if CLEARENUMERATORS is 1
1257  {
1258  // we only need special handling for alg. ext.
1259  if (getCoeffType(r->cf)==n_algExt)
1260  {
1261  number hzz = n_Init(1, r->cf->extRing->cf);
1262  p=ph;
1263  while (p!=NULL)
1264  { // each monom: coeff in Q_a
1265  poly c_n_n=(poly)pGetCoeff(p);
1266  poly c_n=c_n_n;
1267  while (c_n!=NULL)
1268  { // each monom: coeff in Q
1269  d=n_NormalizeHelper(hzz,pGetCoeff(c_n),r->cf->extRing->cf);
1270  n_Delete(&hzz,r->cf->extRing->cf);
1271  hzz=d;
1272  pIter(c_n);
1273  }
1274  pIter(p);
1275  }
1276  // hzz contains the 1/lcm of all denominators in c_n_n
1277  h=n_Invers(hzz,r->cf->extRing->cf);
1278  n_Delete(&hzz,r->cf->extRing->cf);
1279  n_Normalize(h,r->cf->extRing->cf);
1280  if(!n_IsOne(h,r->cf->extRing->cf))
1281  {
1282  p=ph;
1283  while (p!=NULL)
1284  { // each monom: coeff in Q_a
1285  poly c_n=(poly)pGetCoeff(p);
1286  while (c_n!=NULL)
1287  { // each monom: coeff in Q
1288  d=n_Mult(h,pGetCoeff(c_n),r->cf->extRing->cf);
1289  n_Normalize(d,r->cf->extRing->cf);
1290  n_Delete(&pGetCoeff(c_n),r->cf->extRing->cf);
1291  pGetCoeff(c_n)=d;
1292  pIter(c_n);
1293  }
1294  pIter(p);
1295  }
1296  }
1297  n_Delete(&h,r->cf->extRing->cf);
1298  }
1299  }
1300 */
1301 
1302 
1303 // c = n_Init(1, cf); assume(FALSE); // TODO: NOT YET IMPLEMENTED!!!
1304 }
1305 
1306 
1307 void naClearDenominators(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
1308 {
1309  assume(cf != NULL);
1311  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
1312 
1313  assume(cf->extRing != NULL);
1314  const coeffs Q = cf->extRing->cf;
1315  assume(Q != NULL);
1316  assume(nCoeff_is_Q(Q));
1317  number n;
1318  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1319  n_ClearDenominators(itr, n, Q); // this should probably be fine...
1320  c = (number)p_NSet(n, cf->extRing); // over alg. ext. of Q // takes over the input number
1321 }
1322 
1324 {
1325  if ((--cf->extRing->ref) == 0)
1326  rDelete(cf->extRing);
1327 }
1328 
1329 char* naCoeffString(const coeffs r) // currently also for tranext.
1330 {
1331  const char* const* p=n_ParameterNames(r);
1332  int l=0;
1333  int i;
1334  for(i=0; i<n_NumberOfParameters(r);i++)
1335  {
1336  l+=(strlen(p[i])+1);
1337  }
1338  char *s=(char *)omAlloc(l+10+1);
1339  s[0]='\0';
1340  snprintf(s,10+1,"%d",r->ch); /* Fp(a) or Q(a) */
1341  char tt[2];
1342  tt[0]=',';
1343  tt[1]='\0';
1344  for(i=0; i<n_NumberOfParameters(r);i++)
1345  {
1346  strcat(s,tt);
1347  strcat(s,p[i]);
1348  }
1349  return s;
1350 }
1351 
1352 char* naCoeffName(const coeffs r) // currently also for tranext.
1353 {
1354  const char* const* p=n_ParameterNames(r);
1355  int l=0;
1356  int i;
1357  for(i=0; i<n_NumberOfParameters(r);i++)
1358  {
1359  l+=(strlen(p[i])+1);
1360  }
1361  static char s[200];
1362  s[0]='\0';
1363  snprintf(s,10+1,"%d",r->ch); /* Fp(a) or Q(a) */
1364  char tt[2];
1365  tt[0]=',';
1366  tt[1]='\0';
1367  for(i=0; i<n_NumberOfParameters(r);i++)
1368  {
1369  strcat(s,tt);
1370  strcat(s,p[i]);
1371  }
1372  return s;
1373 }
1374 
1375 number naChineseRemainder(number *x, number *q,int rl, BOOLEAN /*sym*/,CFArray &inv_cache,const coeffs cf)
1376 {
1377  poly *P=(poly*)omAlloc(rl*sizeof(poly*));
1378  number *X=(number *)omAlloc(rl*sizeof(number));
1379  int i;
1380  for(i=0;i<rl;i++) P[i]=p_Copy((poly)(x[i]),cf->extRing);
1381  poly result=p_ChineseRemainder(P,X,q,rl,inv_cache,cf->extRing);
1382  omFreeSize(X,rl*sizeof(number));
1383  omFreeSize(P,rl*sizeof(poly*));
1384  return ((number)result);
1385 }
1386 
1387 number naFarey(number p, number n, const coeffs cf)
1388 {
1389  // n is really a bigint
1390  poly result=p_Farey(p_Copy((poly)p,cf->extRing),n,cf->extRing);
1391  return ((number)result);
1392 }
1393 
1394 
1395 BOOLEAN naInitChar(coeffs cf, void * infoStruct)
1396 {
1397  assume( infoStruct != NULL );
1398 
1399  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
1400  /// first check whether cf->extRing != NULL and delete old ring???
1401 
1402  assume(e->r != NULL); // extRing;
1403  assume(e->r->cf != NULL); // extRing->cf;
1404 
1405  assume((e->r->qideal != NULL) && // minideal has one
1406  (IDELEMS(e->r->qideal) == 1) && // non-zero generator
1407  (e->r->qideal->m[0] != NULL) ); // at m[0];
1408 
1409  assume( cf != NULL );
1410  assume(getCoeffType(cf) == n_algExt); // coeff type;
1411 
1412  e->r->ref ++; // increase the ref.counter for the ground poly. ring!
1413  const ring R = e->r; // no copy!
1414  cf->extRing = R;
1415 
1416  /* propagate characteristic up so that it becomes
1417  directly accessible in cf: */
1418  cf->ch = R->cf->ch;
1419 
1420  cf->is_field=TRUE;
1421  cf->is_domain=TRUE;
1422  cf->rep=n_rep_poly;
1423 
1424  #ifdef LDEBUG
1425  p_Test((poly)naMinpoly, naRing);
1426  #endif
1427 
1428  cf->cfCoeffString = naCoeffString;
1429  cf->cfCoeffName = naCoeffName;
1430 
1431  cf->cfGreaterZero = naGreaterZero;
1432  cf->cfGreater = naGreater;
1433  cf->cfEqual = naEqual;
1434  cf->cfIsZero = naIsZero;
1435  cf->cfIsOne = naIsOne;
1436  cf->cfIsMOne = naIsMOne;
1437  cf->cfInit = naInit;
1438  cf->cfFarey = naFarey;
1439  cf->cfChineseRemainder= naChineseRemainder;
1440  cf->cfInt = naInt;
1441  cf->cfInpNeg = naNeg;
1442  cf->cfAdd = naAdd;
1443  cf->cfSub = naSub;
1444  cf->cfMult = naMult;
1445  cf->cfDiv = naDiv;
1446  cf->cfExactDiv = naDiv;
1447  cf->cfPower = naPower;
1448  cf->cfCopy = naCopy;
1449 
1450  cf->cfWriteLong = naWriteLong;
1451 
1452  if( rCanShortOut(naRing) )
1453  cf->cfWriteShort = naWriteShort;
1454  else
1455  cf->cfWriteShort = naWriteLong;
1456 
1457  cf->cfRead = naRead;
1458  cf->cfDelete = naDelete;
1459  cf->cfSetMap = naSetMap;
1460  cf->cfGetDenom = naGetDenom;
1461  cf->cfGetNumerator = naGetNumerator;
1462  cf->cfRePart = naCopy;
1463  cf->cfCoeffWrite = naCoeffWrite;
1464  cf->cfNormalize = naNormalize;
1465  cf->cfKillChar = naKillChar;
1466 #ifdef LDEBUG
1467  cf->cfDBTest = naDBTest;
1468 #endif
1469  cf->cfGcd = naGcd;
1470  cf->cfNormalizeHelper = naLcmContent;
1471  cf->cfSize = naSize;
1472  cf->nCoeffIsEqual = naCoeffIsEqual;
1473  cf->cfInvers = naInvers;
1474  cf->convFactoryNSingN=naConvFactoryNSingN;
1475  cf->convSingNFactoryN=naConvSingNFactoryN;
1476  cf->cfParDeg = naParDeg;
1477 
1478  cf->iNumberOfParameters = rVar(R);
1479  cf->pParameterNames = (const char**)R->names;
1480  cf->cfParameter = naParameter;
1481  cf->has_simple_Inverse= R->cf->has_simple_Inverse;
1482  /* cf->has_simple_Alloc= FALSE; */
1483 
1484  if( nCoeff_is_Q(R->cf) )
1485  {
1486  cf->cfClearContent = naClearContent;
1487  cf->cfClearDenominators = naClearDenominators;
1488  }
1489 
1490  return FALSE;
1491 }
1492 
1494 
1495 template class IAccessor<snumber*>;
1496 
1497 /* --------------------------------------------------------------------*/
1498 /****************************************
1499 * Computer Algebra System SINGULAR *
1500 ****************************************/
1501 /**
1502  * ABSTRACT: numbers as polys in the ring K[a]
1503  * Assuming that we have a coeffs object cf, then these numbers
1504  * are polynomials in the polynomial ring K[a] represented by
1505  * cf->extRing.
1506  * IMPORTANT ASSUMPTIONS:
1507  * 1.) So far we assume that cf->extRing is a valid polynomial
1508  * ring
1509  **/
1510 
1511 #ifdef LDEBUG
1512 #define n2pTest(a) n2pDBTest(a,__FILE__,__LINE__,cf)
1513 BOOLEAN n2pDBTest(number a, const char *f, const int l, const coeffs r);
1514 #else
1515 #define n2pTest(a) do {} while (0)
1516 #endif
1517 
1518 /* polynomial ring in which our numbers live */
1519 #define n2pRing cf->extRing
1520 
1521 /* coeffs object in which the coefficients of our numbers live;
1522  * methods attached to n2pCoeffs may be used to compute with the
1523  * coefficients of our numbers, e.g., use n2pCoeffs->nAdd to add
1524  * coefficients of our numbers */
1525 #define n2pCoeffs cf->extRing->cf
1526 
1527 #ifdef LDEBUG
1528 BOOLEAN n2pDBTest(number a, const char *f, const int l, const coeffs cf)
1529 {
1530  if (a == NULL) return TRUE;
1531  return p_Test((poly)a, n2pRing);
1532 }
1533 #endif
1535 void n2pNormalize(number &a, const coeffs cf)
1536 {
1537  poly aa=(poly)a;
1538  p_Normalize(aa,n2pRing);
1539 }
1540 
1541 /* TRUE iff (a != 0 and (b == 0 or deg(a) > deg(b) or (deg(a)==deg(b) && lc(a)>lc(b))) */
1542 number n2pMult(number a, number b, const coeffs cf)
1543 {
1544  n2pTest(a); n2pTest(b);
1545  if ((a == NULL)||(b == NULL)) return NULL;
1546  poly aTimesB = pp_Mult_qq((poly)a, (poly)b, n2pRing);
1547  return (number)aTimesB;
1548 }
1550 number n2pDiv(number a, number b, const coeffs cf)
1551 {
1552  n2pTest(a); n2pTest(b);
1553  if (b == NULL) WerrorS(nDivBy0);
1554  if (a == NULL) return NULL;
1555  poly p=singclap_pdivide((poly)a,(poly)b,n2pRing);
1556  return (number)p;
1557 }
1559 void n2pPower(number a, int exp, number *b, const coeffs cf)
1560 {
1561  n2pTest(a);
1562 
1563  *b= (number)p_Power((poly)a,exp,n2pRing);
1564 }
1566 const char * n2pRead(const char *s, number *a, const coeffs cf)
1567 {
1568  poly aAsPoly;
1569  const char * result = p_Read(s, aAsPoly, n2pRing);
1570  *a = (number)aAsPoly;
1571  return result;
1572 }
1573 
1574 /* expects *param to be castable to AlgExtInfo */
1575 static BOOLEAN n2pCoeffIsEqual(const coeffs cf, n_coeffType n, void * param)
1576 {
1577  if (n_polyExt != n) return FALSE;
1578  AlgExtInfo *e = (AlgExtInfo *)param;
1579  /* for extension coefficient fields we expect the underlying
1580  polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
1581  this expectation is based on the assumption that we have properly
1582  registered cf and perform reference counting rather than creating
1583  multiple copies of the same coefficient field/domain/ring */
1584  if (n2pRing == e->r)
1585  return TRUE;
1586  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
1587  if( rEqual(n2pRing, e->r, TRUE) ) // also checks the equality of qideals
1588  {
1589  rDelete(e->r);
1590  return TRUE;
1591  }
1592  return FALSE;
1593 }
1595 char* n2pCoeffString(const coeffs cf)
1596 {
1597  const char* const* p=n_ParameterNames(cf);
1598  int l=0;
1599  int i;
1600  for(i=0; i<rVar(n2pRing);i++)
1601  {
1602  l+=(strlen(p[i])+1);
1603  }
1604  char *cf_s=nCoeffString(n2pRing->cf);
1605  char *s=(char *)omAlloc(l+5+strlen(cf_s));
1606  s[0]='\0';
1607  snprintf(s,strlen(cf_s)+2,"%s",cf_s);
1608  omFree(cf_s);
1609  char tt[2];
1610  tt[0]='[';
1611  tt[1]='\0';
1612  strcat(s,tt);
1613  tt[0]=',';
1614  for(i=0; i<rVar(n2pRing);i++)
1615  {
1616  strcat(s,p[i]);
1617  if (i+1!=rVar(n2pRing)) strcat(s,tt);
1618  else { tt[0]=']'; strcat(s,tt); }
1619  }
1620  return s;
1621 }
1623 char* n2pCoeffName(const coeffs cf)
1624 {
1625  const char* const* p=n_ParameterNames(cf);
1626  int l=0;
1627  int i;
1628  for(i=0; i<rVar(n2pRing);i++)
1629  {
1630  l+=(strlen(p[i])+1);
1631  }
1632  char *cf_s=nCoeffString(n2pRing->cf);
1633  static char s[200];
1634  s[0]='\0';
1635  snprintf(s,strlen(cf_s)+2,"%s",cf_s);
1636  omFree(cf_s);
1637  char tt[2];
1638  tt[0]='[';
1639  tt[1]='\0';
1640  strcat(s,tt);
1641  tt[0]=',';
1642  for(i=0; i<rVar(n2pRing);i++)
1643  {
1644  strcat(s,p[i]);
1645  if (i+1!=rVar(n2pRing)) strcat(s,tt);
1646  else { tt[0]=']'; strcat(s,tt); }
1647  }
1648  return s;
1649 }
1651 void n2pCoeffWrite(const coeffs cf, BOOLEAN details)
1652 {
1653  assume( cf != NULL );
1654 
1655  const ring A = cf->extRing;
1656 
1657  assume( A != NULL );
1658  PrintS("// polynomial ring as coefficient ring :\n");
1659  rWrite(A);
1660  PrintLn();
1661 }
1663 number n2pInvers(number a, const coeffs cf)
1664 {
1665  poly aa=(poly)a;
1666  if(p_IsConstant(aa, n2pRing))
1667  {
1668  poly p=p_Init(n2pRing);
1670  return (number)p;
1671  }
1672  else
1673  {
1674  WerrorS("not invertible");
1675  return NULL;
1676  }
1677 }
1679 BOOLEAN n2pInitChar(coeffs cf, void * infoStruct)
1680 {
1681  assume( infoStruct != NULL );
1682 
1683  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
1684  /// first check whether cf->extRing != NULL and delete old ring???
1685 
1686  assume(e->r != NULL); // extRing;
1687  assume(e->r->cf != NULL); // extRing->cf;
1688 
1689  assume( cf != NULL );
1690 
1691  e->r->ref ++; // increase the ref.counter for the ground poly. ring!
1692  const ring R = e->r; // no copy!
1693  cf->extRing = R;
1694 
1695  /* propagate characteristic up so that it becomes
1696  directly accessible in cf: */
1697  cf->ch = R->cf->ch;
1698  cf->is_field=FALSE;
1699  cf->is_domain=TRUE;
1700 
1701  cf->cfCoeffString = n2pCoeffString;
1702  cf->cfCoeffName = n2pCoeffName;
1703 
1704  cf->cfGreaterZero = naGreaterZero;
1705  cf->cfGreater = naGreater;
1706  cf->cfEqual = naEqual;
1707  cf->cfIsZero = naIsZero;
1708  cf->cfIsOne = naIsOne;
1709  cf->cfIsMOne = naIsMOne;
1710  cf->cfInit = naInit;
1711  cf->cfFarey = naFarey;
1712  cf->cfChineseRemainder= naChineseRemainder;
1713  cf->cfInt = naInt;
1714  cf->cfInpNeg = naNeg;
1715  cf->cfAdd = naAdd;
1716  cf->cfSub = naSub;
1717  cf->cfMult = n2pMult;
1718  cf->cfDiv = n2pDiv;
1719  cf->cfPower = n2pPower;
1720  cf->cfCopy = naCopy;
1721 
1722  cf->cfWriteLong = naWriteLong;
1723 
1724  if( rCanShortOut(n2pRing) )
1725  cf->cfWriteShort = naWriteShort;
1726  else
1727  cf->cfWriteShort = naWriteLong;
1728 
1729  cf->cfRead = n2pRead;
1730  cf->cfDelete = naDelete;
1731  cf->cfSetMap = naSetMap;
1732  cf->cfGetDenom = naGetDenom;
1733  cf->cfGetNumerator = naGetNumerator;
1734  cf->cfRePart = naCopy;
1735  cf->cfCoeffWrite = n2pCoeffWrite;
1736  cf->cfNormalize = n2pNormalize;
1737  cf->cfKillChar = naKillChar;
1738 #ifdef LDEBUG
1739  cf->cfDBTest = naDBTest;
1740 #endif
1741  cf->cfGcd = naGcd;
1742  cf->cfNormalizeHelper = naLcmContent;
1743  cf->cfSize = naSize;
1744  cf->nCoeffIsEqual = n2pCoeffIsEqual;
1745  cf->cfInvers = n2pInvers;
1746  cf->convFactoryNSingN=naConvFactoryNSingN;
1747  cf->convSingNFactoryN=naConvSingNFactoryN;
1748  cf->cfParDeg = naParDeg;
1749 
1750  cf->iNumberOfParameters = rVar(R);
1751  cf->pParameterNames = (const char**)R->names;
1752  cf->cfParameter = naParameter;
1753  cf->has_simple_Inverse=FALSE;
1754  /* cf->has_simple_Alloc= FALSE; */
1755 
1756  if( nCoeff_is_Q(R->cf) )
1757  {
1758  cf->cfClearContent = naClearContent;
1759  cf->cfClearDenominators = naClearDenominators;
1760  }
1761 
1762  return FALSE;
1763 }
getCoeffType
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:421
n_rep_gap_rat
(number), see longrat.h
Definition: coeffs.h:111
FALSE
#define FALSE
Definition: auxiliary.h:94
dReportError
int dReportError(const char *fmt,...)
Definition: dError.cc:43
omalloc.h
n2pCoeffString
char * n2pCoeffString(const coeffs cf)
Definition: algext.cc:1594
p_GetCoeff
#define p_GetCoeff(p, r)
Definition: monomials.h:54
nCoeff_is_Zp
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:830
StringAppendS
void StringAppendS(const char *st)
Definition: reporter.cc:106
p_GetExp
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:457
f
FILE * f
Definition: checklibs.c:9
omFree
#define omFree(addr)
Definition: omAllocDecl.h:259
p_Monic
static void p_Monic(poly p, const ring r)
returns NULL if p == NULL, otherwise makes p monic by dividing by its leading coefficient (only done ...
Definition: algext.cc:122
p_SetCoeff0
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:64
p_Normalize
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3706
IAccessor::Current
virtual reference Current()=0
Gets the current element in the collection (read and write).
p_Write0
void p_Write0(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:193
naSetMap
nMapFunc naSetMap(const coeffs src, const coeffs dst)
Get a mapping function from src into the domain of this type (n_algExt)
Definition: algext.cc:1019
naCoeffWrite
void naCoeffWrite(const coeffs cf, BOOLEAN details)
Definition: algext.cc:389
rCanShortOut
static BOOLEAN rCanShortOut(const ring r)
Definition: ring.h:576
napNormalizeHelper
number napNormalizeHelper(number b, const coeffs cf)
Definition: algext.cc:631
x
Variable x
Definition: cfModGcd.cc:4023
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
naIsOne
BOOLEAN naIsOne(number a, const coeffs cf)
Definition: algext.cc:317
naCoeffName
char * naCoeffName(const coeffs r)
Definition: algext.cc:1352
result
return result
Definition: facAbsBiFact.cc:76
n2pCoeffWrite
void n2pCoeffWrite(const coeffs cf, BOOLEAN details)
Definition: algext.cc:1650
singclap_gcd
poly singclap_gcd(poly f, poly g, const ring r)
destroys f and g
Definition: clapsing.cc:254
naIsParam
int naIsParam(number m, const coeffs cf)
if m == var(i)/1 => return i,
Definition: algext.cc:1095
n2pRead
const char * n2pRead(const char *s, number *a, const coeffs cf)
Definition: algext.cc:1565
n2pPower
void n2pPower(number a, int exp, number *b, const coeffs cf)
Definition: algext.cc:1558
naDiv
number naDiv(number a, number b, const coeffs cf)
Definition: algext.cc:471
p_Gcd
static poly p_Gcd(const poly p, const poly q, const ring r)
Definition: algext.cc:167
naGenMap
number naGenMap(number a, const coeffs cf, const coeffs dst)
Definition: algext.cc:974
naInitChar
BOOLEAN naInitChar(coeffs cf, void *infoStruct)
Initialize the coeffs object.
Definition: algext.cc:1395
naGcd
number naGcd(number a, number b, const coeffs cf)
Definition: algext.cc:772
p_Var
int p_Var(poly m, const ring r)
Definition: p_polys.cc:4536
nCoeffString
static FORCE_INLINE char * nCoeffString(const coeffs cf)
TODO: make it a virtual method of coeffs, together with: Decompose & Compose, rParameter & rPar.
Definition: coeffs.h:972
n2pInvers
number n2pInvers(number a, const coeffs cf)
Definition: algext.cc:1662
IAccessor
Definition: Enumerator.h:81
naChineseRemainder
number naChineseRemainder(number *x, number *q, int rl, BOOLEAN, CFArray &inv_cache, const coeffs cf)
Definition: algext.cc:1375
p_Neg
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1028
cf
CanonicalForm cf
Definition: cfModGcd.cc:4024
naParDeg
int naParDeg(number a, const coeffs cf)
Definition: algext.cc:1072
simpleideals.h
naInvers
number naInvers(number a, const coeffs cf)
Definition: algext.cc:820
naFarey
number naFarey(number p, number n, const coeffs cf)
Definition: algext.cc:1387
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
naMap00
number naMap00(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:850
p_ChineseRemainder
poly p_ChineseRemainder(poly *xx, number *x, number *q, int rl, CFArray &inv_cache, const ring R)
Definition: p_polys.cc:85
singclap_pdivide
poly singclap_pdivide(poly f, poly g, const ring r)
Definition: clapsing.cc:576
g
g
Definition: cfModGcd.cc:4031
naWriteLong
void naWriteLong(number a, const coeffs cf)
Definition: algext.cc:572
nCoeff_is_Q_or_BI
static FORCE_INLINE BOOLEAN nCoeff_is_Q_or_BI(const coeffs r)
Definition: coeffs.h:842
nCoeff_bottom
static coeffs nCoeff_bottom(const coeffs r, int &height)
Definition: algext.cc:260
ndCopyMap
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:251
prMapR
poly prMapR(poly src, nMapFunc nMap, ring src_r, ring dest_r)
Definition: prCopy.cc:46
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
naMinpoly
#define naMinpoly
Definition: algext.cc:72
naDBTest
BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs r)
Definition: algext.cc:235
p_Test
#define p_Test(p, r)
Definition: p_polys.h:155
clapconv.h
naMapPP
number naMapPP(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:953
auxiliary.h
naAdd
number naAdd(number a, number b, const coeffs cf)
Definition: algext.cc:439
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:464
n_NumberOfParameters
static FORCE_INLINE int n_NumberOfParameters(const coeffs r)
Returns the number of parameters.
Definition: coeffs.h:804
reporter.h
n_Greater
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff 'a' is larger than 'b'; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:511
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:468
naConvSingNFactoryN
CanonicalForm naConvSingNFactoryN(number n, BOOLEAN, const coeffs cf)
Definition: algext.cc:758
naTest
#define naTest(a)
Definition: algext.cc:56
n2pCoeffs
#define n2pCoeffs
Definition: algext.cc:1524
b
CanonicalForm b
Definition: cfModGcd.cc:4044
__p_Mult_nn
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:912
n_Normalize
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition: coeffs.h:578
p_String0Short
void p_String0Short(const poly p, ring lmRing, ring tailRing)
print p in a short way, if possible
Definition: polys0.cc:94
CanonicalForm
factory's main class
Definition: canonicalform.h:77
n_NormalizeHelper
static FORCE_INLINE number n_NormalizeHelper(number a, number b, const coeffs r)
assume that r is a quotient field (otherwise, return 1) for arguments (a1/a2,b1/b2) return (lcm(a1,...
Definition: coeffs.h:717
n2pMult
number n2pMult(number a, number b, const coeffs cf)
Definition: algext.cc:1541
p_SetExp
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:476
IBaseEnumerator::Reset
virtual void Reset()=0
Sets the enumerator to its initial position: -1, which is before the first element in the collection.
naLcmContent
number naLcmContent(number a, number b, const coeffs cf)
Definition: algext.cc:645
n_coeffType
n_coeffType
Definition: coeffs.h:26
nCoeff_is_Q
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:836
rEqual
BOOLEAN rEqual(ring r1, ring r2, BOOLEAN qr)
returns TRUE, if r1 equals r2 FALSE, otherwise Equality is determined componentwise,...
Definition: ring.cc:1619
n_CoeffWrite
static FORCE_INLINE void n_CoeffWrite(const coeffs r, BOOLEAN details=TRUE)
output the coeff description
Definition: coeffs.h:741
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:797
p_Power
poly p_Power(poly p, int i, const ring r)
Definition: p_polys.cc:2141
naCopy
number naCopy(number a, const coeffs cf)
Definition: algext.cc:298
definiteReduce
void definiteReduce(poly &p, poly reducer, const coeffs cf)
Definition: algext.cc:732
rVar
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:582
n_polyExt
used to represent polys as coeffcients
Definition: coeffs.h:34
TRUE
#define TRUE
Definition: auxiliary.h:98
i
int i
Definition: cfEzgcd.cc:125
Array
Definition: ftmpl_array.h:17
n2pTest
#define n2pTest(a)
ABSTRACT: numbers as polys in the ring K[a] Assuming that we have a coeffs object cf,...
Definition: algext.cc:1511
AlgExtInfo
struct for passing initialization parameters to naInitChar
Definition: algext.h:36
p_PermPoly
poly p_PermPoly(poly p, const int *perm, const ring oldRing, const ring dst, nMapFunc nMap, const int *par_perm, int OldPar, BOOLEAN use_mult)
Definition: p_polys.cc:4011
prCopy.h
nMapFunc
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
nDivBy0
const char *const nDivBy0
Definition: numbers.h:88
PrintS
void PrintS(const char *s)
Definition: reporter.cc:283
omFreeSize
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:258
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
nCoeff_is_algExt
static FORCE_INLINE BOOLEAN nCoeff_is_algExt(const coeffs r)
TRUE iff r represents an algebraic extension field.
Definition: coeffs.h:923
rRingVar
static char * rRingVar(short i, const ring r)
Definition: ring.h:567
naClearContent
void naClearContent(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: algext.cc:1106
clapsing.h
naRing
#define naRing
Definition: algext.cc:63
naClearDenominators
void naClearDenominators(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: algext.cc:1307
naGreaterZero
BOOLEAN naGreaterZero(number a, const coeffs cf)
forward declarations
Definition: algext.cc:380
naGreater
BOOLEAN naGreater(number a, number b, const coeffs cf)
Definition: algext.cc:360
naSize
int naSize(number a, const coeffs cf)
Definition: algext.cc:714
n2pCoeffName
char * n2pCoeffName(const coeffs cf)
Definition: algext.cc:1622
h
static Poly * h
Definition: janet.cc:972
naParameter
number naParameter(const int iParameter, const coeffs cf)
return the specified parameter as a number in the given alg. field
Definition: algext.cc:1080
naGetDenom
number naGetDenom(number &a, const coeffs cf)
Definition: algext.cc:311
ndGcd
number ndGcd(number, number, const coeffs r)
Definition: numbers.cc:161
p_String0Long
void p_String0Long(const poly p, ring lmRing, ring tailRing)
print p in a long way
Definition: polys0.cc:113
coeffs
p_Farey
poly p_Farey(poly p, number N, const ring r)
Definition: p_polys.cc:52
naGetNumerator
number naGetNumerator(number &a, const coeffs cf)
Definition: algext.cc:306
naInt
long naInt(number &a, const coeffs cf)
Definition: algext.cc:347
pp_Mult_qq
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1078
naMult
number naMult(number a, number b, const coeffs cf)
Definition: algext.cc:461
fa
BOOLEAN fa(leftv res, leftv args)
Definition: cohomo.cc:3007
naMapUP
number naMapUP(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:963
pIter
#define pIter(p)
Definition: monomials.h:41
naCoeffString
char * naCoeffString(const coeffs r)
Definition: algext.cc:1329
n_Mult
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:636
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
p_polys.h
naConvFactoryNSingN
number naConvFactoryNSingN(const CanonicalForm n, const coeffs cf)
Definition: algext.cc:752
n_Init
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:538
naPower
void naPower(number a, int exp, number *b, const coeffs cf)
Definition: algext.cc:495
p_Read
const char * p_Read(const char *st, poly &rc, const ring r)
Definition: p_polys.cc:1337
nlModP
number nlModP(number q, const coeffs, const coeffs Zp)
Definition: longrat.cc:1434
p_Init
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1249
naWriteShort
void naWriteShort(number a, const coeffs cf)
Definition: algext.cc:590
pp
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
n2pDiv
number n2pDiv(number a, number b, const coeffs cf)
Definition: algext.cc:1549
p_PolyDiv
poly p_PolyDiv(poly &p, const poly divisor, const BOOLEAN needResult, const ring r)
assumes that p and divisor are univariate polynomials in r, mentioning the same variable; assumes div...
Definition: p_polys.cc:1814
PolyEnumerator.h
naKillChar
void naKillChar(coeffs cf)
Definition: algext.cc:1323
nCoeff_is_Extension
static FORCE_INLINE BOOLEAN nCoeff_is_Extension(const coeffs r)
Definition: coeffs.h:859
nCoeff_is_transExt
static FORCE_INLINE BOOLEAN nCoeff_is_transExt(const coeffs r)
TRUE iff r represents a transcendental extension field.
Definition: coeffs.h:931
n_rep_poly
(poly), see algext.h
Definition: coeffs.h:113
p_ExtGcdHelper
static poly p_ExtGcdHelper(poly &p, poly &pFactor, poly &q, poly &qFactor, ring r)
Definition: algext.cc:185
IEnumerator
Definition: Enumerator.h:124
theDegree
static int theDegree
Definition: cf_char.cc:21
n_ParameterNames
static FORCE_INLINE const char ** n_ParameterNames(const coeffs r)
Returns a (const!) pointer to (const char*) names of parameters.
Definition: coeffs.h:808
convSingPFactoryP
CanonicalForm convSingPFactoryP(poly p, const ring r)
Definition: clapconv.cc:86
exp
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
naInit
number naInit(long i, const coeffs cf)
Definition: algext.cc:341
naRead
const char * naRead(const char *s, number *a, const coeffs cf)
Definition: algext.cc:608
rDelete
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:438
cand
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
ring.h
p_Deg
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:578
transext.h
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:842
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877
p_One
poly p_One(const ring r)
Definition: p_polys.cc:1302
singclap_extgcd
BOOLEAN singclap_extgcd(poly f, poly g, poly &res, poly &pa, poly &pb, const ring r)
Definition: clapsing.cc:437
factor
CanonicalForm factor
Definition: facAbsFact.cc:101
IBaseEnumerator::MoveNext
virtual bool MoveNext()=0
Advances the enumerator to the next element of the collection. returns true if the enumerator was suc...
naSub
number naSub(number a, number b, const coeffs cf)
Definition: algext.cc:450
n_ClearContent
static FORCE_INLINE void n_ClearContent(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs r)
Computes the content and (inplace) divides it out on a collection of numbers number c is the content ...
Definition: coeffs.h:941
n_Invers
static FORCE_INLINE number n_Invers(number a, const coeffs r)
return the multiplicative inverse of 'a'; raise an error if 'a' is not invertible
Definition: coeffs.h:564
p_EqualPolys
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition: p_polys.cc:4392
rWrite
void rWrite(ring r, BOOLEAN details)
Definition: ring.cc:226
n_ClearDenominators
static FORCE_INLINE void n_ClearDenominators(ICoeffsEnumerator &numberCollectionEnumerator, number &d, const coeffs r)
(inplace) Clears denominators on a collection of numbers number d is the LCM of all the coefficient d...
Definition: coeffs.h:948
naNormalize
void naNormalize(number &a, const coeffs cf)
Definition: algext.cc:744
Print
#define Print
Definition: emacs.cc:79
naGenTrans2AlgExt
number naGenTrans2AlgExt(number a, const coeffs cf, const coeffs dst)
Definition: algext.cc:989
heuristicReduce
void heuristicReduce(poly &p, poly reducer, const coeffs cf)
Definition: algext.cc:562
p_NSet
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1432
naCoeffIsEqual
static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void *param)
Definition: algext.cc:680
n2pCoeffIsEqual
static BOOLEAN n2pCoeffIsEqual(const coeffs cf, n_coeffType n, void *param)
Definition: algext.cc:1574
naIsZero
BOOLEAN naIsZero(number a, const coeffs cf)
Definition: algext.cc:274
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:400
n_IsMOne
static FORCE_INLINE BOOLEAN n_IsMOne(number n, const coeffs r)
TRUE iff 'n' represents the additive inverse of the one element, i.e. -1.
Definition: coeffs.h:472
n_GreaterZero
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff 'n' is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2),...
Definition: coeffs.h:494
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:451
pow
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:414
WerrorS
void WerrorS(const char *s)
Definition: feFopen.cc:24
m
int m
Definition: cfEzgcd.cc:121
naMapP0
number naMapP0(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:872
assume
#define assume(x)
Definition: mod2.h:384
NULL
#define NULL
Definition: omList.c:9
l
int l
Definition: cfEzgcd.cc:93
p_ExtGcd
poly p_ExtGcd(poly p, poly &pFactor, poly q, poly &qFactor, ring r)
assumes that p and q are univariate polynomials in r, mentioning the same variable; assumes a global ...
Definition: algext.cc:218
n_SubringGcd
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:688
n_Int
static FORCE_INLINE long n_Int(number &n, const coeffs r)
conversion of n to an int; 0 if not possible in Z/pZ: the representing int lying in (-p/2 ....
Definition: coeffs.h:547
nCoeff_is_Q_algext
static FORCE_INLINE BOOLEAN nCoeff_is_Q_algext(const coeffs r)
is it an alg. ext. of Q?
Definition: coeffs.h:927
R
#define R
Definition: sirandom.c:26
naNeg
number naNeg(number a, const coeffs cf)
this is in-place, modifies a
Definition: algext.cc:334
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:224
naCoeffs
#define naCoeffs
Definition: algext.cc:69
rSamePolyRep
BOOLEAN rSamePolyRep(ring r1, ring r2)
returns TRUE, if r1 and r2 represents the monomials in the same way FALSE, otherwise this is an analo...
Definition: ring.cc:1667
p_Totaldegree
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1435
p
int p
Definition: cfModGcd.cc:4019
longrat.h
p_IsConstant
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1901
naDelete
void naDelete(number *a, const coeffs cf)
Definition: algext.cc:280
naCopyTrans2AlgExt
number naCopyTrans2AlgExt(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:892
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
p_GcdHelper
static poly p_GcdHelper(poly &p, poly &q, const ring r)
see p_Gcd; additional assumption: deg(p) >= deg(q); must destroy p and q (unless one of them is retur...
Definition: algext.cc:147
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
n_Div
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition: coeffs.h:615
n_SetMap
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:721
IDELEMS
#define IDELEMS(i)
Definition: simpleideals.h:24
p_ISet
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1286
Q
#define Q
Definition: sirandom.c:25
p_Mult_q
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1035
naIsMOne
BOOLEAN naIsMOne(number a, const coeffs cf)
Definition: algext.cc:325
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:48
PrintLn
void PrintLn()
Definition: reporter.cc:309
naEqual
BOOLEAN naEqual(number a, number b, const coeffs cf)
Definition: algext.cc:289
n_Test
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738
algext.h
AlgExtInfo::r
ring r
Definition: algext.h:37
n2pRing
#define n2pRing
Definition: algext.cc:1518
A
#define A
Definition: sirandom.c:23
n2pInitChar
BOOLEAN n2pInitChar(coeffs cf, void *infoStruct)
Definition: algext.cc:1678
numbers.h
pNext
#define pNext(p)
Definition: monomials.h:40
convFactoryPSingP
poly convFactoryPSingP(const CanonicalForm &f, const ring r)
Definition: clapconv.cc:41
n2pDBTest
BOOLEAN n2pDBTest(number a, const char *f, const int l, const coeffs r)
Definition: algext.cc:1527
CRecursivePolyCoeffsEnumerator
go into polynomials over an alg. extension recursively
Definition: PolyEnumerator.h:161
naMapZ0
number naMapZ0(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:860
n2pNormalize
void n2pNormalize(number &a, const coeffs cf)
Definition: algext.cc:1534
n_algExt
used for all algebraic extensions, i.e., the top-most extension in an extension tower is algebraic
Definition: coeffs.h:35
coeffs.h
naMap0P
number naMap0P(number a, const coeffs src, const coeffs dst)
Definition: algext.cc:940
n_rep_gap_gmp
(), see rinteger.h, new impl.
Definition: coeffs.h:112