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