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