transext.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: numbers in a rational function field K(t_1, .., t_s) with
6 * transcendental variables t_1, ..., t_s, where s >= 1.
7 * Denoting the implemented coeffs object by cf, then these numbers
8 * are represented as quotients of polynomials living in the
9 * polynomial ring K[t_1, .., t_s] represented by cf->extring.
10 *
11 * An element of K(t_1, .., t_s) may have numerous representations,
12 * due to the possibility of common polynomial factors in the
13 * numerator and denominator. This problem is handled by a
14 * cancellation heuristic: Each number "knows" its complexity
15 * which is 0 if and only if common factors have definitely been
16 * cancelled, and some positive integer otherwise.
17 * Each arithmetic operation of two numbers with complexities c1
18 * and c2 will result in a number of complexity c1 + c2 + some
19 * penalty (specific for each arithmetic operation; see constants
20 * in the *.h file). Whenever the resulting complexity exceeds a
21 * certain threshold (see constant in the *.h file), then the
22 * cancellation heuristic will call 'factory' to compute the gcd
23 * and cancel it out in the given number.
24 * For the special case of K = Q (i.e., when computing over the
25 * rationals), this definite cancellation procedure will also take
26 * care of nested fractions: If there are fractional coefficients
27 * in the numerator or denominator of a number, then this number
28 * is being replaced by a quotient of two polynomials over Z, or
29 * - if the denominator is a constant - by a polynomial over Q.
30 *
31 * TODO: the description above needs a major update!!!
32 */
33 #define TRANSEXT_PRIVATES
34 
35 #include <misc/auxiliary.h>
36 
37 #include <omalloc/omalloc.h>
38 #include <factory/factory.h>
39 
40 #include <reporter/reporter.h>
41 
42 #include <coeffs/coeffs.h>
43 #include <coeffs/numbers.h>
44 
45 #include <coeffs/longrat.h>
46 
47 #include <polys/monomials/ring.h>
49 #include <polys/simpleideals.h>
50 
51 #include <polys/clapsing.h>
52 #include <polys/clapconv.h>
53 
54 #include <polys/prCopy.h>
55 #include "transext.h"
56 #include "algext.h"
57 
58 #include <polys/PolyEnumerator.h>
59 
60 
61 /* constants for controlling the complexity of numbers */
62 #define ADD_COMPLEXITY 1 /**< complexity increase due to + and - */
63 #define MULT_COMPLEXITY 2 /**< complexity increase due to * and / */
64 #define DIFF_COMPLEXITY 2 /**< complexity increase due to * and / */
65 #define BOUND_COMPLEXITY 10 /**< maximum complexity of a number */
66 
67 /// TRUE iff num. represents 1
68 #define NUMIS1(f) (p_IsOne(NUM(f), cf->extRing))
69 
70 #define COM(f) f->complexity
71 
72 
73 #ifdef LDEBUG
74 BOOLEAN ntDBTest(number a, const char *f, const int l, const coeffs r);
75 #endif
76 
77 #define ntTest(a) n_Test(a, cf)
78 
79 /// Our own type!
80 static const n_coeffType ID = n_transExt;
81 
82 /* polynomial ring in which the numerators and denominators of our
83  numbers live */
84 #define ntRing cf->extRing
85 
86 /* coeffs object in which the coefficients of our numbers live;
87  * methods attached to ntCoeffs may be used to compute with the
88  * coefficients of our numbers, e.g., use ntCoeffs->nAdd to add
89  * coefficients of our numbers */
90 #define ntCoeffs cf->extRing->cf
91 
92 
93 omBin fractionObjectBin = omGetSpecBin(sizeof(fractionObject));
94 
95 /// forward declarations
96 BOOLEAN ntGreaterZero(number a, const coeffs cf);
97 BOOLEAN ntGreater(number a, number b, const coeffs cf);
98 BOOLEAN ntEqual(number a, number b, const coeffs cf);
99 BOOLEAN ntIsOne(number a, const coeffs cf);
100 BOOLEAN ntIsMOne(number a, const coeffs cf);
101 BOOLEAN ntIsZero(number a, const coeffs cf);
102 number ntInit(long i, const coeffs cf);
103 long ntInt(number &a, const coeffs cf);
104 number ntNeg(number a, const coeffs cf);
105 number ntInvers(number a, const coeffs cf);
106 number ntAdd(number a, number b, const coeffs cf);
107 number ntSub(number a, number b, const coeffs cf);
108 number ntMult(number a, number b, const coeffs cf);
109 number ntDiv(number a, number b, const coeffs cf);
110 void ntPower(number a, int exp, number *b, const coeffs cf);
111 number ntCopy(number a, const coeffs cf);
112 void ntWriteLong(number a, const coeffs cf);
113 void ntWriteShort(number a, const coeffs cf);
114 number ntRePart(number a, const coeffs cf);
115 number ntImPart(number a, const coeffs cf);
116 number ntGetDenom(number &a, const coeffs cf);
117 number ntGetNumerator(number &a, const coeffs cf);
118 number ntGcd(number a, number b, const coeffs cf);
119 number ntNormalizeHelper(number a, number b, const coeffs cf);
120 int ntSize(number a, const coeffs cf);
121 void ntDelete(number * a, const coeffs cf);
122 void ntCoeffWrite(const coeffs cf, BOOLEAN details);
123 const char * ntRead(const char *s, number *a, const coeffs cf);
124 static BOOLEAN ntCoeffIsEqual(const coeffs cf, n_coeffType n, void * param);
125 
126 void heuristicGcdCancellation(number a, const coeffs cf);
127 void definiteGcdCancellation(number a, const coeffs cf,
128  BOOLEAN simpleTestsHaveAlreadyBeenPerformed);
129 void handleNestedFractionsOverQ(fraction f, const coeffs cf);
130 
131 /* test routine, usualy disabled *
132  * if want to activate it, activate also the calls to check_N *
133  *
134 void check_normalized(number t,const coeffs cf, const char *f, int l)
135 {
136  if (IS0(t)) return;
137  if(rField_is_Q(ntRing))
138  {
139  poly pp=NUM(t);
140  while(pp!=NULL)
141  {
142  if (((SR_HDL(pGetCoeff(pp)) & SR_INT)==0)&&(SR_HDL(pGetCoeff(pp))!=NULL))
143  {
144  if (pGetCoeff(pp)->s==0)
145  {
146  Print("NUM not normalized in %s:%d\n",f,l);
147  p_Normalize(pp,ntRing);
148  }
149  else if (pGetCoeff(pp)->s==1)
150  Print("NUM is rational in %s:%d\n",f,l);
151  }
152  pIter(pp);
153  }
154  pp=DEN(t);
155  while(pp!=NULL)
156  {
157  if (((SR_HDL(pGetCoeff(pp)) & SR_INT)==0)&&(SR_HDL(pGetCoeff(pp))!=NULL))
158  {
159  if (pGetCoeff(pp)->s==0)
160  {
161  Print("NUM not normalized in %s:%d\n",f,l);
162  p_Normalize(pp,ntRing);
163  }
164  else if (pGetCoeff(pp)->s==1)
165  Print("DEN is rational in %s:%d\n",f,l);
166  }
167  pIter(pp);
168  }
169  }
170 }
171 #define check_N(A,B) check_normalized(A,B,__FILE__,__LINE__)
172 */
173 
174 #ifdef LDEBUG
175 BOOLEAN ntDBTest(number a, const char *f, const int l, const coeffs cf)
176 {
177  assume(getCoeffType(cf) == ID);
178 
179  if (IS0(a)) return TRUE;
180 
181  const fraction t = (fraction)a;
182 
183  //check_N(a,cf);
184  const poly num = NUM(t);
185  assume(num != NULL); ///< t != 0 ==> numerator(t) != 0
186 
187  p_Test(num, ntRing);
188 
189  if (getCoeffType(ntCoeffs)==n_Q)
190  for( poly p = num; p != NULL; pIter(p) )
191  if (! nlIsInteger( p_GetCoeff(p, ntRing), ntCoeffs) )
192  {
193  Print("ERROR in %s:%d: non-integer Q coeff in num. poly\n",f,l);
194  Print("TERM: "); p_wrp(p, ntRing); PrintLn();
195  return FALSE;
196  }
197 
198  const poly den = DEN(t);
199 
200  if (den != NULL) // !DENIS1(f)
201  {
202  p_Test(den, ntRing);
203 
204  if (getCoeffType(ntCoeffs)==n_Q)
205  for( poly p = den; p != NULL; pIter(p) )
206  if (! nlIsInteger( p_GetCoeff(p, ntRing), ntCoeffs) )
207  {
208  Print("ERROR in %s:%d: non-integer Q coeff in den. poly\n",f,l);
209  Print("TERM: "); p_wrp(p, ntRing); PrintLn();
210  return FALSE;
211  }
212 
213  if (getCoeffType(ntCoeffs)==n_Zp)
214  {
215  if( p_IsConstant(den, ntRing) )
216  {
217  Print("ERROR in %s:%d: constant den. poly / Zp\n",f,l);
218  Print("NUM: "); p_Write(num, ntRing);
219  Print("DEN: "); p_Write(den, ntRing);
220  return FALSE;
221  }
222 
223  if( !n_IsOne(pGetCoeff(den), ntCoeffs) )
224  {
225  Print("ERROR in %s:%d: non-monic den. poly / Zp\n",f,l);
226  Print("NUM: "); p_Write(num, ntRing);
227  Print("DEN: "); p_Write(den, ntRing);
228  return FALSE;
229  }
230  }
231 
232  if (COM(t)==0)
233  {
234  poly gcd = singclap_gcd_r( num, den, ntRing );
235  if( !p_IsOne(gcd, ntRing) )
236  {
237  Print("ERROR in %s:%d: 1 != GCD between num. & den. poly\n",f,l);
238  Print("GCD: "); p_Write(gcd, ntRing);
239  Print("NUM: "); p_Write(num, ntRing);
240  Print("DEN: "); p_Write(den, ntRing);
241  return FALSE;
242  }
243  p_Delete( &gcd, ntRing );
244  }
245  return TRUE;
246 
247 
248 
249  if(p_IsConstant(den, ntRing) && (n_IsOne(pGetCoeff(den), ntCoeffs)))
250  {
251  Print("?/1 in %s:%d\n",f,l);
252  return FALSE;
253  }
254  if( !n_GreaterZero(pGetCoeff(den), ntCoeffs) )
255  {
256  Print("negative sign of DEN. of a fraction in %s:%d\n",f,l);
257  return FALSE;
258  }
259  // test that den is over integers!?
260  }
261  else
262  {
263  return TRUE;
264 
265  // num != NULL // den == NULL
266 // if( COM(t) != 0 )
267 // {
268 // Print("?//NULL with non-zero complexity: %d in %s:%d\n", COM(t), f, l);
269 // return FALSE;
270 // }
271  // test that nume is over integers!?
272  }
273  if (getCoeffType(ntCoeffs)==n_Q)
274  {
275  poly p=num; // !=NULL
276  do
277  {
278  number n=pGetCoeff(p);
279  n_Test(n,ntCoeffs);
280  if ((!(SR_HDL(n) & SR_INT))&&(n->s==0))
281  /* not normalized, just do for the following test*/
282  {
284  n=pGetCoeff(p);
285  }
286  if (!(SR_HDL(n) & SR_INT))
287  {
288  if (n->s<2)
289  Print("rational coeff in num: %s:%d\n",f,l);
290  }
291  pIter(p);
292  } while(p!=NULL);
293  p=den;
294  while(p!=NULL)
295  {
296  number n=pGetCoeff(p);
297  if (!(SR_HDL(n) & SR_INT))
298  {
299  if (n->s!=3)
300  Print("rational coeff in den.:%s:%d\n",f,l);
301  }
302  pIter(p);
303  }
304  }
305  return TRUE;
306 }
307 #endif
308 
309 /* returns the bottom field in this field extension tower; if the tower
310  is flat, i.e., if there is no extension, then r itself is returned;
311  as a side-effect, the counter 'height' is filled with the height of
312  the extension tower (in case the tower is flat, 'height' is zero) */
313 static coeffs nCoeff_bottom(const coeffs r, int &height)
314 {
315  assume(r != NULL);
316  coeffs cf = r;
317  height = 0;
318  while (nCoeff_is_Extension(cf))
319  {
320  assume(cf->extRing != NULL); assume(cf->extRing->cf != NULL);
321  cf = cf->extRing->cf;
322  height++;
323  }
324  return cf;
325 }
326 
327 BOOLEAN ntIsZero(number a, const coeffs cf)
328 {
329  //check_N(a,cf);
330  ntTest(a); // !!!
331  return (IS0(a));
332 }
333 
334 void ntDelete(number * a, const coeffs cf)
335 {
336  //check_N(*a,cf);
337  ntTest(*a); // !!!
338 
339  fraction f = (fraction)(*a);
340  if (IS0(f)) return;
341  p_Delete(&NUM(f), ntRing);
342  if (!DENIS1(f)) p_Delete(&DEN(f), ntRing);
344  *a = NULL;
345 }
346 
347 BOOLEAN ntEqual(number a, number b, const coeffs cf)
348 {
349  //check_N(a,cf);
350  //check_N(b,cf);
351  ntTest(a);
352  ntTest(b);
353 
354  /// simple tests
355  if (a == b) return TRUE;
356  if ((IS0(a)) && (!IS0(b))) return FALSE;
357  if ((IS0(b)) && (!IS0(a))) return FALSE;
358 
359  /// cheap test if gcd's have been cancelled in both numbers
360  fraction fa = (fraction)a;
361  fraction fb = (fraction)b;
362  if ((COM(fa) == 1) && (COM(fb) == 1))
363  {
364  poly f = p_Add_q(p_Copy(NUM(fa), ntRing),
365  p_Neg(p_Copy(NUM(fb), ntRing), ntRing),
366  ntRing);
367  if (f != NULL) { p_Delete(&f, ntRing); return FALSE; }
368  if (DENIS1(fa) && DENIS1(fb)) return TRUE;
369  if (DENIS1(fa) && !DENIS1(fb)) return FALSE;
370  if (!DENIS1(fa) && DENIS1(fb)) return FALSE;
371  f = p_Add_q(p_Copy(DEN(fa), ntRing),
372  p_Neg(p_Copy(DEN(fb), ntRing), ntRing),
373  ntRing);
374  if (f != NULL) { p_Delete(&f, ntRing); return FALSE; }
375  return TRUE;
376  }
377 
378  /* default: the more expensive multiplication test
379  a/b = c/d <==> a*d = b*c */
380  poly f = p_Copy(NUM(fa), ntRing);
381  if (!DENIS1(fb)) f = p_Mult_q(f, p_Copy(DEN(fb), ntRing), ntRing);
382  poly g = p_Copy(NUM(fb), ntRing);
383  if (!DENIS1(fa)) g = p_Mult_q(g, p_Copy(DEN(fa), ntRing), ntRing);
384  poly h = p_Add_q(f, p_Neg(g, ntRing), ntRing);
385  if (h == NULL) return TRUE;
386  else
387  {
388  p_Delete(&h, ntRing);
389  return FALSE;
390  }
391 }
392 
393 number ntCopy(number a, const coeffs cf)
394 {
395  //check_N(a,cf);
396  ntTest(a); // !!!
397  if (IS0(a)) return NULL;
398  fraction f = (fraction)a;
399  poly g = NUM(f);
400  poly h = NULL;
401  h =DEN(f);
402  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
403  NUM(result) = p_Copy(g,cf->extRing);
404  DEN(result) = p_Copy(h,cf->extRing);
405  COM(result) = COM(f);
406  ntTest((number)result);
407  return (number)result;
408 }
409 
410 /// TODO: normalization of a!?
411 number ntGetNumerator(number &a, const coeffs cf)
412 {
413  //check_N(a,cf);
414  ntTest(a);
415  if (IS0(a)) return NULL;
416 
418 
419  fraction f = (fraction)a;
420  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
421 
422  const BOOLEAN denis1= DENIS1 (f);
423 
424  if (getCoeffType (ntCoeffs) == n_Q && !denis1)
426 
427  if (getCoeffType (ntCoeffs) == n_Q && denis1)
428  {
429  assume( DEN (f) == NULL );
430 
431  number g;
432  // TODO/NOTE: the following should not be necessary (due to
433  // Hannes!) as NUM (f) should be over Z!!!
434  CPolyCoeffsEnumerator itr(NUM(f));
435 
436 
437  n_ClearDenominators(itr, g, ntCoeffs);
438 
439  if( !n_GreaterZero(g, ntCoeffs) )
440  {
441  NUM (f) = p_Neg(NUM (f), ntRing);
442  g = n_InpNeg(g, ntCoeffs);
443  }
444 
445  // g should be a positive integer now!
447 
448  if( !n_IsOne(g, ntCoeffs) )
449  {
450  DEN (f) = p_NSet(g, ntRing);
451  COM (f) ++;
452  assume( DEN (f) != NULL );
453  }
454  else
455  n_Delete(&g, ntCoeffs);
456 
457  ntTest(a);
458  }
459 
460  // Call ntNormalize instead of above?!?
461 
462  NUM (result) = p_Copy (NUM (f), ntRing); // ???
463  //DEN (result) = NULL; // done by ..Alloc0..
464  //COM (result) = 0; // done by ..Alloc0..
465 
466  ntTest((number)result);
467  //check_N((number)result,cf);
468  return (number)result;
469 }
470 
471 /// TODO: normalization of a!?
472 number ntGetDenom(number &a, const coeffs cf)
473 {
474  //check_N(a,cf);
475  ntTest(a);
476 
477  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
478  //DEN (result)= NULL; // done by ..Alloc0..
479  //COM (result)= 0; // done by ..Alloc0..
480 
481  if (IS0(a))
482  {
483  NUM (result) = p_One(ntRing);
484  return (number)result;
485  }
486 
488 
489  fraction f = (fraction)a;
490 
491  assume( !IS0(f) );
492 
493  const BOOLEAN denis1 = DENIS1 (f);
494 
495  if( denis1 && (getCoeffType (ntCoeffs) != n_Q) ) // */1 or 0
496  {
497  NUM (result)= p_One(ntRing);
498  ntTest((number)result);
499  return (number)result;
500  }
501 
502  if (!denis1) // */* / Q
503  {
504  assume( DEN (f) != NULL );
505 
506  if (getCoeffType (ntCoeffs) == n_Q)
508 
509  ntTest(a);
510 
511  if( DEN (f) != NULL ) // is it ?? // 1 now???
512  {
513  assume( !p_IsOne(DEN (f), ntRing) );
514 
515  NUM (result) = p_Copy (DEN (f), ntRing);
516  ntTest((number)result);
517  return (number)result;
518  }
519 // NUM (result) = p_One(ntRing); // NOTE: just in order to be sure...
520  }
521 
522  // */1 / Q
524  assume( DEN (f) == NULL );
525 
526  number g;
527 // poly num= p_Copy (NUM (f), ntRing); // ???
528 
529 
530  // TODO/NOTE: the following should not be necessary (due to
531  // Hannes!) as NUM (f) should be over Z!!!
532  CPolyCoeffsEnumerator itr(NUM(f));
533 
534  n_ClearDenominators(itr, g, ntCoeffs); // may return -1 :(((
535 
536  if( !n_GreaterZero(g, ntCoeffs) )
537  {
538 // NUM (f) = p_Neg(NUM (f), ntRing); // Ugly :(((
539 // g = n_InpNeg(g, ntCoeffs);
540  NUM (f) = p_Neg(NUM (f), ntRing); // Ugly :(((
541  g = n_InpNeg(g, ntCoeffs);
542  }
543 
544  // g should be a positive integer now!
546 
547  if( !n_IsOne(g, ntCoeffs) )
548  {
550  assume( !n_IsOne(g, ntCoeffs) );
551 
552  DEN (f) = p_NSet(g, ntRing); // update COM(f)???
553  assume( DEN (f) != NULL );
554  COM (f) ++;
555 
556  NUM (result)= p_Copy (DEN (f), ntRing);
557  }
558  else
559  { // common denom == 1?
560  NUM (result)= p_NSet(g, ntRing); // p_Copy (DEN (f), ntRing);
561 // n_Delete(&g, ntCoeffs);
562  }
563 
564 // if (!p_IsConstant (num, ntRing) && pNext(num) != NULL)
565 // else
566 // g= p_GetAllDenom (num, ntRing);
567 // result= (fraction) ntSetMap (ntCoeffs, cf) (g, ntCoeffs, cf);
568 
569  ntTest((number)result);
570  //check_N((number)result,cf);
571  return (number)result;
572 }
573 
574 BOOLEAN ntIsOne(number a, const coeffs cf)
575 {
576  //check_N(a,cf);
577  ntTest(a); // !!!
579  fraction f = (fraction)a;
580  return (f!=NULL) && DENIS1(f) && NUMIS1(f);
581 }
582 
583 BOOLEAN ntIsMOne(number a, const coeffs cf)
584 {
585  //check_N(a,cf);
586  ntTest(a);
588  fraction f = (fraction)a;
589  if ((f==NULL) || (!DENIS1(f))) return FALSE;
590  poly g = NUM(f);
591  if (!p_IsConstant(g, ntRing)) return FALSE;
592  return n_IsMOne(p_GetCoeff(g, ntRing), ntCoeffs);
593 }
594 
595 /// this is in-place, modifies a
596 number ntNeg(number a, const coeffs cf)
597 {
598  //check_N(a,cf);
599  ntTest(a);
600  if (!IS0(a))
601  {
602  fraction f = (fraction)a;
603  NUM(f) = p_Neg(NUM(f), ntRing);
604  }
605  ntTest(a);
606  return a;
607 }
608 
609 number ntImPart(number a, const coeffs cf)
610 {
611  ntTest(a);
612  return NULL;
613 }
614 
615 number ntInit(long i, const coeffs cf)
616 {
617  if (i != 0)
618  {
619  poly p=p_ISet(i, ntRing);
620  if (p!=NULL)
621  {
622  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
623  NUM(result) = p;
624  //DEN(result) = NULL; // done by omAlloc0Bin
625  //COM(result) = 0; // done by omAlloc0Bin
626  ntTest((number)result);
627  //check_N((number)result,cf);
628  return (number)result;
629  }
630  }
631  return NULL;
632 }
633 
634 
635 /// takes over p!
636 number ntInit(poly p, const coeffs cf)
637 {
638  if (p == NULL) return NULL;
639 
640  p_Test( p, ntRing);
641  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
642 
643  if (nCoeff_is_Q(ntCoeffs))
644  {
645  number g;
646  // the following is necessary because
647  // NUM (f) should be over Z,
648  // while p may be over Q
649  CPolyCoeffsEnumerator itr(p);
650 
651  n_ClearDenominators(itr, g, ntCoeffs);
652 
653  if( !n_GreaterZero(g, ntCoeffs) )
654  {
655  p = p_Neg(p, ntRing);
656  g = n_InpNeg(g, ntCoeffs);
657  }
658 
659  // g should be a positive integer now!
661 
662  if( !n_IsOne(g, ntCoeffs) )
663  {
664  DEN (f) = p_NSet(g, ntRing);
665  p_Normalize(DEN(f), ntRing);
666  assume( DEN (f) != NULL );
667  }
668  else
669  {
670  //DEN(f) = NULL; // done by omAlloc0
671  n_Delete(&g, ntCoeffs);
672  }
673  }
674 
675  p_Normalize(p, ntRing);
676  NUM(f) = p;
677  //COM(f) = 0; // done by omAlloc0
678 
679  //check_N((number)f,cf);
680  ntTest((number)f);
681  return (number)f;
682 }
683 
684 long ntInt(number &a, const coeffs cf)
685 {
686  //check_N(a,cf);
687  ntTest(a);
688  if (IS0(a)) return 0;
690  fraction f = (fraction)a;
691  if (!DENIS1(f)) return 0;
692 
693  const poly aAsPoly = NUM(f);
694 
695  if(aAsPoly == NULL)
696  return 0;
697 
698  if (!p_IsConstant(aAsPoly, ntRing))
699  return 0;
700 
701  assume( aAsPoly != NULL );
702 
703  return n_Int(p_GetCoeff(aAsPoly, ntRing), ntCoeffs);
704 }
705 
706 /* This method will only consider the numerators of a and b, without
707  cancelling gcd's before.
708  Moreover it may return TRUE only if one or both numerators
709  are zero or if their degrees are equal. Then TRUE is returned iff
710  coeff(numerator(a)) > coeff(numerator(b));
711  In all other cases, FALSE will be returned. */
712 BOOLEAN ntGreater(number a, number b, const coeffs cf)
713 {
714  //check_N(a,cf);
715  //check_N(b,cf);
716  ntTest(a);
717  ntTest(b);
718  number aNumCoeff = NULL; int aNumDeg = 0;
719  number aDenCoeff = NULL; int aDenDeg = 0;
720  number bNumCoeff = NULL; int bNumDeg = 0;
721  number bDenCoeff = NULL; int bDenDeg = 0;
722  if (!IS0(a))
723  {
724  fraction fa = (fraction)a;
725  aNumDeg = p_Totaldegree(NUM(fa), ntRing);
726  aNumCoeff = p_GetCoeff(NUM(fa), ntRing);
727  if (DEN(fa)!=NULL)
728  {
729  aDenDeg = p_Totaldegree(DEN(fa), ntRing);
730  aDenCoeff=p_GetCoeff(DEN(fa),ntRing);
731  }
732  }
733  else return !(ntGreaterZero (b,cf));
734  if (!IS0(b))
735  {
736  fraction fb = (fraction)b;
737  bNumDeg = p_Totaldegree(NUM(fb), ntRing);
738  bNumCoeff = p_GetCoeff(NUM(fb), ntRing);
739  if (DEN(fb)!=NULL)
740  {
741  bDenDeg = p_Totaldegree(DEN(fb), ntRing);
742  bDenCoeff=p_GetCoeff(DEN(fb),ntRing);
743  }
744  }
745  else return ntGreaterZero(a,cf);
746  if (aNumDeg-aDenDeg > bNumDeg-bDenDeg) return TRUE;
747  if (aNumDeg-aDenDeg < bNumDeg-bDenDeg) return FALSE;
748  number aa;
749  number bb;
750  if (bDenCoeff==NULL) aa=n_Copy(aNumCoeff,ntCoeffs);
751  else aa=n_Mult(aNumCoeff,bDenCoeff,ntCoeffs);
752  if (aDenCoeff==NULL) bb=n_Copy(bNumCoeff,ntCoeffs);
753  else bb=n_Mult(bNumCoeff,aDenCoeff,ntCoeffs);
754  BOOLEAN rr= n_Greater(aa, bb, ntCoeffs);
755  n_Delete(&aa,ntCoeffs);
756  n_Delete(&bb,ntCoeffs);
757  return rr;
758 }
759 
760 /* this method will only consider the numerator of a, without cancelling
761  the gcd before;
762  returns TRUE iff the leading coefficient of the numerator of a is > 0
763  or the leading term of the numerator of a is not a
764  constant */
766 {
767  //check_N(a,cf);
768  ntTest(a);
769  if (IS0(a)) return FALSE;
770  fraction f = (fraction)a;
771  poly g = NUM(f);
773 }
774 
775 void ntCoeffWrite(const coeffs cf, BOOLEAN details)
776 {
777  assume( cf != NULL );
778 
779  const ring A = cf->extRing;
780 
781  assume( A != NULL );
782  assume( A->cf != NULL );
783 
784  n_CoeffWrite(A->cf, details);
785 
786 // rWrite(A);
787 
788  const int P = rVar(A);
789  assume( P > 0 );
790 
791  Print("// %d parameter : ", P);
792 
793  for (int nop=0; nop < P; nop ++)
794  Print("%s ", rRingVar(nop, A));
795 
796  assume( A->qideal == NULL );
797 
798  PrintS("\n// minpoly : 0\n");
799 
800 /*
801  PrintS("// Coefficients live in the rational function field\n");
802  Print("// K(");
803  for (int i = 0; i < rVar(ntRing); i++)
804  {
805  if (i > 0) PrintS(" ");
806  Print("%s", rRingVar(i, ntRing));
807  }
808  PrintS(") with\n");
809  PrintS("// K: "); n_CoeffWrite(cf->extRing->cf);
810 */
811 }
812 
813 number ntDiff(number a, number d, const coeffs cf)
814 {
815  //check_N(a,cf);
816  //check_N(d,cf);
817  ntTest(a);
818  ntTest(d);
819 
820  if (IS0(d))
821  {
822  WerrorS("ringvar expected");
823  return NULL;
824  }
825  fraction t = (fraction) d;
826  if (!DENIS1(t))
827  {
828  WerrorS("expected differentiation by a variable");
829  return NULL;
830  }
831  int k=p_Var(NUM(t),ntRing);
832  if (k==0)
833  {
834  WerrorS("expected differentiation by a variable");
835  return NULL;
836  }
837 
838  if (IS0(a)) return ntCopy(a, cf);
839 
840  fraction fa = (fraction)a;
841  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
842  if (DENIS1(fa))
843  {
844  NUM(result) = p_Diff(NUM(fa),k,ntRing);
845  //DEN(result) = NULL; // done by ..Alloc0..
846  if (NUM(result)==NULL)
847  {
849  return(NULL);
850  }
851  COM(result) = COM(fa);
852  //check_N((number)result,cf);
853  ntTest((number)result);
854  return (number)result;
855  }
856 
857  poly fg = p_Mult_q(p_Copy(DEN(fa),ntRing),p_Diff(NUM(fa),k,ntRing),ntRing);
858  poly gf = p_Mult_q(p_Copy(NUM(fa),ntRing),p_Diff(DEN(fa),k,ntRing),ntRing);
859  NUM(result) = p_Sub(fg,gf,ntRing);
860  if (NUM(result)==NULL) return(NULL);
861  DEN(result) = pp_Mult_qq(DEN(fa), DEN(fa), ntRing);
862  COM(result) = COM(fa) + COM(fa) + DIFF_COMPLEXITY;
863  heuristicGcdCancellation((number)result, cf);
864 
865  //check_N((number)result,cf);
866  ntTest((number)result);
867  return (number)result;
868 }
869 
870 
871 number ntAdd(number a, number b, const coeffs cf)
872 {
873  //check_N(a,cf);
874  //check_N(b,cf);
875  ntTest(a);
876  ntTest(b);
877  if (IS0(a)) return ntCopy(b, cf);
878  if (IS0(b)) return ntCopy(a, cf);
879 
880  fraction fa = (fraction)a;
881  fraction fb = (fraction)b;
882 
883  poly g = p_Copy(NUM(fa), ntRing);
884  if (!DENIS1(fb)) g = p_Mult_q(g, p_Copy(DEN(fb), ntRing), ntRing);
885  poly h = p_Copy(NUM(fb), ntRing);
886  if (!DENIS1(fa)) h = p_Mult_q(h, p_Copy(DEN(fa), ntRing), ntRing);
887  g = p_Add_q(g, h, ntRing);
888 
889  if (g == NULL) return NULL;
890 
891  poly f;
892  if (DENIS1(fa) && DENIS1(fb)) f = NULL;
893  else if (!DENIS1(fa) && DENIS1(fb)) f = p_Copy(DEN(fa), ntRing);
894  else if (DENIS1(fa) && !DENIS1(fb)) f = p_Copy(DEN(fb), ntRing);
895  else /* both denom's are != 1 */ f = p_Mult_q(p_Copy(DEN(fa), ntRing),
896  p_Copy(DEN(fb), ntRing),
897  ntRing);
898 
899  fraction result = (fraction)omAllocBin(fractionObjectBin);
900  NUM(result) = g;
901  DEN(result) = f;
902  COM(result) = COM(fa) + COM(fb) + ADD_COMPLEXITY;
903  heuristicGcdCancellation((number)result, cf);
904 
905 // ntTest((number)result);
906 
907  //check_N((number)result,cf);
908  ntTest((number)result);
909  return (number)result;
910 }
911 
912 number ntSub(number a, number b, const coeffs cf)
913 {
914  //check_N(a,cf);
915  //check_N(b,cf);
916  ntTest(a);
917  ntTest(b);
918  if (IS0(a)) return ntNeg(ntCopy(b, cf), cf);
919  if (IS0(b)) return ntCopy(a, cf);
920 
921  fraction fa = (fraction)a;
922  fraction fb = (fraction)b;
923 
924  poly g = p_Copy(NUM(fa), ntRing);
925  if (!DENIS1(fb)) g = p_Mult_q(g, p_Copy(DEN(fb), ntRing), ntRing);
926  poly h = p_Copy(NUM(fb), ntRing);
927  if (!DENIS1(fa)) h = p_Mult_q(h, p_Copy(DEN(fa), ntRing), ntRing);
928  g = p_Add_q(g, p_Neg(h, ntRing), ntRing);
929 
930  if (g == NULL) return NULL;
931 
932  poly f;
933  if (DENIS1(fa) && DENIS1(fb)) f = NULL;
934  else if (!DENIS1(fa) && DENIS1(fb)) f = p_Copy(DEN(fa), ntRing);
935  else if (DENIS1(fa) && !DENIS1(fb)) f = p_Copy(DEN(fb), ntRing);
936  else /* both den's are != 1 */ f = p_Mult_q(p_Copy(DEN(fa), ntRing),
937  p_Copy(DEN(fb), ntRing),
938  ntRing);
939 
940  fraction result = (fraction)omAllocBin(fractionObjectBin);
941  NUM(result) = g;
942  DEN(result) = f;
943  COM(result) = COM(fa) + COM(fb) + ADD_COMPLEXITY;
944  heuristicGcdCancellation((number)result, cf);
945 // ntTest((number)result);
946  //check_N((number)result,cf);
947  ntTest((number)result);
948  return (number)result;
949 }
950 
951 number ntMult(number a, number b, const coeffs cf)
952 {
953  //check_N(a,cf);
954  //check_N(b,cf);
955  ntTest(a); // !!!?
956  ntTest(b); // !!!?
957 
958  if (IS0(a) || IS0(b)) return NULL;
959 
960  fraction fa = (fraction)a;
961  fraction fb = (fraction)b;
962 
963  const poly g = pp_Mult_qq(NUM(fa), NUM(fb), ntRing);
964 
965  if (g == NULL) return NULL; // may happen due to zero divisors???
966 
967  fraction result = (fraction)omAllocBin(fractionObjectBin);
968 
969  NUM(result) = g;
970 
971  const poly da = DEN(fa);
972  const poly db = DEN(fb);
973 
974 
975  //check_N((number)result,cf);
976  if (db == NULL)
977  {
978  // b = ? // NULL
979 
980  if(da == NULL)
981  { // both fa && fb are ?? // NULL!
982  assume (da == NULL && db == NULL);
983  DEN(result) = NULL;
984  COM(result) = 0;
985  }
986  else
987  {
988  assume (da != NULL && db == NULL);
989  DEN(result) = p_Copy(da, ntRing);
990  COM(result) = COM(fa) + MULT_COMPLEXITY;
991  heuristicGcdCancellation((number)result, cf);
992  //check_N((number)result,cf);
993  }
994  }
995  else
996  { // b = ?? / ??
997  if (da == NULL)
998  { // a == ? // NULL
999  assume( db != NULL && da == NULL);
1000  DEN(result) = p_Copy(db, ntRing);
1001  COM(result) = COM(fb) + MULT_COMPLEXITY;
1002  heuristicGcdCancellation((number)result, cf);
1003  //check_N((number)result,cf);
1004  }
1005  else /* both den's are != 1 */
1006  {
1007  assume (da != NULL && db != NULL);
1008  DEN(result) = pp_Mult_qq(da, db, ntRing);
1009  COM(result) = COM(fa) + COM(fb) + MULT_COMPLEXITY;
1010  heuristicGcdCancellation((number)result, cf);
1011  //check_N((number)result,cf);
1012  }
1013  }
1014 
1015 // ntTest((number)result);
1016 
1017  //check_N((number)result,cf);
1018  ntTest((number)result);
1019  return (number)result;
1020 }
1021 
1022 number ntDiv(number a, number b, const coeffs cf)
1023 {
1024  //check_N(a,cf);
1025  //check_N(b,cf);
1026  ntTest(a);
1027  ntTest(b);
1028  if (IS0(a)) return NULL;
1029  if (IS0(b)) WerrorS(nDivBy0);
1030 
1031  fraction fa = (fraction)a;
1032  fraction fb = (fraction)b;
1033 
1034  poly g = p_Copy(NUM(fa), ntRing);
1035  if (!DENIS1(fb)) g = p_Mult_q(g, p_Copy(DEN(fb), ntRing), ntRing);
1036 
1037  if (g == NULL) return NULL; /* may happen due to zero divisors */
1038 
1039  poly f = p_Copy(NUM(fb), ntRing);
1040  if (!DENIS1(fa)) f = p_Mult_q(f, p_Copy(DEN(fa), ntRing), ntRing);
1041 
1042  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1043  NUM(result) = g;
1044  if (!n_GreaterZero(pGetCoeff(f),ntCoeffs))
1045  {
1046  g=p_Neg(g,ntRing);
1047  f=p_Neg(f,ntRing);
1048  NUM(result) = g;
1049  }
1050  if (!p_IsConstant(f,ntRing) || !n_IsOne(pGetCoeff(f),ntCoeffs))
1051  {
1052  DEN(result) = f;
1053  }
1054  COM(result) = COM(fa) + COM(fb) + MULT_COMPLEXITY;
1055 // definiteGcdCancellation((number)result, cf,FALSE);
1056  heuristicGcdCancellation((number)result, cf);
1057 // ntTest((number)result);
1058  //check_N((number)result,cf);
1059  ntTest((number)result);
1060  return (number)result;
1061 }
1062 
1063 /* 0^0 = 0;
1064  for |exp| <= 7 compute power by a simple multiplication loop;
1065  for |exp| >= 8 compute power along binary presentation of |exp|, e.g.
1066  p^13 = p^1 * p^4 * p^8, where we utilise that
1067  p^(2^(k+1)) = p^(2^k) * p^(2^k);
1068  intermediate cancellation is controlled by the in-place method
1069  heuristicGcdCancellation; see there.
1070 */
1071 void ntPower(number a, int exp, number *b, const coeffs cf)
1072 {
1073  ntTest(a);
1074 
1075  /* special cases first */
1076  if (IS0(a))
1077  {
1078  if (exp >= 0) *b = NULL;
1079  else WerrorS(nDivBy0);
1080  }
1081  else if (exp == 0) { *b = ntInit(1, cf); return;}
1082  else if (exp == 1) { *b = ntCopy(a, cf); return;}
1083  else if (exp == -1) { *b = ntInvers(a, cf); return;}
1084 
1085  int expAbs = exp; if (expAbs < 0) expAbs = -expAbs;
1086 
1087  /* now compute a^expAbs */
1088  number pow; number t;
1089  if (expAbs <= 7)
1090  {
1091  pow = ntCopy(a, cf);
1092  for (int i = 2; i <= expAbs; i++)
1093  {
1094  t = ntMult(pow, a, cf);
1095  ntDelete(&pow, cf);
1096  pow = t;
1097  heuristicGcdCancellation(pow, cf);
1098  }
1099  }
1100  else
1101  {
1102  pow = ntInit(1, cf);
1103  number factor = ntCopy(a, cf);
1104  while (expAbs != 0)
1105  {
1106  if (expAbs & 1)
1107  {
1108  t = ntMult(pow, factor, cf);
1109  ntDelete(&pow, cf);
1110  pow = t;
1111  heuristicGcdCancellation(pow, cf);
1112  }
1113  expAbs = expAbs / 2;
1114  if (expAbs != 0)
1115  {
1116  t = ntMult(factor, factor, cf);
1117  ntDelete(&factor, cf);
1118  factor = t;
1119  heuristicGcdCancellation(factor, cf);
1120  }
1121  }
1122  ntDelete(&factor, cf);
1123  }
1124 
1125  /* invert if original exponent was negative */
1126  if (exp < 0)
1127  {
1128  t = ntInvers(pow, cf);
1129  ntDelete(&pow, cf);
1130  pow = t;
1131  }
1132  *b = pow;
1133  ntTest(*b);
1134  //check_N(*b,cf);
1135 }
1136 
1137 /* assumes that cf represents the rationals, i.e. Q, and will only
1138  be called in that case;
1139  assumes furthermore that f != NULL and that the denominator of f != 1;
1140  generally speaking, this method removes denominators in the rational
1141  coefficients of the numerator and denominator of 'a';
1142  more concretely, the following normalizations will be performed,
1143  where t^alpha denotes a monomial in the transcendental variables t_k
1144  (1) if 'a' is of the form
1145  (sum_alpha a_alpha/b_alpha * t^alpha)
1146  -------------------------------------
1147  (sum_beta c_beta/d_beta * t^beta)
1148  with integers a_alpha, b_alpha, c_beta, d_beta, then both the
1149  numerator and the denominator will be multiplied by the LCM of
1150  the b_alpha's and the d_beta's (if this LCM is != 1),
1151  (2) if 'a' is - e.g. after having performed step (1) - of the form
1152  (sum_alpha a_alpha * t^alpha)
1153  -----------------------------
1154  (sum_beta c_beta * t^beta)
1155  with integers a_alpha, c_beta, and with a non-constant denominator,
1156  then both the numerator and the denominator will be divided by the
1157  GCD of the a_alpha's and the c_beta's (if this GCD is != 1),
1158  this procedure does not alter COM(f) (this has to be done by the
1159  calling procedure);
1160  modifies f */
1161 void handleNestedFractionsOverQ(fraction f, const coeffs cf)
1162 {
1164  assume(!IS0(f));
1165  assume(!DENIS1(f));
1166 
1167  { /* step (1); see documentation of this procedure above */
1168  number lcmOfDenominators = n_Init(1, ntCoeffs);
1169  number c; number tmp;
1170  poly p = NUM(f);
1171  /* careful when using n_NormalizeHelper!!! It computes the lcm of the numerator
1172  of the 1st argument and the denominator of the 2nd!!! */
1173  while (p != NULL)
1174  {
1175  c = p_GetCoeff(p, ntRing);
1176  tmp = n_NormalizeHelper(lcmOfDenominators, c, ntCoeffs);
1177  n_Delete(&lcmOfDenominators, ntCoeffs);
1178  lcmOfDenominators = tmp;
1179  pIter(p);
1180  }
1181  p = DEN(f);
1182  while (p != NULL)
1183  {
1184  c = p_GetCoeff(p, ntRing);
1185  tmp = n_NormalizeHelper(lcmOfDenominators, c, ntCoeffs);
1186  n_Delete(&lcmOfDenominators, ntCoeffs);
1187  lcmOfDenominators = tmp;
1188  pIter(p);
1189  }
1190  if (!n_IsOne(lcmOfDenominators, ntCoeffs))
1191  { /* multiply NUM(f) and DEN(f) with lcmOfDenominators */
1192  NUM(f) = p_Mult_nn(NUM(f), lcmOfDenominators, ntRing);
1193  p_Normalize(NUM(f), ntRing);
1194  DEN(f) = p_Mult_nn(DEN(f), lcmOfDenominators, ntRing);
1195  p_Normalize(DEN(f), ntRing);
1196  }
1197  n_Delete(&lcmOfDenominators, ntCoeffs);
1198  if (DEN(f)!=NULL)
1199  { /* step (2); see documentation of this procedure above */
1200  p = NUM(f);
1201  number gcdOfCoefficients = n_Copy(p_GetCoeff(p, ntRing), ntCoeffs);
1202  pIter(p);
1203  while ((p != NULL) && (!n_IsOne(gcdOfCoefficients, ntCoeffs)))
1204  {
1205  c = p_GetCoeff(p, ntRing);
1206  tmp = n_Gcd(c, gcdOfCoefficients, ntCoeffs);
1207  n_Delete(&gcdOfCoefficients, ntCoeffs);
1208  gcdOfCoefficients = tmp;
1209  pIter(p);
1210  }
1211  p = DEN(f);
1212  while ((p != NULL) && (!n_IsOne(gcdOfCoefficients, ntCoeffs)))
1213  {
1214  c = p_GetCoeff(p, ntRing);
1215  tmp = n_Gcd(c, gcdOfCoefficients, ntCoeffs);
1216  n_Delete(&gcdOfCoefficients, ntCoeffs);
1217  gcdOfCoefficients = tmp;
1218  pIter(p);
1219  }
1220  if (!n_IsOne(gcdOfCoefficients, ntCoeffs))
1221  { /* divide NUM(f) and DEN(f) by gcdOfCoefficients */
1222  number inverseOfGcdOfCoefficients = n_Invers(gcdOfCoefficients,
1223  ntCoeffs);
1224  NUM(f) = p_Mult_nn(NUM(f), inverseOfGcdOfCoefficients, ntRing);
1225  p_Normalize(NUM(f), ntRing);
1226  DEN(f) = p_Mult_nn(DEN(f), inverseOfGcdOfCoefficients, ntRing);
1227  p_Normalize(DEN(f), ntRing);
1228  n_Delete(&inverseOfGcdOfCoefficients, ntCoeffs);
1229  }
1230  n_Delete(&gcdOfCoefficients, ntCoeffs);
1231  }
1232  }
1233 
1234  /* Now, due to the above computations, DEN(f) may have become the
1235  1-polynomial which needs to be represented by NULL: */
1236  if ((DEN(f) != NULL) &&
1237  p_IsConstant(DEN(f), ntRing) &&
1238  n_IsOne(p_GetCoeff(DEN(f), ntRing), ntCoeffs))
1239  {
1240  p_Delete(&DEN(f), ntRing); DEN(f) = NULL;
1241  }
1242 
1243  if( DEN(f) != NULL )
1244  if( !n_GreaterZero(pGetCoeff(DEN(f)), ntCoeffs) )
1245  {
1246  NUM(f) = p_Neg(NUM(f), ntRing);
1247  DEN(f) = p_Neg(DEN(f), ntRing);
1248  }
1249 
1250  ntTest((number)f); // TODO!
1251 }
1252 
1253 /* modifies a */
1254 /* this is an intermediate simplification routine - not a comple "normalize" */
1256 {
1257  if (IS0(a)) return;
1258 
1259  fraction f = (fraction)a;
1260  p_Normalize(NUM(f),ntRing);
1261  if (DENIS1(f) || NUMIS1(f)) { COM(f) = 0; return; }
1262 
1263  assume( DEN(f) != NULL );
1264  p_Normalize(DEN(f),ntRing);
1265 
1266  /* check whether NUM(f) = DEN(f), and - if so - replace 'a' by 1 */
1267  if (p_EqualPolys(NUM(f), DEN(f), ntRing))
1268  { /* numerator and denominator are both != 1 */
1269  p_Delete(&NUM(f), ntRing); NUM(f) = p_ISet(1, ntRing);
1270  p_Delete(&DEN(f), ntRing); DEN(f) = NULL;
1271  COM(f) = 0;
1272  }
1273  else
1274  {
1275  if (COM(f) > BOUND_COMPLEXITY)
1276  definiteGcdCancellation(a, cf, TRUE);
1277 
1278  // TODO: check if it is enough to put the following into definiteGcdCancellation?!
1279  if( DEN(f) != NULL )
1280  {
1281  if( !n_GreaterZero(pGetCoeff(DEN(f)), ntCoeffs) )
1282  {
1283  NUM(f) = p_Neg(NUM(f), ntRing);
1284  DEN(f) = p_Neg(DEN(f), ntRing);
1285  }
1286  if (ntCoeffs->has_simple_Inverse)
1287  {
1288  if (!n_IsOne(pGetCoeff(DEN(f)),ntCoeffs))
1289  {
1290  number inv=n_Invers(pGetCoeff(DEN(f)),ntCoeffs);
1291  DEN(f)=p_Mult_nn(DEN(f),inv,ntRing);
1292  NUM(f)=p_Mult_nn(NUM(f),inv,ntRing);
1293  }
1294  if(p_LmIsConstant(DEN(f),ntRing))
1295  {
1296  p_Delete(&DEN(f),ntRing);
1297  COM(f)=0;
1298  }
1299  }
1300  if ((DEN(f)!=NULL)
1301  && (pNext(DEN(f))==NULL))
1302  {
1303  poly den_f=DEN(f);
1304  poly h=NUM(f);
1305  loop
1306  {
1307  if (h==NULL)
1308  {
1309  h=NUM(f);
1310  do
1311  {
1312  p_ExpVectorDiff(h,h,den_f,ntRing);
1313  pIter(h);
1314  } while(h!=NULL);
1315  p_ExpVectorDiff(den_f,den_f,den_f,ntRing);
1316  break;
1317  }
1318  int i=0;
1319  do
1320  {
1321  i++;
1322  if (p_GetExp(den_f,i,ntRing) > p_GetExp(h,i,ntRing)) return;
1323  } while(i<ntRing->N);
1324  pIter(h);
1325  }
1326  }
1327  }
1328  }
1329 }
1330 
1331 /// modifies a
1332 void definiteGcdCancellation(number a, const coeffs cf,
1333  BOOLEAN simpleTestsHaveAlreadyBeenPerformed)
1334 {
1335 // ntTest(a); // !!!!
1336 
1337  fraction f = (fraction)a;
1338 
1339  if (IS0(a)) return;
1340  if (DENIS1(f) || NUMIS1(f)) { COM(f) = 0; ntTest(a); return; }
1341  if (!simpleTestsHaveAlreadyBeenPerformed)
1342  {
1343 
1344  /* check whether NUM(f) = DEN(f), and - if so - replace 'a' by 1 */
1345  if (p_EqualPolys(NUM(f), DEN(f), ntRing))
1346  { /* numerator and denominator are both != 1 */
1347  p_Delete(&NUM(f), ntRing); NUM(f) = p_ISet(1, ntRing);
1348  p_Delete(&DEN(f), ntRing); DEN(f) = NULL;
1349  COM(f) = 0;
1350  ntTest(a);
1351  return;
1352  }
1353  }
1354  /*if (rField_is_Q(ntRing))
1355  {
1356  number c=n_Copy(pGetCoeff(NUM(f)),ntCoeffs);
1357  poly p=pNext(NUM(f));
1358  while((p!=NULL)&&(!n_IsOne(c,ntCoeffs)))
1359  {
1360  number cc=n_Gcd(c,pGetCoeff(p),ntCoeffs);
1361  n_Delete(&c,ntCoeffs);
1362  c=cc;
1363  pIter(p);
1364  };
1365  p=DEN(f);
1366  while((p!=NULL)&&(!n_IsOne(c,ntCoeffs)))
1367  {
1368  number cc=n_Gcd(c,pGetCoeff(p),ntCoeffs);
1369  n_Delete(&c,ntCoeffs);
1370  c=cc;
1371  pIter(p);
1372  };
1373  if(!n_IsOne(c,ntCoeffs))
1374  {
1375  p=NUM(f);
1376  do
1377  {
1378  number cc=n_Div(pGetCoeff(p),c,ntCoeffs);
1379  n_Normalize(cc,ntCoeffs);
1380  p_SetCoeff(p,cc,ntRing);
1381  pIter(p);
1382  } while(p!=NULL);
1383  p=DEN(f);
1384  do
1385  {
1386  number cc=n_Div(pGetCoeff(p),c,ntCoeffs);
1387  n_Normalize(cc,ntCoeffs);
1388  p_SetCoeff(p,cc,ntRing);
1389  pIter(p);
1390  } while(p!=NULL);
1391  n_Delete(&c,ntCoeffs);
1392  if(pNext(DEN(f))==NULL)
1393  {
1394  if (p_IsOne(DEN(f),ntRing))
1395  {
1396  p_LmDelete(&DEN(f),ntRing);
1397  COM(f)=0;
1398  return;
1399  }
1400  else
1401  {
1402  return;
1403  }
1404  }
1405  }
1406  }*/
1407 
1408  /* here we assume: NUM(f), DEN(f) !=NULL, in Z_a reqp. Z/p_a */
1409  poly pGcd = singclap_gcd_and_divide(NUM(f), DEN(f), ntRing);
1410  //PrintS("gcd= ");p_wrp(pGcd,ntRing);PrintLn();
1411  if (p_IsConstant(pGcd, ntRing)
1412  && n_IsOne(p_GetCoeff(pGcd, ntRing), ntCoeffs)
1413  )
1414  { /* gcd = 1; nothing to cancel;
1415  Suppose the given rational function field is over Q. Although the
1416  gcd is 1, we may have produced fractional coefficients in NUM(f),
1417  DEN(f), or both, due to previous arithmetics. The next call will
1418  remove those nested fractions, in case there are any. */
1419  if (nCoeff_is_Zp(ntCoeffs))
1420  {
1421  NUM (f) = p_Div_nn (NUM (f), p_GetCoeff (DEN(f),ntRing), ntRing);
1422  if (p_IsConstant (DEN (f), ntRing))
1423  {
1424  p_Delete(&DEN (f), ntRing);
1425  DEN (f) = NULL;
1426  }
1427  else
1428  {
1429  p_Norm (DEN (f),ntRing);
1430  }
1431  } else if (nCoeff_is_Q(ntCoeffs)) handleNestedFractionsOverQ(f, cf);
1432  }
1433  else
1434  { /* We divide both NUM(f) and DEN(f) by the gcd which is known
1435  to be != 1. */
1436  if (p_IsConstant(DEN(f), ntRing) &&
1437  n_IsOne(p_GetCoeff(DEN(f), ntRing), ntCoeffs))
1438  {
1439  /* DEN(f) = 1 needs to be represented by NULL! */
1440  p_Delete(&DEN(f), ntRing);
1441  DEN(f) = NULL;
1442  }
1443  else
1444  {
1445  if (nCoeff_is_Zp(ntCoeffs))
1446  {
1447  NUM (f) = p_Div_nn (NUM (f), p_GetCoeff (DEN(f),ntRing), ntRing);
1448  if (p_IsConstant (DEN (f), ntRing))
1449  {
1450  p_Delete(&DEN (f), ntRing);
1451  DEN (f) = NULL;
1452  }
1453  else
1454  {
1455  p_Norm (DEN (f),ntRing);
1456  }
1457  }
1458  }
1459  }
1460  p_Delete(&pGcd, ntRing);
1461  COM(f) = 0;
1462 
1463  if( DEN(f) != NULL )
1464  {
1465  if( !n_GreaterZero(pGetCoeff(DEN(f)), ntCoeffs) )
1466  {
1467  NUM(f) = p_Neg(NUM(f), ntRing);
1468  DEN(f) = p_Neg(DEN(f), ntRing);
1469  if (p_IsConstant(DEN(f), ntRing) &&
1470  n_IsOne(p_GetCoeff(DEN(f), ntRing), ntCoeffs))
1471  {
1472  /* DEN(f) = 1 needs to be represented by NULL! */
1473  p_Delete(&DEN(f), ntRing);
1474  DEN (f) = NULL;
1475  }
1476  }
1477  }
1478  ntTest(a); // !!!!
1479 }
1480 
1481 void ntWriteLong(number a, const coeffs cf)
1482 {
1483  ntTest(a);
1484  if (IS0(a))
1485  StringAppendS("0");
1486  else
1487  {
1488  fraction f = (fraction)a;
1489  // stole logic from napWrite from kernel/longtrans.cc of legacy singular
1490  BOOLEAN omitBrackets = p_IsConstant(NUM(f), ntRing);
1491  if (!omitBrackets) StringAppendS("(");
1492  p_String0Long(NUM(f), ntRing, ntRing);
1493  if (!omitBrackets) StringAppendS(")");
1494  if (!DENIS1(f))
1495  {
1496  StringAppendS("/");
1497  omitBrackets = p_IsConstant(DEN(f), ntRing);
1498  if (!omitBrackets) StringAppendS("(");
1499  p_String0Long(DEN(f), ntRing, ntRing);
1500  if (!omitBrackets) StringAppendS(")");
1501  }
1502  }
1503  ntTest(a); // !!!!
1504 }
1505 
1506 void ntWriteShort(number a, const coeffs cf)
1507 {
1508  ntTest(a);
1509  if (IS0(a))
1510  StringAppendS("0");
1511  else
1512  {
1513  fraction f = (fraction)a;
1514  // stole logic from napWrite from kernel/longtrans.cc of legacy singular
1515  BOOLEAN omitBrackets = p_IsConstant(NUM(f), ntRing);
1516  if (!omitBrackets) StringAppendS("(");
1517  p_String0Short(NUM(f), ntRing, ntRing);
1518  if (!omitBrackets) StringAppendS(")");
1519  if (!DENIS1(f))
1520  {
1521  StringAppendS("/");
1522  omitBrackets = p_IsConstant(DEN(f), ntRing);
1523  if (!omitBrackets) StringAppendS("(");
1524  p_String0Short(DEN(f), ntRing, ntRing);
1525  if (!omitBrackets) StringAppendS(")");
1526  }
1527  }
1528  ntTest(a);
1529 }
1530 
1531 const char * ntRead(const char *s, number *a, const coeffs cf)
1532 {
1533  poly p;
1534  const char * result = p_Read(s, p, ntRing);
1535  if (p == NULL) *a = NULL;
1536  else *a = ntInit(p, cf);
1537  ntTest(*a);
1538  return result;
1539 }
1540 
1541 void ntNormalize (number &a, const coeffs cf)
1542 {
1543  if ( /*(*/ a!=NULL /*)*/ )
1544  {
1545  //PrintS("num=");p_wrp(NUM(a),ntRing);
1546  //PrintS(" den=");p_wrp(DEN(a),ntRing);PrintLn();
1548  if ((DEN((fraction)a)!=NULL)
1549  &&(!n_GreaterZero(pGetCoeff(DEN((fraction)a)),ntCoeffs)))
1550  {
1551  NUM((fraction)a)=p_Neg(NUM((fraction)a),ntRing);
1552  DEN((fraction)a)=p_Neg(DEN((fraction)a),ntRing);
1553  }
1554  }
1555  ntTest(a); // !!!!
1556 }
1557 
1558 /* expects *param to be castable to TransExtInfo */
1559 static BOOLEAN ntCoeffIsEqual(const coeffs cf, n_coeffType n, void * param)
1560 {
1561  if (ID != n) return FALSE;
1562  TransExtInfo *e = (TransExtInfo *)param;
1563  /* for rational function fields we expect the underlying
1564  polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
1565  this expectation is based on the assumption that we have properly
1566  registered cf and perform reference counting rather than creating
1567  multiple copies of the same coefficient field/domain/ring */
1568  if (ntRing == e->r)
1569  return TRUE;
1570 
1571  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
1572  if( rEqual(ntRing, e->r, TRUE) )
1573  {
1574  rDelete(e->r);
1575  return TRUE;
1576  }
1577 
1578  return FALSE;
1579 }
1580 
1581 number ntNormalizeHelper(number a, number b, const coeffs cf)
1582 {
1583  ntTest(a);
1584  ntTest(b);
1585  fraction fb = (fraction)b;
1586  if ((b==NULL)||(DEN(fb)==NULL)) return ntCopy(a,cf);
1587  fraction fa = (fraction)a;
1588  /* singclap_gcd destroys its arguments; we hence need copies: */
1589  poly pa = p_Copy(NUM(fa), ntRing);
1590  poly pb = p_Copy(DEN(fb), ntRing);
1591 
1592  poly pGcd;
1593  if (nCoeff_is_Q(ntCoeffs))
1594  {
1595  if (p_IsConstant(pa,ntRing) && p_IsConstant(pb,ntRing))
1596  {
1597  pGcd = pa;
1598  p_SetCoeff (pGcd, n_Gcd (pGetCoeff(pGcd), pGetCoeff(pb), ntCoeffs), ntRing);
1599  }
1600  else
1601  {
1602  number contentpa, contentpb, tmp;
1603 
1604  contentpb= p_GetCoeff(pb, ntRing);
1605  pIter(pb);
1606  while (pb != NULL)
1607  {
1608  tmp = n_SubringGcd(contentpb, p_GetCoeff(pb, ntRing) , ntCoeffs);
1609  n_Delete(&contentpb, ntCoeffs);
1610  contentpb = tmp;
1611  pIter(pb);
1612  }
1613 
1614  contentpa= p_GetCoeff(pa, ntRing);
1615  pIter(pa);
1616  while (pa != NULL)
1617  {
1618  tmp = n_SubringGcd(contentpa, p_GetCoeff(pa, ntRing), ntCoeffs);
1619  n_Delete(&contentpa, ntCoeffs);
1620  contentpa = tmp;
1621  pIter(pa);
1622  }
1623 
1624  tmp= n_SubringGcd (contentpb, contentpa, ntCoeffs);
1625  n_Delete(&contentpa, ntCoeffs);
1626  n_Delete(&contentpb, ntCoeffs);
1627  contentpa= tmp;
1628  p_Delete(&pb, ntRing);
1629  p_Delete(&pa, ntRing);
1630 
1631  /* singclap_gcd destroys its arguments; we hence need copies: */
1632  pGcd = singclap_gcd(p_Copy(NUM(fa),ntRing), p_Copy(DEN(fb),ntRing), ntRing);
1633  pGcd= p_Mult_nn (pGcd, contentpa, ntRing);
1634  n_Delete(&contentpa, ntCoeffs);
1635  }
1636  }
1637  else
1638  pGcd = singclap_gcd(pa, pb, cf->extRing);
1639 
1640  /* Note that, over Q, singclap_gcd will remove the denominators in all
1641  rational coefficients of pa and pb, before starting to compute
1642  the gcd. Thus, we do not need to ensure that the coefficients of
1643  pa and pb live in Z; they may well be elements of Q\Z. */
1644 
1645  if (p_IsConstant(pGcd, ntRing) &&
1646  n_IsOne(p_GetCoeff(pGcd, ntRing), ntCoeffs))
1647  { /* gcd = 1; return pa*pb*/
1648  p_Delete(&pGcd,ntRing);
1649  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1650  NUM(result) = pp_Mult_qq(NUM(fa),DEN(fb),ntRing);
1651 
1652  ntTest((number)result); // !!!!
1653 
1654  return (number)result;
1655  }
1656 
1657 
1658  /* return pa*pb/gcd */
1659  poly newNum = singclap_pdivide(NUM(fa), pGcd, ntRing);
1660  p_Delete(&pGcd,ntRing);
1661  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1662  NUM(result) = p_Mult_q(p_Copy(DEN(fb),ntRing),newNum,ntRing);
1663  ntTest((number)result); // !!!!
1664  return (number)result;
1665 
1666  return NULL;
1667 }
1668 
1669 number ntGcd(number a, number b, const coeffs cf)
1670 {
1671  ntTest(a);
1672  ntTest(b);
1673  if (a==NULL) return ntCopy(b,cf);
1674  if (b==NULL) return ntCopy(a,cf);
1675  fraction fa = (fraction)a;
1676  fraction fb = (fraction)b;
1677 
1678  poly pa = p_Copy(NUM(fa), ntRing);
1679  poly pb = p_Copy(NUM(fb), ntRing);
1680 
1681  poly pGcd;
1682  if (nCoeff_is_Q(ntCoeffs))
1683  {
1684  if (p_IsConstant(pa,ntRing) && p_IsConstant(pb,ntRing))
1685  {
1686  pGcd = pa;
1687  p_SetCoeff (pGcd, n_SubringGcd (pGetCoeff(pGcd), pGetCoeff(pb), ntCoeffs), ntRing);
1688  }
1689  else
1690  {
1691  number contentpa, contentpb, tmp;
1692 
1693  contentpb= p_GetCoeff(pb, ntRing);
1694  pIter(pb);
1695  while (pb != NULL)
1696  {
1697  tmp = n_SubringGcd(contentpb, p_GetCoeff(pb, ntRing) , ntCoeffs);
1698  n_Delete(&contentpb, ntCoeffs);
1699  contentpb = tmp;
1700  pIter(pb);
1701  }
1702 
1703  contentpa= p_GetCoeff(pa, ntRing);
1704  pIter(pa);
1705  while (pa != NULL)
1706  {
1707  tmp = n_SubringGcd(contentpa, p_GetCoeff(pa, ntRing), ntCoeffs);
1708  n_Delete(&contentpa, ntCoeffs);
1709  contentpa = tmp;
1710  pIter(pa);
1711  }
1712 
1713  tmp= n_SubringGcd (contentpb, contentpa, ntCoeffs);
1714  n_Delete(&contentpa, ntCoeffs);
1715  n_Delete(&contentpb, ntCoeffs);
1716  contentpa= tmp;
1717  p_Delete(&pb, ntRing);
1718  p_Delete(&pa, ntRing);
1719 
1720  /* singclap_gcd destroys its arguments; we hence need copies: */
1721  pGcd = singclap_gcd(p_Copy(NUM(fa),ntRing), p_Copy(NUM(fb),ntRing), ntRing);
1722  pGcd= p_Mult_nn (pGcd, contentpa, ntRing);
1723  n_Delete(&contentpa, ntCoeffs);
1724  }
1725  }
1726  else
1727  pGcd = singclap_gcd(pa, pb, cf->extRing);
1728  /* Note that, over Q, singclap_gcd will remove the denominators in all
1729  rational coefficients of pa and pb, before starting to compute
1730  the gcd. Thus, we do not need to ensure that the coefficients of
1731  pa and pb live in Z; they may well be elements of Q\Z. */
1732 
1733  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1734  NUM(result) = pGcd;
1735  ntTest((number)result); // !!!!
1736  return (number)result;
1737 }
1738 //number ntGcd_dummy(number a, number b, const coeffs cf)
1739 //{
1740 // extern char my_yylinebuf[80];
1741 // Print("ntGcd in >>%s<<\n",my_yylinebuf);
1742 // return ntGcd(a,b,cf);
1743 //}
1744 
1745 int ntSize(number a, const coeffs cf)
1746 {
1747  ntTest(a);
1748  if (IS0(a)) return -1;
1749  /* this has been taken from the old implementation of field extensions,
1750  where we computed the sum of the degrees and the numbers of terms in
1751  the numerator and denominator of a; so we leave it at that, for the
1752  time being */
1753  fraction f = (fraction)a;
1754  poly p = NUM(f);
1755  int noOfTerms = 0;
1756  int numDegree = 0;
1757  if (p!=NULL)
1758  {
1759  numDegree = p_Totaldegree(p,ntRing);
1760  noOfTerms = pLength(p);
1761  }
1762  int denDegree = 0;
1763  if (!DENIS1(f))
1764  {
1765  denDegree = p_Totaldegree(DEN(f),ntRing);
1766  noOfTerms += pLength(DEN(f));
1767  }
1768  ntTest(a); // !!!!
1769  return numDegree + denDegree + noOfTerms;
1770 }
1771 
1772 number ntInvers(number a, const coeffs cf)
1773 {
1774  //check_N(a,cf);
1775  ntTest(a);
1776  if (IS0(a))
1777  {
1778  WerrorS(nDivBy0);
1779  return NULL;
1780  }
1781  fraction f = (fraction)a;
1782  assume( f != NULL );
1783 
1784  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
1785 
1786  assume( NUM(f) != NULL );
1787  const poly den = DEN(f);
1788 
1789  if (den == NULL)
1790  NUM(result) = p_One(ntRing);
1791  else
1792  NUM(result) = p_Copy(den, ntRing);
1793 
1794  if( !NUMIS1(f) )
1795  {
1796  poly num_f=NUM(f);
1797  BOOLEAN neg= !n_GreaterZero(pGetCoeff(num_f),ntCoeffs);
1798  if (neg)
1799  {
1800  num_f=p_Neg(p_Copy(num_f, ntRing), ntRing);
1801  NUM(result)=p_Neg(NUM(result), ntRing);
1802  }
1803  else
1804  {
1805  num_f=p_Copy(num_f, ntRing);
1806  }
1807  DEN(result) = num_f;
1808  COM(result) = COM(f);
1809  if (neg)
1810  {
1811  if (p_IsOne(num_f, ntRing))
1812  {
1813  DEN(result)=NULL;
1814  //COM(result) = 0;
1815  p_Delete(&num_f,ntRing);
1816  }
1817  }
1818  }
1819  //else// Alloc0
1820  //{
1821  // DEN(result) = NULL;
1822  // COM(result) = 0;
1823  //}
1824  ntTest((number)result); // !!!!
1825  //check_N((number)result,cf);
1826  return (number)result;
1827 }
1828 
1829 /* assumes that src = Q or Z, dst = Q(t_1, ..., t_s) */
1830 number ntMap00(number a, const coeffs src, const coeffs dst)
1831 {
1832  n_Test(a, src);
1833 
1834  if (n_IsZero(a, src)) return NULL;
1835  assume(src->rep == dst->extRing->cf->rep);
1836  if ((SR_HDL(a) & SR_INT) || (a->s==3))
1837  {
1838  number res=ntInit(p_NSet(n_Copy(a, src), dst->extRing), dst);
1839  n_Test(res, dst);
1840  return res;
1841  }
1842  number nn=n_GetDenom(a,src);
1843  number zz=n_GetNumerator(a,src);
1844  number res=ntInit(p_NSet(zz,dst->extRing), dst);
1845  fraction ff=(fraction)res;
1846  if (n_IsOne(nn,src)) DEN(ff)=NULL;
1847  else DEN(ff)=p_NSet(nn,dst->extRing);
1848 
1849  n_Test((number)ff,dst);
1850  //check_N((number)ff,dst);
1851  return (number)ff;
1852 }
1853 
1854 number ntMapZ0(number a, const coeffs src, const coeffs dst)
1855 {
1856  n_Test(a, src);
1857  if (n_IsZero(a, src)) return NULL;
1858  nMapFunc nMap=n_SetMap(src,dst->extRing->cf);
1859  poly p=p_NSet(nMap(a, src,dst->extRing->cf), dst->extRing);
1860  if (n_IsZero(pGetCoeff(p),dst->extRing->cf))
1861  p_Delete(&p,dst->extRing);
1862  number res=ntInit(p, dst);
1863  n_Test(res,dst);
1864  return res;
1865 }
1866 
1867 /* assumes that src = Z/p, dst = Q(t_1, ..., t_s) */
1868 number ntMapP0(number a, const coeffs src, const coeffs dst)
1869 {
1870  n_Test(a, src);
1871  if (n_IsZero(a, src)) return NULL;
1872  /* mapping via intermediate int: */
1873  int n = n_Int(a, src);
1874  number q = n_Init(n, dst->extRing->cf);
1875  if (n_IsZero(q, dst->extRing->cf))
1876  {
1877  n_Delete(&q, dst->extRing->cf);
1878  return NULL;
1879  }
1880  return ntInit(p_NSet(q, dst->extRing), dst);
1881 }
1882 
1883  /* assumes that either src = K(t_1, ..., t_s), dst = K(t_1, ..., t_s) */
1884 number ntCopyMap(number a, const coeffs cf, const coeffs dst)
1885 {
1886  ntTest(a);
1887  if (IS0(a)) return NULL;
1888 
1889  const ring rSrc = cf->extRing;
1890  const ring rDst = dst->extRing;
1891 
1892  if( rSrc == rDst )
1893  return ntCopy(a, dst); // USUALLY WRONG!
1894 
1895  fraction f = (fraction)a;
1896  poly g = prCopyR(NUM(f), rSrc, rDst);
1897 
1898  poly h = NULL;
1899 
1900  if (!DENIS1(f))
1901  h = prCopyR(DEN(f), rSrc, rDst);
1902 
1903  fraction result = (fraction)omAllocBin(fractionObjectBin);
1904 
1905  NUM(result) = g;
1906  DEN(result) = h;
1907  COM(result) = COM(f);
1908  //check_N((number)result,dst);
1909  n_Test((number)result, dst);
1910  return (number)result;
1911 }
1912 
1913 number ntGenMap(number a, const coeffs cf, const coeffs dst)
1914 {
1915  ntTest(a);
1916  if (IS0(a)) return NULL;
1917 
1918  const ring rSrc = cf->extRing;
1919  const ring rDst = dst->extRing;
1920 
1921  const nMapFunc nMap=n_SetMap(rSrc->cf,rDst->cf);
1922  fraction f = (fraction)a;
1923  poly g = prMapR(NUM(f), nMap, rSrc, rDst);
1924  /* g may contain summands with coeff 0 */
1925  poly hh=g;
1926  poly prev=NULL;
1927  while(hh!=NULL)
1928  {
1929  if (n_IsZero(pGetCoeff(hh),rDst->cf))
1930  {
1931  if (prev==NULL)
1932  {
1933  g=p_LmFreeAndNext(g,rDst);
1934  hh=g;
1935  }
1936  else
1937  {
1938  prev->next=p_LmFreeAndNext(prev->next,rDst);
1939  hh=prev->next;
1940  }
1941  }
1942  else
1943  {
1944  prev=hh;
1945  pIter(hh);
1946  }
1947  }
1948  if (g==NULL) return NULL;
1949 
1950  poly h = NULL;
1951 
1952  if (!DENIS1(f))
1953  {
1954  h = prMapR(DEN(f), nMap, rSrc, rDst);
1955  /* h may contain summands with coeff 0 */
1956  hh=h;
1957  prev=NULL;
1958  while(hh!=NULL)
1959  {
1960  if (n_IsZero(pGetCoeff(hh),rDst->cf))
1961  {
1962  if (prev==NULL)
1963  {
1964  h=p_LmFreeAndNext(h,rDst);
1965  hh=h;
1966  }
1967  else
1968  {
1969  prev->next=p_LmFreeAndNext(prev->next,rDst);
1970  hh=prev->next;
1971  }
1972  }
1973  else
1974  {
1975  prev=hh;
1976  pIter(hh);
1977  }
1978  }
1979  if (h==NULL) WerrorS("mapping to */0");
1980  }
1981 
1982  fraction result = (fraction)omAllocBin(fractionObjectBin);
1983 
1984  NUM(result) = g;
1985  DEN(result) = h;
1986  COM(result) = COM(f);
1987  //check_N((number)result,dst);
1988  n_Test((number)result, dst);
1989  return (number)result;
1990 }
1991 
1992 number ntCopyAlg(number a, const coeffs cf, const coeffs dst)
1993 {
1994  n_Test(a, cf) ;
1995  if (n_IsZero(a, cf)) return NULL;
1996  return ntInit(prCopyR((poly)a, cf->extRing, dst->extRing),dst);
1997 }
1998 
1999 number ntGenAlg(number a, const coeffs cf, const coeffs dst)
2000 {
2001  n_Test(a, cf) ;
2002  if (n_IsZero(a, cf)) return NULL;
2003 
2004  const nMapFunc nMap=n_SetMap(cf->extRing->cf,dst->extRing->cf);
2005  return ntInit(prMapR((poly)a, nMap, cf->extRing, dst->extRing),dst);
2006 }
2007 
2008 /* assumes that src = Q, dst = Z/p(t_1, ..., t_s) */
2009 number ntMap0P(number a, const coeffs src, const coeffs dst)
2010 {
2011  n_Test(a, src) ;
2012  if (n_IsZero(a, src)) return NULL;
2013  // int p = rChar(dst->extRing);
2014 
2015  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 Zp
2016 
2017  if (n_IsZero(q, dst->extRing->cf))
2018  {
2019  n_Delete(&q, dst->extRing->cf);
2020  return NULL;
2021  }
2022 
2023  poly g = p_NSet(q, dst->extRing);
2024 
2025  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
2026  NUM(f) = g; // DEN(f) = NULL; COM(f) = 0;
2027  n_Test((number)f, dst);
2028  //check_N((number)f,dst);
2029  return (number)f;
2030 }
2031 
2032 /* assumes that src = Z/p, dst = Z/p(t_1, ..., t_s) */
2033 number ntMapPP(number a, const coeffs src, const coeffs dst)
2034 {
2035  n_Test(a, src) ;
2036  if (n_IsZero(a, src)) return NULL;
2037  assume(src == dst->extRing->cf);
2038  poly p = p_One(dst->extRing);
2039  p_SetCoeff(p, n_Copy(a, src), dst->extRing);
2040  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
2041  NUM(f) = p; // DEN(f) = NULL; COM(f) = 0;
2042  n_Test((number)f, dst);
2043  //check_N((number)f,dst);
2044  return (number)f;
2045 }
2046 
2047 /* assumes that src = Z/u, dst = Z/p(t_1, ..., t_s), where u != p */
2048 number ntMapUP(number a, const coeffs src, const coeffs dst)
2049 {
2050  n_Test(a, src) ;
2051  if (n_IsZero(a, src)) return NULL;
2052  /* mapping via intermediate int: */
2053  int n = n_Int(a, src);
2054  number q = n_Init(n, dst->extRing->cf);
2055  poly p;
2056  if (n_IsZero(q, dst->extRing->cf))
2057  {
2058  n_Delete(&q, dst->extRing->cf);
2059  return NULL;
2060  }
2061  p = p_One(dst->extRing);
2062  p_SetCoeff(p, q, dst->extRing);
2063  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
2064  NUM(f) = p; // DEN(f) = NULL; COM(f) = 0;
2065  n_Test((number)f, dst);
2066  //check_N((number)f,dst);
2067  return (number)f;
2068 }
2069 
2070 nMapFunc ntSetMap(const coeffs src, const coeffs dst)
2071 {
2072  /* dst is expected to be a rational function field */
2073  assume(getCoeffType(dst) == ID);
2074 
2075  if( src == dst ) return ndCopyMap;
2076 
2077  int h = 0; /* the height of the extension tower given by dst */
2078  coeffs bDst = nCoeff_bottom(dst, h); /* the bottom field in the tower dst */
2079  coeffs bSrc = nCoeff_bottom(src, h); /* the bottom field in the tower src */
2080 
2081  /* for the time being, we only provide maps if h = 1 and if b is Q or
2082  some field Z/pZ: */
2083  if (h==0)
2084  {
2085  if ((src->rep==n_rep_gap_rat) && nCoeff_is_Q(bDst))
2086  return ntMap00; /// Q or Z --> Q(T)
2087  if (src->rep==n_rep_gap_gmp)
2088  return ntMapZ0; /// Z --> K(T)
2089  if (nCoeff_is_Zp(src) && nCoeff_is_Q(bDst))
2090  return ntMapP0; /// Z/p --> Q(T)
2091  if (nCoeff_is_Q_or_BI(src) && nCoeff_is_Zp(bDst))
2092  return ntMap0P; /// Q --> Z/p(T)
2093  if (nCoeff_is_Zp(src) && nCoeff_is_Zp(bDst))
2094  {
2095  if (src->ch == dst->ch) return ntMapPP; /// Z/p --> Z/p(T)
2096  else return ntMapUP; /// Z/u --> Z/p(T)
2097  }
2098  }
2099  if (h != 1) return NULL;
2100  //if ((!nCoeff_is_Zp(bDst)) && (!nCoeff_is_Q(bDst))) return NULL;
2101 
2102  /* Let T denote the sequence of transcendental extension variables, i.e.,
2103  K[t_1, ..., t_s] =: K[T];
2104  Let moreover, for any such sequence T, T' denote any subsequence of T
2105  of the form t_1, ..., t_w with w <= s. */
2106 
2107  if (rVar(src->extRing) > rVar(dst->extRing))
2108  return NULL;
2109 
2110  for (int i = 0; i < rVar(src->extRing); i++)
2111  if (strcmp(rRingVar(i, src->extRing), rRingVar(i, dst->extRing)) != 0)
2112  return NULL;
2113 
2114  if (src->type==n_transExt)
2115  {
2116  if (src->extRing->cf==dst->extRing->cf)
2117  return ntCopyMap; /// K(T') --> K(T)
2118  else
2119  return ntGenMap; /// K(T') --> K'(T)
2120  }
2121  else
2122  {
2123  if (src->extRing->cf==dst->extRing->cf)
2124  return ntCopyAlg; /// K(T') --> K(T)
2125  else
2126  return ntGenAlg; /// K(T') --> K'(T)
2127  }
2128 
2129  return NULL; /// default
2130 }
2131 #if 0
2132 nMapFunc ntSetMap_T(const coeffs src, const coeffs dst)
2133 {
2134  nMapFunc n=ntSetMap(src,dst);
2135  if (n==ntCopyAlg) printf("n=ntCopyAlg\n");
2136  else if (n==ntCopyMap) printf("n=ntCopyMap\n");
2137  else if (n==ntMapUP) printf("n=ntMapUP\n");
2138  else if (n==ntMap0P) printf("n=ntMap0P\n");
2139  else if (n==ntMapP0) printf("n=ntMapP0\n");
2140  else if (n==ntMap00) printf("n=ntMap00\n");
2141  else if (n==NULL) printf("n=NULL\n");
2142  else printf("n=?\n");
2143  return n;
2144 }
2145 #endif
2146 
2148 {
2149  if ((--cf->extRing->ref) == 0)
2150  rDelete(cf->extRing);
2151 }
2153 {
2154  if (n.isZero()) return NULL;
2156  p_Normalize(p,ntRing);
2157  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
2158  NUM(result) = p;
2159  //DEN(result) = NULL; // done by omAlloc0Bin
2160  //COM(result) = 0; // done by omAlloc0Bin
2161  ntTest((number)result);
2162  return (number)result;
2163 }
2164 CanonicalForm ntConvSingNFactoryN( number n, BOOLEAN /*setChar*/, const coeffs cf )
2165 {
2166  ntTest(n);
2167  if (IS0(n)) return CanonicalForm(0);
2168 
2169  fraction f = (fraction)n;
2170  return convSingPFactoryP(NUM(f),ntRing);
2171 }
2172 
2173 static int ntParDeg(number a, const coeffs cf)
2174 {
2175  ntTest(a);
2176  if (IS0(a)) return -1;
2177  fraction fa = (fraction)a;
2178  return cf->extRing->pFDeg(NUM(fa),cf->extRing);
2179 }
2180 
2181 /// return the specified parameter as a number in the given trans.ext.
2182 static number ntParameter(const int iParameter, const coeffs cf)
2183 {
2184  assume(getCoeffType(cf) == ID);
2185 
2186  const ring R = cf->extRing;
2187  assume( R != NULL );
2188  assume( 0 < iParameter && iParameter <= rVar(R) );
2189 
2190  poly p = p_One(R); p_SetExp(p, iParameter, 1, R); p_Setm(p, R);
2191  p_Test(p,R);
2192 
2193  fraction f = (fraction)omAlloc0Bin(fractionObjectBin);
2194  NUM(f) = p;
2195  //DEN(f) = NULL;
2196  //COM(f) = 0;
2197 
2198  ntTest((number)f);
2199 
2200  return (number)f;
2201 }
2202 
2203 /// if m == var(i)/1 => return i,
2204 int ntIsParam(number m, const coeffs cf)
2205 {
2206  ntTest(m);
2207  assume(getCoeffType(cf) == ID);
2208 
2209  const ring R = cf->extRing;
2210  assume( R != NULL );
2211 
2212  fraction f = (fraction)m;
2213 
2214  if( DEN(f) != NULL )
2215  return 0;
2216 
2217  return p_Var( NUM(f), R );
2218 }
2219 
2221 {
2222  static inline poly convert(const number& n)
2223  {
2224  // suitable for trans. ext. numbers that are fractions of polys
2225  return NUM((fraction)n); // return the numerator
2226  }
2227 };
2228 
2229 
2230 static void ntClearContent(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
2231 {
2232  assume(cf != NULL);
2233  assume(getCoeffType(cf) == ID);
2234  // all coeffs are given by fractions of polynomails over integers!!!
2235  // without denominators!!!
2236 
2237  const ring R = cf->extRing;
2238  assume(R != NULL);
2239  const coeffs Q = R->cf;
2240  assume(Q != NULL);
2241  assume(nCoeff_is_Q(Q));
2242 
2243 
2244  numberCollectionEnumerator.Reset();
2245 
2246  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
2247  {
2248  c = ntInit(1, cf);
2249  return;
2250  }
2251 
2252  // all coeffs are given by integers after returning from this routine
2253 
2254  // part 1, collect product of all denominators /gcds
2255  poly cand = NULL;
2256 
2257  do
2258  {
2259  number &n = numberCollectionEnumerator.Current();
2260 
2261  ntNormalize(n, cf);
2262 
2263  fraction f = (fraction)n;
2264 
2265  assume( f != NULL );
2266 
2267  const poly den = DEN(f);
2268 
2269  assume( den == NULL ); // ?? / 1 ?
2270 
2271  const poly num = NUM(f);
2272 
2273  if( cand == NULL )
2274  cand = p_Copy(num, R);
2275  else
2276  cand = singclap_gcd(cand, p_Copy(num, R), R); // gcd(cand, num)
2277 
2278  if( p_IsConstant(cand, R) )
2279  break;
2280  }
2281  while( numberCollectionEnumerator.MoveNext() ) ;
2282 
2283 
2284  // part2: all coeffs = all coeffs * cand
2285  if( cand != NULL )
2286  {
2287  if( !p_IsConstant(cand, R) )
2288  {
2289  c = ntInit(cand, cf);
2290  numberCollectionEnumerator.Reset();
2291  while (numberCollectionEnumerator.MoveNext() )
2292  {
2293  number &n = numberCollectionEnumerator.Current();
2294  const number t = ntDiv(n, c, cf); // TODO: rewrite!?
2295  ntDelete(&n, cf);
2296  n = t;
2297  }
2298  } // else NUM (result) = p_One(R);
2299  else { p_Delete(&cand, R); cand = NULL; }
2300  }
2301 
2302  // Quick and dirty fix for constant content clearing: consider numerators???
2303  CRecursivePolyCoeffsEnumerator<NTNumConverter> itr(numberCollectionEnumerator); // recursively treat the NUM(numbers) as polys!
2304  number cc;
2305 
2306  n_ClearContent(itr, cc, Q);
2307  number g = ntInit(p_NSet(cc, R), cf);
2308 
2309  if( cand != NULL )
2310  {
2311  number gg = ntMult(g, c, cf);
2312  ntDelete(&g, cf);
2313  ntDelete(&c, cf); c = gg;
2314  } else
2315  c = g;
2316  ntTest(c);
2317 }
2318 
2319 static void ntClearDenominators(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
2320 {
2321  assume(cf != NULL);
2322  assume(getCoeffType(cf) == ID); // both over Q(a) and Zp(a)!
2323  // all coeffs are given by fractions of polynomails over integers!!!
2324 
2325  numberCollectionEnumerator.Reset();
2326 
2327  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
2328  {
2329  c = ntInit(1, cf);
2330  return;
2331  }
2332 
2333  // all coeffs are given by integers after returning from this routine
2334 
2335  // part 1, collect product of all denominators /gcds
2336  poly cand = NULL;
2337 
2338  const ring R = cf->extRing;
2339  assume(R != NULL);
2340 
2341  const coeffs Q = R->cf;
2342  assume(Q != NULL);
2343 // assume(nCoeff_is_Q(Q));
2344 
2345  do
2346  {
2347  number &n = numberCollectionEnumerator.Current();
2348 
2349  ntNormalize(n, cf);
2350 
2351  fraction f = (fraction)ntGetDenom (n, cf);
2352 
2353  assume( f != NULL );
2354 
2355  const poly den = NUM(f);
2356 
2357  if( den == NULL ) // ?? / 1 ?
2358  continue;
2359 
2360  if( cand == NULL )
2361  cand = p_Copy(den, R);
2362  else
2363  {
2364  // cand === LCM( cand, den )!!!!
2365  // NOTE: maybe it's better to make the product and clearcontent afterwards!?
2366  // TODO: move the following to factory?
2367  poly gcd = singclap_gcd(p_Copy(cand, R), p_Copy(den, R), R); // gcd(cand, den) is monic no mater leading coeffs! :((((
2368  if (nCoeff_is_Q (Q))
2369  {
2370  number LcGcd= n_SubringGcd (p_GetCoeff (cand, R), p_GetCoeff(den, R), Q);
2371  gcd = p_Mult_nn(gcd, LcGcd, R);
2372  n_Delete(&LcGcd,Q);
2373  }
2374 // assume( n_IsOne(pGetCoeff(gcd), Q) ); // TODO: this may be wrong...
2375  cand = p_Mult_q(cand, p_Copy(den, R), R); // cand *= den
2376  const poly t = singclap_pdivide( cand, gcd, R ); // cand' * den / gcd(cand', den)
2377  p_Delete(&cand, R);
2378  p_Delete(&gcd, R);
2379  cand = t;
2380  }
2381  }
2382  while( numberCollectionEnumerator.MoveNext() );
2383 
2384  if( cand == NULL )
2385  {
2386  c = ntInit(1, cf);
2387  return;
2388  }
2389 
2390  c = ntInit(cand, cf);
2391 
2392  numberCollectionEnumerator.Reset();
2393 
2394  number d = NULL;
2395 
2396  while (numberCollectionEnumerator.MoveNext() )
2397  {
2398  number &n = numberCollectionEnumerator.Current();
2399  number t = ntMult(n, c, cf); // TODO: rewrite!?
2400  ntDelete(&n, cf);
2401 
2402  ntNormalize(t, cf); // TODO: needed?
2403  n = t;
2404 
2405  fraction f = (fraction)t;
2406  assume( f != NULL );
2407 
2408  const poly den = DEN(f);
2409 
2410  if( den != NULL ) // ?? / ?? ?
2411  {
2412  assume( p_IsConstant(den, R) );
2413  assume( pNext(den) == NULL );
2414 
2415  if( d == NULL )
2416  d = n_Copy(pGetCoeff(den), Q);
2417  else
2418  {
2419  number g = n_NormalizeHelper(d, pGetCoeff(den), Q);
2420  n_Delete(&d, Q); d = g;
2421  }
2422  }
2423  }
2424 
2425  if( d != NULL )
2426  {
2427  numberCollectionEnumerator.Reset();
2428  while (numberCollectionEnumerator.MoveNext() )
2429  {
2430  number &n = numberCollectionEnumerator.Current();
2431  fraction f = (fraction)n;
2432 
2433  assume( f != NULL );
2434 
2435  const poly den = DEN(f);
2436 
2437  if( den == NULL ) // ?? / 1 ?
2438  NUM(f) = p_Mult_nn(NUM(f), d, R);
2439  else
2440  {
2441  assume( p_IsConstant(den, R) );
2442  assume( pNext(den) == NULL );
2443 
2444  number ddd = n_Div(d, pGetCoeff(den), Q); // but be an integer now!!!
2445  NUM(f) = p_Mult_nn(NUM(f), ddd, R);
2446  n_Delete(&ddd, Q);
2447 
2448  p_Delete(&DEN(f), R);
2449  DEN(f) = NULL; // TODO: check if this is needed!?
2450  }
2451 
2452  assume( DEN(f) == NULL );
2453  }
2454 
2455  NUM((fraction)c) = p_Mult_nn(NUM((fraction)c), d, R);
2456  n_Delete(&d, Q);
2457  }
2458 
2459 
2460  ntTest(c);
2461 }
2462 
2463 number ntChineseRemainder(number *x, number *q,int rl, BOOLEAN sym,CFArray &inv_cache,const coeffs cf)
2464 {
2465  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
2466 
2467  poly *P=(poly*)omAlloc(rl*sizeof(poly*));
2468  number *X=(number *)omAlloc(rl*sizeof(number));
2469 
2470  int i;
2471 
2472  for(i=0;i<rl;i++) P[i]=p_Copy(NUM((fraction)(x[i])),cf->extRing);
2473  NUM(result)=p_ChineseRemainder(P,X,q,rl,inv_cache,cf->extRing);
2474 
2475  for(i=0;i<rl;i++)
2476  {
2477  P[i]=p_Copy(DEN((fraction)(x[i])),cf->extRing);
2478  if (P[i]==NULL) P[i]=p_One(cf->extRing);
2479  }
2480  DEN(result)=p_ChineseRemainder(P,X,q,rl,inv_cache,cf->extRing);
2481 
2482  omFreeSize(X,rl*sizeof(number));
2483  omFreeSize(P,rl*sizeof(poly*));
2484  if (p_IsConstant(DEN(result), ntRing)
2485  && n_IsOne(pGetCoeff(DEN(result)), ntCoeffs))
2486  {
2487  p_Delete(&DEN(result),ntRing);
2488  }
2489  ntTest((number)result);
2490  return ((number)result);
2491 }
2492 
2493 number ntFarey(number p, number n, const coeffs cf)
2494 {
2495  // n is really a bigint
2496  fraction result = (fraction)omAlloc0Bin(fractionObjectBin);
2497  NUM(result)=p_Farey(p_Copy(NUM((fraction)p),cf->extRing),n,cf->extRing);
2498  DEN(result)=p_Farey(p_Copy(DEN((fraction)p),cf->extRing),n,cf->extRing);
2499  ntTest((number)result);
2500  return ((number)result);
2501 }
2502 
2503 BOOLEAN ntInitChar(coeffs cf, void * infoStruct)
2504 {
2505 
2506  assume( infoStruct != NULL );
2507 
2508  TransExtInfo *e = (TransExtInfo *)infoStruct;
2509 
2510  assume( e->r != NULL); // extRing;
2511  assume( e->r->cf != NULL); // extRing->cf;
2512  assume( e->r->qideal == NULL );
2513 
2514  assume( cf != NULL );
2515  assume(getCoeffType(cf) == ID); // coeff type;
2516 
2517  ring R = e->r;
2518  assume(R != NULL);
2519 
2520  R->ref ++; // increase the ref.counter for the ground poly. ring!
2521 
2522  cf->extRing = R;
2523  /* propagate characteristic up so that it becomes
2524  directly accessible in cf: */
2525  cf->ch = R->cf->ch;
2526 
2527  cf->is_field=TRUE;
2528  cf->is_domain=TRUE;
2529  cf->rep=n_rep_rat_fct;
2530 
2531  cf->factoryVarOffset = R->cf->factoryVarOffset + rVar(R);
2532 
2533  cf->cfCoeffString = naCoeffString; // FIXME? TODO? // extern char* naCoeffString(const coeffs r);
2534 
2535  cf->cfGreaterZero = ntGreaterZero;
2536  cf->cfGreater = ntGreater;
2537  cf->cfEqual = ntEqual;
2538  cf->cfIsZero = ntIsZero;
2539  cf->cfIsOne = ntIsOne;
2540  cf->cfIsMOne = ntIsMOne;
2541  cf->cfInit = ntInit;
2542  cf->cfFarey = ntFarey;
2543  cf->cfChineseRemainder = ntChineseRemainder;
2544  cf->cfInt = ntInt;
2545  cf->cfInpNeg = ntNeg;
2546  cf->cfAdd = ntAdd;
2547  cf->cfSub = ntSub;
2548  cf->cfMult = ntMult;
2549  cf->cfDiv = ntDiv;
2550  cf->cfExactDiv = ntDiv;
2551  cf->cfPower = ntPower;
2552  cf->cfCopy = ntCopy;
2553  cf->cfWriteLong = ntWriteLong;
2554  cf->cfRead = ntRead;
2555  cf->cfNormalize = ntNormalize;
2556  cf->cfDelete = ntDelete;
2557  cf->cfSetMap = ntSetMap;
2558  cf->cfGetDenom = ntGetDenom;
2559  cf->cfGetNumerator = ntGetNumerator;
2560  cf->cfRePart = ntCopy;
2561  cf->cfImPart = ntImPart;
2562  cf->cfCoeffWrite = ntCoeffWrite;
2563 #ifdef LDEBUG
2564  cf->cfDBTest = ntDBTest;
2565 #endif
2566  //cf->cfGcd = ntGcd_dummy;
2567  cf->cfSubringGcd = ntGcd;
2568  cf->cfNormalizeHelper = ntNormalizeHelper;
2569  cf->cfSize = ntSize;
2570  cf->nCoeffIsEqual = ntCoeffIsEqual;
2571  cf->cfInvers = ntInvers;
2572  cf->cfKillChar = ntKillChar;
2573 
2574  if( rCanShortOut(ntRing) )
2575  cf->cfWriteShort = ntWriteShort;
2576  else
2577  cf->cfWriteShort = ntWriteLong;
2578 
2579  cf->convFactoryNSingN =ntConvFactoryNSingN;
2580  cf->convSingNFactoryN =ntConvSingNFactoryN;
2581  cf->cfParDeg = ntParDeg;
2582 
2583  cf->iNumberOfParameters = rVar(R);
2584  cf->pParameterNames = (const char**)R->names;
2585  cf->cfParameter = ntParameter;
2586  cf->has_simple_Inverse= FALSE;
2587  /* cf->has_simple_Alloc= FALSE; */
2588 
2589 
2590  if( nCoeff_is_Q(R->cf) )
2591  cf->cfClearContent = ntClearContent;
2592 
2593  cf->cfClearDenominators = ntClearDenominators;
2594 
2595  return FALSE;
2596 }
2597 
2599 template class IEnumerator<snumber*>;
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
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:512
static FORCE_INLINE number n_GetNumerator(number &n, const coeffs r)
return the numerator of n (if elements of r are by nature not fractional, result is n) ...
Definition: coeffs.h:609
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ...
Definition: coeffs.h:685
long ntInt(number &a, const coeffs cf)
Definition: transext.cc:684
const CanonicalForm int s
Definition: facAbsFact.cc:55
poly p_Diff(poly a, int k, const ring r)
Definition: p_polys.cc:1809
#define BOUND_COMPLEXITY
maximum complexity of a number
Definition: transext.cc:65
poly singclap_gcd_r(poly f, poly g, const ring r)
Definition: clapsing.cc:52
poly singclap_gcd_and_divide(poly &f, poly &g, const ring r)
clears denominators of f and g, divides by gcd(f,g)
Definition: clapsing.cc:150
number ntNormalizeHelper(number a, number b, const coeffs cf)
Definition: transext.cc:1581
number ntDiff(number a, number d, const coeffs cf)
Definition: transext.cc:813
const poly a
Definition: syzextra.cc:212
omBin_t * omBin
Definition: omStructs.h:12
void PrintLn()
Definition: reporter.cc:322
#define Print
Definition: emacs.cc:83
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:818
number ntMap00(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:1830
number ntMapUP(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:2048
poly prCopyR(poly p, ring src_r, ring dest_r)
Definition: prCopy.cc:36
number ntGenMap(number a, const coeffs cf, const coeffs dst)
Definition: transext.cc:1913
number ntImPart(number a, const coeffs cf)
Definition: transext.cc:609
void ntWriteLong(number a, const coeffs cf)
Definition: transext.cc:1481
void ntDelete(number *a, const coeffs cf)
Definition: transext.cc:334
static poly convert(const number &n)
Definition: transext.cc:2222
CanonicalForm num(const CanonicalForm &f)
loop
Definition: myNF.cc:98
used for all transcendental extensions, i.e., the top-most extension in an extension tower is transce...
Definition: coeffs.h:38
#define DIFF_COMPLEXITY
complexity increase due to * and /
Definition: transext.cc:64
void p_String0Long(const poly p, ring lmRing, ring tailRing)
print p in a long way
Definition: polys0.cc:116
#define FALSE
Definition: auxiliary.h:140
number ntDiv(number a, number b, const coeffs cf)
Definition: transext.cc:1022
static FORCE_INLINE BOOLEAN nlIsInteger(number q, const coeffs r)
Definition: longrat.h:99
return P p
Definition: myNF.cc:203
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:469
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1448
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:239
BOOLEAN ntIsMOne(number a, const coeffs cf)
Definition: transext.cc:583
number ntMult(number a, number b, const coeffs cf)
Definition: transext.cc:951
rational (GMP) numbers
Definition: coeffs.h:31
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 BOOLEAN nCoeff_is_Q_or_BI(const coeffs r)
Definition: coeffs.h:827
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define ntTest(a)
Definition: transext.cc:77
{p < 2^31}
Definition: coeffs.h:30
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
number ntSub(number a, number b, const coeffs cf)
Definition: transext.cc:912
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:540
poly singclap_gcd(poly f, poly g, const ring r)
destroys f and g
Definition: clapsing.cc:287
(), see rinteger.h, new impl.
Definition: coeffs.h:111
poly p_Div_nn(poly p, const number n, const ring r)
Definition: p_polys.cc:1480
#define COM(f)
Definition: transext.cc:70
factory's main class
Definition: canonicalform.h:75
#define TRUE
Definition: auxiliary.h:144
int ntSize(number a, const coeffs cf)
Definition: transext.cc:1745
void handleNestedFractionsOverQ(fraction f, const coeffs cf)
Definition: transext.cc:1161
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1435
BOOLEAN ntIsZero(number a, const coeffs cf)
Definition: transext.cc:327
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
void * ADDRESS
Definition: auxiliary.h:161
void ntWriteShort(number a, const coeffs cf)
Definition: transext.cc:1506
BOOLEAN ntDBTest(number a, const char *f, const int l, const coeffs r)
Definition: transext.cc:175
g
Definition: cfModGcd.cc:4031
void WerrorS(const char *s)
Definition: feFopen.cc:23
int k
Definition: cfEzgcd.cc:93
static FORCE_INLINE number n_NormalizeHelper(number a, number b, const coeffs r)
assume that r is a quotient field (otherwise, return 1) for arguments (a1/a2,b1/b2) return (lcm(a1...
Definition: coeffs.h:716
(fraction), see transext.h
Definition: coeffs.h:113
nMapFunc ntSetMap(const coeffs src, const coeffs dst)
Get a mapping function from src into the domain of this type (n_transExt)
Definition: transext.cc:2070
void p_Norm(poly p1, const ring r)
Definition: p_polys.cc:3565
#define Q
Definition: sirandom.c:25
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
static FORCE_INLINE BOOLEAN nCoeff_is_Q(const coeffs r)
Definition: coeffs.h:824
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
char * naCoeffString(const coeffs r)
Definition: algext.cc:1346
poly singclap_pdivide(poly f, poly g, const ring r)
Definition: clapsing.cc:547
#define omAlloc(size)
Definition: omAllocDecl.h:210
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:401
poly p_Sub(poly p1, poly p2, const ring r)
Definition: p_polys.cc:1901
static coeffs nCoeff_bottom(const coeffs r, int &height)
Definition: transext.cc:313
static BOOLEAN rCanShortOut(const ring r)
Definition: ring.h:534
static int pLength(poly a)
Definition: p_polys.h:189
BOOLEAN ntIsOne(number a, const coeffs cf)
Definition: transext.cc:574
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:811
void ntNormalize(number &a, const coeffs cf)
Definition: transext.cc:1541
poly prMapR(poly src, nMapFunc nMap, ring src_r, ring dest_r)
Definition: prCopy.cc:47
number ntInvers(number a, const coeffs cf)
Definition: transext.cc:1772
static BOOLEAN p_LmIsConstant(const poly p, const ring r)
Definition: p_polys.h:954
#define pIter(p)
Definition: monomials.h:44
poly res
Definition: myNF.cc:322
BOOLEAN ntGreater(number a, number b, const coeffs cf)
Definition: transext.cc:712
static int ntParDeg(number a, const coeffs cf)
Definition: transext.cc:2173
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:635
virtual void Reset()=0
Sets the enumerator to its initial position: -1, which is before the first element in the collection...
const char * p_Read(const char *st, poly &rc, const ring r)
Definition: p_polys.cc:1353
number ntCopyMap(number a, const coeffs cf, const coeffs dst)
Definition: transext.cc:1884
const char * ntRead(const char *s, number *a, const coeffs cf)
Definition: transext.cc:1531
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:932
static void ntClearDenominators(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: transext.cc:2319
const ring r
Definition: syzextra.cc:208
number ntMapPP(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:2033
Coefficient rings, fields and other domains suitable for Singular polynomials.
poly p_Farey(poly p, number N, const ring r)
Definition: p_polys.cc:61
CanonicalForm ntConvSingNFactoryN(number n, BOOLEAN, const coeffs cf)
Definition: transext.cc:2164
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
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
poly p_One(const ring r)
Definition: p_polys.cc:1318
Concrete implementation of enumerators over polynomials.
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:465
This is a polynomial enumerator for simple iteration over coefficients of polynomials.
number ntInit(long i, const coeffs cf)
Definition: transext.cc:615
#define assume(x)
Definition: mod2.h:405
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1784
The main handler for Singular numbers which are suitable for Singular polynomials.
Templated enumerator interface for simple iteration over a generic collection of T's.
Definition: Enumerator.h:124
number ntFarey(number p, number n, const coeffs cf)
Definition: transext.cc:2493
number ntGetDenom(number &a, const coeffs cf)
TODO: normalization of a!?
Definition: transext.cc:472
number ntGenAlg(number a, const coeffs cf, const coeffs dst)
Definition: transext.cc:1999
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1075
void StringAppendS(const char *st)
Definition: reporter.cc:107
#define A
Definition: sirandom.c:23
poly convFactoryPSingP(const CanonicalForm &f, const ring r)
Definition: clapconv.cc:41
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:72
number ntMapP0(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:1868
static const n_coeffType ID
Our own type!
Definition: transext.cc:80
number nlModP(number q, const coeffs Q, const coeffs Zp)
Definition: longrat.cc:1368
virtual reference Current()=0
Gets the current element in the collection (read and write).
number ntNeg(number a, const coeffs cf)
this is in-place, modifies a
Definition: transext.cc:596
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:923
All the auxiliary stuff.
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
int m
Definition: cfEzgcd.cc:119
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition: coeffs.h:558
static BOOLEAN ntCoeffIsEqual(const coeffs cf, n_coeffType n, void *param)
Definition: transext.cc:1559
#define NUMIS1(f)
TRUE iff num. represents 1.
Definition: transext.cc:68
struct for passing initialization parameters to naInitChar
Definition: transext.h:92
const char *const nDivBy0
Definition: numbers.h:83
FILE * f
Definition: checklibs.c:7
static BOOLEAN p_IsOne(const poly p, const ring R)
either poly(1) or gen(k)?!
Definition: p_polys.h:1792
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
static char * rRingVar(short i, const ring r)
Definition: ring.h:525
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:902
BOOLEAN ntGreaterZero(number a, const coeffs cf)
forward declarations
Definition: transext.cc:765
number ntChineseRemainder(number *x, number *q, int rl, BOOLEAN sym, CFArray &inv_cache, const coeffs cf)
Definition: transext.cc:2463
number ntRePart(number a, const coeffs cf)
static poly p_LmFreeAndNext(poly p, ring)
Definition: p_polys.h:699
CanonicalForm factor
Definition: facAbsFact.cc:101
void definiteGcdCancellation(number a, const coeffs cf, BOOLEAN simpleTestsHaveAlreadyBeenPerformed)
modifies a
Definition: transext.cc:1332
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
BOOLEAN rEqual(ring r1, ring r2, BOOLEAN qr)
returns TRUE, if r1 equals r2 FALSE, otherwise Equality is determined componentwise, if qr == 1, then qrideal equality is tested, as well
Definition: ring.cc:1633
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:720
go into polynomials over an alg. extension recursively
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:422
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition: p_polys.cc:4291
#define p_Test(p, r)
Definition: p_polys.h:160
number ntCopy(number a, const coeffs cf)
Definition: transext.cc:393
static void ntClearContent(ICoeffsEnumerator &numberCollectionEnumerator, number &c, const coeffs cf)
Definition: transext.cc:2230
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3621
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:850
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
#define omGetSpecBin(size)
Definition: omBin.h:11
(number), see longrat.h
Definition: coeffs.h:110
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1402
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:484
void heuristicGcdCancellation(number a, const coeffs cf)
Definition: transext.cc:1255
n_coeffType
Definition: coeffs.h:27
CanonicalForm cf
Definition: cfModGcd.cc:4024
static FORCE_INLINE void n_CoeffWrite(const coeffs r, BOOLEAN details=TRUE)
output the coeff description
Definition: coeffs.h:737
#define NULL
Definition: omList.c:10
CanonicalForm convSingPFactoryP(poly p, const ring r)
Definition: clapconv.cc:88
number ntAdd(number a, number b, const coeffs cf)
Definition: transext.cc:871
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:452
static number ntParameter(const int iParameter, const coeffs cf)
return the specified parameter as a number in the given trans.ext.
Definition: transext.cc:2182
CanonicalForm den(const CanonicalForm &f)
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:448
BOOLEAN ntEqual(number a, number b, const coeffs cf)
Definition: transext.cc:347
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition: coeffs.h:615
virtual bool MoveNext()=0
Advances the enumerator to the next element of the collection. returns true if the enumerator was suc...
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define R
Definition: sirandom.c:26
number ntMapZ0(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:1854
#define SR_INT
Definition: longrat.h:65
void ntPower(number a, int exp, number *b, const coeffs cf)
Definition: transext.cc:1071
poly p_ChineseRemainder(poly *xx, number *x, number *q, int rl, CFArray &inv_cache, const ring R)
Definition: p_polys.cc:94
void ntKillChar(coeffs cf)
Definition: transext.cc:2147
Variable x
Definition: cfModGcd.cc:4023
number ntConvFactoryNSingN(const CanonicalForm n, const coeffs cf)
Definition: transext.cc:2152
static FORCE_INLINE number n_GetDenom(number &n, const coeffs r)
return the denominator of n (if elements of r are by nature not fractional, result is 1) ...
Definition: coeffs.h:604
#define pNext(p)
Definition: monomials.h:43
#define ntCoeffs
Definition: transext.cc:90
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:436
#define p_GetCoeff(p, r)
Definition: monomials.h:57
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:687
number ntGetNumerator(number &a, const coeffs cf)
TODO: normalization of a!?
Definition: transext.cc:411
static FORCE_INLINE BOOLEAN nCoeff_is_Extension(const coeffs r)
Definition: coeffs.h:844
int ntIsParam(number m, const coeffs cf)
if m == var(i)/1 => return i,
Definition: transext.cc:2204
p exp[i]
Definition: DebugPrint.cc:39
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1018
number ntMap0P(number a, const coeffs src, const coeffs dst)
Definition: transext.cc:2009
#define SR_HDL(A)
Definition: tgb.cc:35
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
#define ntRing
Definition: transext.cc:84
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:237
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:473
void p_Write(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:206
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), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:495
#define ADD_COMPLEXITY
complexity increase due to + and -
Definition: transext.cc:62
kBucketDestroy & P
Definition: myNF.cc:191
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:884
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:418
static Poly * h
Definition: janet.cc:978
number ntCopyAlg(number a, const coeffs cf, const coeffs dst)
Definition: transext.cc:1992
int BOOLEAN
Definition: auxiliary.h:131
const poly b
Definition: syzextra.cc:213
number ntGcd(number a, number b, const coeffs cf)
Definition: transext.cc:1669
int p_Var(poly m, const ring r)
Definition: p_polys.cc:4435
#define MULT_COMPLEXITY
complexity increase due to * and /
Definition: transext.cc:63
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1302
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1025
void ntCoeffWrite(const coeffs cf, BOOLEAN details)
Definition: transext.cc:775
void p_String0Short(const poly p, ring lmRing, ring tailRing)
print p in a short way, if possible
Definition: polys0.cc:97
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
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:939
BOOLEAN ntInitChar(coeffs cf, void *infoStruct)
Initialize the coeffs object.
Definition: transext.cc:2503
omBin fractionObjectBin
Definition: transext.cc:93