My Project  UNKNOWN_GIT_VERSION
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_r((poly)a, (poly)b, 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 static 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  { // R->cf is QQ
1175  poly tmp=gcd_over_Q(cand,(poly)n,R);
1176  p_Delete(&cand,R);
1177  cand=tmp;
1178  }
1179 
1180 // cand1 = p_Gcd(cand,(poly)n, R); p_Delete(&cand, R); cand = cand1;
1181 
1182  assume( naGreaterZero((number)cand, cf) ); // ???
1183 /*
1184  if(p_IsConstant(cand,R))
1185  {
1186  c = cand;
1187 
1188  if(!lc_is_pos)
1189  {
1190  // make the leading coeff positive
1191  c = nlNeg(c, cf);
1192  numberCollectionEnumerator.Reset();
1193 
1194  while (numberCollectionEnumerator.MoveNext() )
1195  {
1196  number& nn = numberCollectionEnumerator.Current();
1197  nn = nlNeg(nn, cf);
1198  }
1199  }
1200  return;
1201  }
1202 */
1203 
1204  }
1205 
1206 
1207  // part3: all coeffs = all coeffs / cand
1208  if (!lc_is_pos)
1209  cand = p_Neg(cand, R);
1210 
1211  c = (number)cand; naTest(c);
1212 
1213  poly cInverse = (poly)naInvers(c, cf);
1214  assume(cInverse != NULL); // c is non-zero divisor!?
1215 
1216 
1217  numberCollectionEnumerator.Reset();
1218 
1219 
1220  while (numberCollectionEnumerator.MoveNext() )
1221  {
1222  number& n = numberCollectionEnumerator.Current();
1223 
1224  assume( length > 0 );
1225 
1226  if( --length > 0 )
1227  {
1228  assume( cInverse != NULL );
1229  n = (number) p_Mult_q(p_Copy(cInverse, R), (poly)n, R);
1230  }
1231  else
1232  {
1233  n = (number) p_Mult_q(cInverse, (poly)n, R);
1234  cInverse = NULL;
1235  assume(length == 0);
1236  }
1237 
1238  definiteReduce((poly &)n, naMinpoly, cf);
1239  }
1240 
1241  assume(length == 0);
1242  assume(cInverse == NULL); // p_Delete(&cInverse, R);
1243 
1244  // Quick and dirty fix for constant content clearing... !?
1245  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1246 
1247  number cc;
1248 
1249  n_ClearContent(itr, cc, Q); // TODO: get rid of (-LC) normalization!?
1250 
1251  // over alg. ext. of Q // takes over the input number
1252  c = (number) __p_Mult_nn( (poly)c, cc, R);
1253 // p_Mult_q(p_NSet(cc, R), , R);
1254 
1255  n_Delete(&cc, Q);
1256 
1257  // TODO: the above is not enough! need GCD's of polynomial coeffs...!
1258 /*
1259  // old and wrong part of p_Content
1260  if (rField_is_Q_a(r) && !CLEARENUMERATORS) // should not be used anymore if CLEARENUMERATORS is 1
1261  {
1262  // we only need special handling for alg. ext.
1263  if (getCoeffType(r->cf)==n_algExt)
1264  {
1265  number hzz = n_Init(1, r->cf->extRing->cf);
1266  p=ph;
1267  while (p!=NULL)
1268  { // each monom: coeff in Q_a
1269  poly c_n_n=(poly)pGetCoeff(p);
1270  poly c_n=c_n_n;
1271  while (c_n!=NULL)
1272  { // each monom: coeff in Q
1273  d=n_NormalizeHelper(hzz,pGetCoeff(c_n),r->cf->extRing->cf);
1274  n_Delete(&hzz,r->cf->extRing->cf);
1275  hzz=d;
1276  pIter(c_n);
1277  }
1278  pIter(p);
1279  }
1280  // hzz contains the 1/lcm of all denominators in c_n_n
1281  h=n_Invers(hzz,r->cf->extRing->cf);
1282  n_Delete(&hzz,r->cf->extRing->cf);
1283  n_Normalize(h,r->cf->extRing->cf);
1284  if(!n_IsOne(h,r->cf->extRing->cf))
1285  {
1286  p=ph;
1287  while (p!=NULL)
1288  { // each monom: coeff in Q_a
1289  poly c_n=(poly)pGetCoeff(p);
1290  while (c_n!=NULL)
1291  { // each monom: coeff in Q
1292  d=n_Mult(h,pGetCoeff(c_n),r->cf->extRing->cf);
1293  n_Normalize(d,r->cf->extRing->cf);
1294  n_Delete(&pGetCoeff(c_n),r->cf->extRing->cf);
1295  pGetCoeff(c_n)=d;
1296  pIter(c_n);
1297  }
1298  pIter(p);
1299  }
1300  }
1301  n_Delete(&h,r->cf->extRing->cf);
1302  }
1303  }
1304 */
1305 
1306 
1307 // c = n_Init(1, cf); assume(FALSE); // TODO: NOT YET IMPLEMENTED!!!
1308 }
1309 
1310 
1311 void naClearDenominators(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
1312 {
1313  assume(cf != NULL);
1315  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
1316 
1317  assume(cf->extRing != NULL);
1318  const coeffs Q = cf->extRing->cf;
1319  assume(Q != NULL);
1320  assume(nCoeff_is_Q(Q));
1321  number n;
1322  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1323  n_ClearDenominators(itr, n, Q); // this should probably be fine...
1324  c = (number)p_NSet(n, cf->extRing); // over alg. ext. of Q // takes over the input number
1325 }
1326 
1328 {
1329  if ((--cf->extRing->ref) == 0)
1330  rDelete(cf->extRing);
1331 }
1332 
1333 char* naCoeffString(const coeffs r) // currently also for tranext.
1334 {
1335  const char* const* p=n_ParameterNames(r);
1336  int l=0;
1337  int i;
1338  for(i=0; i<n_NumberOfParameters(r);i++)
1339  {
1340  l+=(strlen(p[i])+1);
1341  }
1342  char *s=(char *)omAlloc(l+10+1);
1343  s[0]='\0';
1344  snprintf(s,10+1,"%d",r->ch); /* Fp(a) or Q(a) */
1345  char tt[2];
1346  tt[0]=',';
1347  tt[1]='\0';
1348  for(i=0; i<n_NumberOfParameters(r);i++)
1349  {
1350  strcat(s,tt);
1351  strcat(s,p[i]);
1352  }
1353  return s;
1354 }
1355 
1356 char* naCoeffName(const coeffs r) // currently also for tranext.
1357 {
1358  const char* const* p=n_ParameterNames(r);
1359  int l=0;
1360  int i;
1361  for(i=0; i<n_NumberOfParameters(r);i++)
1362  {
1363  l+=(strlen(p[i])+1);
1364  }
1365  static char s[200];
1366  s[0]='\0';
1367  snprintf(s,10+1,"%d",r->ch); /* Fp(a) or Q(a) */
1368  char tt[2];
1369  tt[0]=',';
1370  tt[1]='\0';
1371  for(i=0; i<n_NumberOfParameters(r);i++)
1372  {
1373  strcat(s,tt);
1374  strcat(s,p[i]);
1375  }
1376  return s;
1377 }
1378 
1379 number naChineseRemainder(number *x, number *q,int rl, BOOLEAN /*sym*/,CFArray &inv_cache,const coeffs cf)
1380 {
1381  poly *P=(poly*)omAlloc(rl*sizeof(poly*));
1382  number *X=(number *)omAlloc(rl*sizeof(number));
1383  int i;
1384  for(i=0;i<rl;i++) P[i]=p_Copy((poly)(x[i]),cf->extRing);
1385  poly result=p_ChineseRemainder(P,X,q,rl,inv_cache,cf->extRing);
1386  omFreeSize(X,rl*sizeof(number));
1387  omFreeSize(P,rl*sizeof(poly*));
1388  return ((number)result);
1389 }
1390 
1391 number naFarey(number p, number n, const coeffs cf)
1392 {
1393  // n is really a bigint
1394  poly result=p_Farey(p_Copy((poly)p,cf->extRing),n,cf->extRing);
1395  return ((number)result);
1396 }
1397 
1398 
1399 BOOLEAN naInitChar(coeffs cf, void * infoStruct)
1400 {
1401  assume( infoStruct != NULL );
1402 
1403  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
1404  /// first check whether cf->extRing != NULL and delete old ring???
1405 
1406  assume(e->r != NULL); // extRing;
1407  assume(e->r->cf != NULL); // extRing->cf;
1408 
1409  assume((e->r->qideal != NULL) && // minideal has one
1410  (IDELEMS(e->r->qideal) == 1) && // non-zero generator
1411  (e->r->qideal->m[0] != NULL) ); // at m[0];
1412 
1413  assume( cf != NULL );
1414  assume(getCoeffType(cf) == n_algExt); // coeff type;
1415 
1416  e->r->ref ++; // increase the ref.counter for the ground poly. ring!
1417  const ring R = e->r; // no copy!
1418  cf->extRing = R;
1419 
1420  /* propagate characteristic up so that it becomes
1421  directly accessible in cf: */
1422  cf->ch = R->cf->ch;
1423 
1424  cf->is_field=TRUE;
1425  cf->is_domain=TRUE;
1426  cf->rep=n_rep_poly;
1427 
1428  #ifdef LDEBUG
1429  p_Test((poly)naMinpoly, naRing);
1430  #endif
1431 
1432  cf->cfCoeffString = naCoeffString;
1433  cf->cfCoeffName = naCoeffName;
1434 
1435  cf->cfGreaterZero = naGreaterZero;
1436  cf->cfGreater = naGreater;
1437  cf->cfEqual = naEqual;
1438  cf->cfIsZero = naIsZero;
1439  cf->cfIsOne = naIsOne;
1440  cf->cfIsMOne = naIsMOne;
1441  cf->cfInit = naInit;
1442  cf->cfFarey = naFarey;
1443  cf->cfChineseRemainder= naChineseRemainder;
1444  cf->cfInt = naInt;
1445  cf->cfInpNeg = naNeg;
1446  cf->cfAdd = naAdd;
1447  cf->cfSub = naSub;
1448  cf->cfMult = naMult;
1449  cf->cfDiv = naDiv;
1450  cf->cfExactDiv = naDiv;
1451  cf->cfPower = naPower;
1452  cf->cfCopy = naCopy;
1453 
1454  cf->cfWriteLong = naWriteLong;
1455 
1456  if( rCanShortOut(naRing) )
1457  cf->cfWriteShort = naWriteShort;
1458  else
1459  cf->cfWriteShort = naWriteLong;
1460 
1461  cf->cfRead = naRead;
1462  cf->cfDelete = naDelete;
1463  cf->cfSetMap = naSetMap;
1464  cf->cfGetDenom = naGetDenom;
1465  cf->cfGetNumerator = naGetNumerator;
1466  cf->cfRePart = naCopy;
1467  cf->cfCoeffWrite = naCoeffWrite;
1468  cf->cfNormalize = naNormalize;
1469  cf->cfKillChar = naKillChar;
1470 #ifdef LDEBUG
1471  cf->cfDBTest = naDBTest;
1472 #endif
1473  cf->cfGcd = naGcd;
1474  cf->cfNormalizeHelper = naLcmContent;
1475  cf->cfSize = naSize;
1476  cf->nCoeffIsEqual = naCoeffIsEqual;
1477  cf->cfInvers = naInvers;
1478  cf->convFactoryNSingN=naConvFactoryNSingN;
1479  cf->convSingNFactoryN=naConvSingNFactoryN;
1480  cf->cfParDeg = naParDeg;
1481 
1482  cf->iNumberOfParameters = rVar(R);
1483  cf->pParameterNames = (const char**)R->names;
1484  cf->cfParameter = naParameter;
1485  cf->has_simple_Inverse= R->cf->has_simple_Inverse;
1486  /* cf->has_simple_Alloc= FALSE; */
1487 
1488  if( nCoeff_is_Q(R->cf) )
1489  {
1490  cf->cfClearContent = naClearContent;
1491  cf->cfClearDenominators = naClearDenominators;
1492  }
1493 
1494  return FALSE;
1495 }
1496 
1498 
1499 template class IAccessor<snumber*>;
1500 
1501 /* --------------------------------------------------------------------*/
1502 /****************************************
1503 * Computer Algebra System SINGULAR *
1504 ****************************************/
1505 /**
1506  * ABSTRACT: numbers as polys in the ring K[a]
1507  * Assuming that we have a coeffs object cf, then these numbers
1508  * are polynomials in the polynomial ring K[a] represented by
1509  * cf->extRing.
1510  * IMPORTANT ASSUMPTIONS:
1511  * 1.) So far we assume that cf->extRing is a valid polynomial
1512  * ring
1513  **/
1514 
1515 #ifdef LDEBUG
1516 #define n2pTest(a) n2pDBTest(a,__FILE__,__LINE__,cf)
1517 BOOLEAN n2pDBTest(number a, const char *f, const int l, const coeffs r);
1518 #else
1519 #define n2pTest(a) do {} while (0)
1520 #endif
1521 
1522 /* polynomial ring in which our numbers live */
1523 #define n2pRing cf->extRing
1524 
1525 /* coeffs object in which the coefficients of our numbers live;
1526  * methods attached to n2pCoeffs may be used to compute with the
1527  * coefficients of our numbers, e.g., use n2pCoeffs->nAdd to add
1528  * coefficients of our numbers */
1529 #define n2pCoeffs cf->extRing->cf
1530 
1531 #ifdef LDEBUG
1532 BOOLEAN n2pDBTest(number a, const char *f, const int l, const coeffs cf)
1533 {
1534  if (a == NULL) return TRUE;
1535  return p_Test((poly)a, n2pRing);
1536 }
1537 #endif
1539 void n2pNormalize(number &a, const coeffs cf)
1540 {
1541  poly aa=(poly)a;
1542  p_Normalize(aa,n2pRing);
1543 }
1544 
1545 /* TRUE iff (a != 0 and (b == 0 or deg(a) > deg(b) or (deg(a)==deg(b) && lc(a)>lc(b))) */
1546 number n2pMult(number a, number b, const coeffs cf)
1547 {
1548  n2pTest(a); n2pTest(b);
1549  if ((a == NULL)||(b == NULL)) return NULL;
1550  poly aTimesB = pp_Mult_qq((poly)a, (poly)b, n2pRing);
1551  return (number)aTimesB;
1552 }
1554 number n2pDiv(number a, number b, const coeffs cf)
1555 {
1556  n2pTest(a); n2pTest(b);
1557  if (b == NULL) WerrorS(nDivBy0);
1558  if (a == NULL) return NULL;
1559  poly p=singclap_pdivide((poly)a,(poly)b,n2pRing);
1560  return (number)p;
1561 }
1563 void n2pPower(number a, int exp, number *b, const coeffs cf)
1564 {
1565  n2pTest(a);
1566 
1567  *b= (number)p_Power((poly)a,exp,n2pRing);
1568 }
1570 const char * n2pRead(const char *s, number *a, const coeffs cf)
1571 {
1572  poly aAsPoly;
1573  const char * result = p_Read(s, aAsPoly, n2pRing);
1574  *a = (number)aAsPoly;
1575  return result;
1576 }
1577 
1578 /* expects *param to be castable to AlgExtInfo */
1579 static BOOLEAN n2pCoeffIsEqual(const coeffs cf, n_coeffType n, void * param)
1580 {
1581  if (n_polyExt != n) return FALSE;
1582  AlgExtInfo *e = (AlgExtInfo *)param;
1583  /* for extension coefficient fields we expect the underlying
1584  polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
1585  this expectation is based on the assumption that we have properly
1586  registered cf and perform reference counting rather than creating
1587  multiple copies of the same coefficient field/domain/ring */
1588  if (n2pRing == e->r)
1589  return TRUE;
1590  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
1591  if( rEqual(n2pRing, e->r, TRUE) ) // also checks the equality of qideals
1592  {
1593  rDelete(e->r);
1594  return TRUE;
1595  }
1596  return FALSE;
1597 }
1599 char* n2pCoeffString(const coeffs cf)
1600 {
1601  const char* const* p=n_ParameterNames(cf);
1602  int l=0;
1603  int i;
1604  for(i=0; i<rVar(n2pRing);i++)
1605  {
1606  l+=(strlen(p[i])+1);
1607  }
1608  char *cf_s=nCoeffString(n2pRing->cf);
1609  char *s=(char *)omAlloc(l+5+strlen(cf_s));
1610  s[0]='\0';
1611  snprintf(s,strlen(cf_s)+2,"%s",cf_s);
1612  omFree(cf_s);
1613  char tt[2];
1614  tt[0]='[';
1615  tt[1]='\0';
1616  strcat(s,tt);
1617  tt[0]=',';
1618  for(i=0; i<rVar(n2pRing);i++)
1619  {
1620  strcat(s,p[i]);
1621  if (i+1!=rVar(n2pRing)) strcat(s,tt);
1622  else { tt[0]=']'; strcat(s,tt); }
1623  }
1624  return s;
1625 }
1627 char* n2pCoeffName(const coeffs cf)
1628 {
1629  const char* const* p=n_ParameterNames(cf);
1630  int l=0;
1631  int i;
1632  for(i=0; i<rVar(n2pRing);i++)
1633  {
1634  l+=(strlen(p[i])+1);
1635  }
1636  char *cf_s=nCoeffString(n2pRing->cf);
1637  static char s[200];
1638  s[0]='\0';
1639  snprintf(s,strlen(cf_s)+2,"%s",cf_s);
1640  omFree(cf_s);
1641  char tt[2];
1642  tt[0]='[';
1643  tt[1]='\0';
1644  strcat(s,tt);
1645  tt[0]=',';
1646  for(i=0; i<rVar(n2pRing);i++)
1647  {
1648  strcat(s,p[i]);
1649  if (i+1!=rVar(n2pRing)) strcat(s,tt);
1650  else { tt[0]=']'; strcat(s,tt); }
1651  }
1652  return s;
1653 }
1655 void n2pCoeffWrite(const coeffs cf, BOOLEAN details)
1656 {
1657  assume( cf != NULL );
1658 
1659  const ring A = cf->extRing;
1660 
1661  assume( A != NULL );
1662  PrintS("// polynomial ring as coefficient ring :\n");
1663  rWrite(A);
1664  PrintLn();
1665 }
1667 number n2pInvers(number a, const coeffs cf)
1668 {
1669  poly aa=(poly)a;
1670  if(p_IsConstant(aa, n2pRing))
1671  {
1672  poly p=p_Init(n2pRing);
1674  return (number)p;
1675  }
1676  else
1677  {
1678  WerrorS("not invertible");
1679  return NULL;
1680  }
1681 }
1683 BOOLEAN n2pInitChar(coeffs cf, void * infoStruct)
1684 {
1685  assume( infoStruct != NULL );
1686 
1687  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
1688  /// first check whether cf->extRing != NULL and delete old ring???
1689 
1690  assume(e->r != NULL); // extRing;
1691  assume(e->r->cf != NULL); // extRing->cf;
1692 
1693  assume( cf != NULL );
1694 
1695  e->r->ref ++; // increase the ref.counter for the ground poly. ring!
1696  const ring R = e->r; // no copy!
1697  cf->extRing = R;
1698 
1699  /* propagate characteristic up so that it becomes
1700  directly accessible in cf: */
1701  cf->ch = R->cf->ch;
1702  cf->is_field=FALSE;
1703  cf->is_domain=TRUE;
1704 
1705  cf->cfCoeffString = n2pCoeffString;
1706  cf->cfCoeffName = n2pCoeffName;
1707 
1708  cf->cfGreaterZero = naGreaterZero;
1709  cf->cfGreater = naGreater;
1710  cf->cfEqual = naEqual;
1711  cf->cfIsZero = naIsZero;
1712  cf->cfIsOne = naIsOne;
1713  cf->cfIsMOne = naIsMOne;
1714  cf->cfInit = naInit;
1715  cf->cfFarey = naFarey;
1716  cf->cfChineseRemainder= naChineseRemainder;
1717  cf->cfInt = naInt;
1718  cf->cfInpNeg = naNeg;
1719  cf->cfAdd = naAdd;
1720  cf->cfSub = naSub;
1721  cf->cfMult = n2pMult;
1722  cf->cfDiv = n2pDiv;
1723  cf->cfPower = n2pPower;
1724  cf->cfCopy = naCopy;
1725 
1726  cf->cfWriteLong = naWriteLong;
1727 
1728  if( rCanShortOut(n2pRing) )
1729  cf->cfWriteShort = naWriteShort;
1730  else
1731  cf->cfWriteShort = naWriteLong;
1732 
1733  cf->cfRead = n2pRead;
1734  cf->cfDelete = naDelete;
1735  cf->cfSetMap = naSetMap;
1736  cf->cfGetDenom = naGetDenom;
1737  cf->cfGetNumerator = naGetNumerator;
1738  cf->cfRePart = naCopy;
1739  cf->cfCoeffWrite = n2pCoeffWrite;
1740  cf->cfNormalize = n2pNormalize;
1741  cf->cfKillChar = naKillChar;
1742 #ifdef LDEBUG
1743  cf->cfDBTest = naDBTest;
1744 #endif
1745  cf->cfGcd = naGcd;
1746  cf->cfNormalizeHelper = naLcmContent;
1747  cf->cfSize = naSize;
1748  cf->nCoeffIsEqual = n2pCoeffIsEqual;
1749  cf->cfInvers = n2pInvers;
1750  cf->convFactoryNSingN=naConvFactoryNSingN;
1751  cf->convSingNFactoryN=naConvSingNFactoryN;
1752  cf->cfParDeg = naParDeg;
1753 
1754  cf->iNumberOfParameters = rVar(R);
1755  cf->pParameterNames = (const char**)R->names;
1756  cf->cfParameter = naParameter;
1757  cf->has_simple_Inverse=FALSE;
1758  /* cf->has_simple_Alloc= FALSE; */
1759 
1760  if( nCoeff_is_Q(R->cf) )
1761  {
1762  cf->cfClearContent = naClearContent;
1763  cf->cfClearDenominators = naClearDenominators;
1764  }
1765 
1766  return FALSE;
1767 }
getCoeffType
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:420
n_rep_gap_rat
(number), see longrat.h
Definition: coeffs.h:110
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:1598
p_GetCoeff
#define p_GetCoeff(p, r)
Definition: monomials.h:48
nCoeff_is_Zp
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:821
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:458
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:58
p_Normalize
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3720
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:575
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:1356
result
return result
Definition: facAbsBiFact.cc:76
n2pCoeffWrite
void n2pCoeffWrite(const coeffs cf, BOOLEAN details)
Definition: algext.cc:1654
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:1569
n2pPower
void n2pPower(number a, int exp, number *b, const coeffs cf)
Definition: algext.cc:1562
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:1399
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:4550
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:980
n2pInvers
number n2pInvers(number a, const coeffs cf)
Definition: algext.cc:1666
IAccessor
Definition: Enumerator.h:81
naChineseRemainder
number naChineseRemainder(number *x, number *q, int rl, BOOLEAN, CFArray &inv_cache, const coeffs cf)
Definition: algext.cc:1379
p_Neg
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1029
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:1391
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
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:556
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:850
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:252
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:454
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:156
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:463
n_NumberOfParameters
static FORCE_INLINE int n_NumberOfParameters(const coeffs r)
Returns the number of parameters.
Definition: coeffs.h:795
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:510
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:467
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:1528
b
CanonicalForm b
Definition: cfModGcd.cc:4044
__p_Mult_nn
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:913
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:577
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:716
n2pMult
number n2pMult(number a, number b, const coeffs cf)
Definition: algext.cc:1545
gcd_over_Q
poly gcd_over_Q(poly f, poly g, const ring r)
helper routine for calling singclap_gcd_r
Definition: transext.cc:275
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:477
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:827
rEqual
BOOLEAN rEqual(ring r1, ring r2, BOOLEAN qr)
returns TRUE, if r1 equals r2 FALSE, otherwise Equality is determined componentwise,...
Definition: ring.cc:1634
n_CoeffWrite
static FORCE_INLINE void n_CoeffWrite(const coeffs r, BOOLEAN details=TRUE)
output the coeff description
Definition: coeffs.h:740
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:798
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:581
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< CanonicalForm >
n2pTest
#define n2pTest(a)
ABSTRACT: numbers as polys in the ring K[a] Assuming that we have a coeffs object cf,...
Definition: algext.cc:1515
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:4025
prCopy.h
nMapFunc
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:72
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:931
rRingVar
static char * rRingVar(short i, const ring r)
Definition: ring.h:566
clapsing.h
naRing
#define naRing
Definition: algext.cc:63
naClearDenominators
void naClearDenominators(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: algext.cc:1311
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:1626
naClearContent
static void naClearContent(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: algext.cc:1106
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:162
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:1073
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:35
naCoeffString
char * naCoeffString(const coeffs r)
Definition: algext.cc:1333
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:635
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:537
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:1240
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:248
n2pDiv
number n2pDiv(number a, number b, const coeffs cf)
Definition: algext.cc:1553
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:1327
nCoeff_is_Extension
static FORCE_INLINE BOOLEAN nCoeff_is_Extension(const coeffs r)
Definition: coeffs.h:867
nCoeff_is_transExt
static FORCE_INLINE BOOLEAN nCoeff_is_transExt(const coeffs r)
TRUE iff r represents a transcendental extension field.
Definition: coeffs.h:939
n_rep_poly
(poly), see algext.h
Definition: coeffs.h:112
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:799
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:436
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:843
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:878
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:421
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:949
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:563
p_EqualPolys
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition: p_polys.cc:4406
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:956
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:1578
singclap_gcd_r
poly singclap_gcd_r(poly f, poly g, const ring r)
Definition: clapsing.cc:42
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:401
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:471
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:493
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:450
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:687
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:546
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:935
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:225
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:1682
p_Totaldegree
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1426
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:1907
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
NUM
Definition: readcf.cc:173
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:614
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:720
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:1036
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:42
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:737
algext.h
AlgExtInfo::r
ring r
Definition: algext.h:37
n2pRing
#define n2pRing
Definition: algext.cc:1522
A
#define A
Definition: sirandom.c:23
n2pInitChar
BOOLEAN n2pInitChar(coeffs cf, void *infoStruct)
Definition: algext.cc:1682
numbers.h
pNext
#define pNext(p)
Definition: monomials.h:34
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:1531
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:1538
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:111