My Project  debian-1:4.1.1-p2+ds-4build3
kbuckets.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 
5 #include "omalloc/omalloc.h"
6 #include "misc/auxiliary.h"
7 #include "misc/options.h"
8 
10 #include "coeffs/coeffs.h"
11 #include "coeffs/numbers.h"
12 #include "polys/monomials/ring.h"
13 #include "polys/kbuckets.h"
14 
15 #ifdef HAVE_COEF_BUCKETS
16 #define USE_COEF_BUCKETS
17 #endif
18 
19 #ifdef USE_COEF_BUCKETS
20 #ifdef HAVE_RINGS_OLD
21 #define MULTIPLY_BUCKET(B,I) do \
22  { if (B->coef[I]!=NULL) \
23  { \
24  assume(p_IsConstant(B->Coef[i],B->bucket->ring)); \
25  B->buckets[I]=p_Mult_q(B->buckets[I],B->coef[I],B->bucket_ring); \
26  B->coef[I]=NULL; \
27  } \
28  } while(0) \
29  if (rField_is_Ring(B->bucket_ring)) B->buckets_length[i] = pLength(B->buckets[i]);
30 #else
31 #define MULTIPLY_BUCKET(B,I) do \
32  { if (B->coef[I]!=NULL) \
33  { \
34  B->buckets[I]=p_Mult_q(B->buckets[I],B->coef[I],B->bucket_ring); \
35  B->coef[I]=NULL; \
36  } \
37  } while(0)
38 #endif
39 #else
40 #define MULTIPLY_BUCKET(B,I)
41 #endif
43 #ifdef USE_COEF_BUCKETS
44 static int coef_start=1;
45 #endif
46 //////////////////////////////////////////////////////////////////////////
47 ///
48 /// Some internal stuff
49 ///
50 
51 // https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
52 #ifndef BUCKET_TWO_BASE
53 static inline int LOG4(int v)
54 {
55  const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
56  const unsigned int S[] = {1, 2, 4, 8, 16};
57 
58  unsigned int r = 0; // result of log4(v) will go here
59  if (v & b[4]) { v >>= S[4]; r |= S[3]; }
60  if (v & b[3]) { v >>= S[3]; r |= S[2]; }
61  if (v & b[2]) { v >>= S[2]; r |= S[1]; }
62  if (v & b[1]) { v >>= S[1]; r |= S[0]; }
63  return (int)r;
64 }
65 #endif
66 
67 // returns ceil(log_4(l))
68 static inline unsigned int pLogLength(unsigned int l)
69 {
70  unsigned int i = 0;
71 
72  if (l == 0) return 0;
73  l--;
74 #ifdef BUCKET_TWO_BASE
75  i=SI_LOG2(l);
76 #else
77  i=LOG4(l);
78 #endif
79  return i+1;
80 }
81 
82 // returns ceil(log_4(pLength(p)))
83 static inline unsigned int pLogLength(poly p)
84 {
85  return pLogLength((unsigned int) pLength(p));
86 }
87 
88 #ifdef KDEBUG
89 
90 #ifndef HAVE_PSEUDO_BUCKETS
91 BOOLEAN kbTest_i(kBucket_pt bucket, int i)
92 {//sBucketSortMerge
93  #ifdef USE_COEF_BUCKETS
94  assume(bucket->coef[0]==NULL);
95  if ((bucket->coef[i]!=NULL) && (bucket->buckets[i]==NULL))
96  {
97  dReportError("Bucket %d coef not NULL", i);
98  }
99  if (bucket->coef[i]!=NULL)
100  {
101  assume(bucket->buckets[i]!=NULL);
102  p_Test(bucket->coef[i],bucket->bucket_ring);
103  }
104  #endif
105  pFalseReturn(p_Test(bucket->buckets[i], bucket->bucket_ring));
106  if ((unsigned)bucket->buckets_length[i] != pLength(bucket->buckets[i]))
107  {
108  dReportError("Bucket %d lengths difference should:%d has:%d",
109  i, bucket->buckets_length[i], pLength(bucket->buckets[i]));
110  }
111  else if (i > 0 && (int) pLogLength(bucket->buckets_length[i]) > i)
112  {
113  dReportError("Bucket %d too long %d",
114  i, bucket->buckets_length[i]);
115  }
116  if (i==0 && bucket->buckets_length[0] > 1)
117  {
118  dReportError("Bucket 0 too long");
119  }
120  return TRUE;
121 }
122 
123 
124 BOOLEAN kbTest(kBucket_pt bucket)
125 {
126  #ifdef HAVE_COEF_BUCKETS
127  assume(bucket->coef[0]==NULL);
128  #endif
129  int i;
130  poly lm = bucket->buckets[0];
131 
132  omCheckAddrBin(bucket, kBucket_bin);
133  assume(bucket->buckets_used <= MAX_BUCKET);
134  if (! kbTest_i(bucket, 0)) return FALSE;
135  for (i=1; i<= (int) bucket->buckets_used; i++)
136  {
137  if (!kbTest_i(bucket, i)) return FALSE;
138  if (lm != NULL && bucket->buckets[i] != NULL
139  && p_LmCmp(lm, bucket->buckets[i], bucket->bucket_ring) != 1)
140  {
141  dReportError("Bucket %d larger or equal than lm", i);
142  if (p_LmCmp(lm, bucket->buckets[i], bucket->bucket_ring) ==0)
143  dReportError("Bucket %d equal to lm", i);
144  return FALSE;
145  }
146  if (!p_Test(bucket->buckets[i],bucket->bucket_ring))
147  {
148  dReportError("Bucket %d is not =0(4)", i);
149  return FALSE;
150  }
151  }
152 
153  for (; i<=MAX_BUCKET; i++)
154  {
155  if (bucket->buckets[i] != NULL || bucket->buckets_length[i] != 0)
156  {
157  dReportError("Bucket %d not zero", i);
158  return FALSE;
159  }
160  }
161  for(i=0;i<=MAX_BUCKET;i++)
162  {
163  if (bucket->buckets[i]!=NULL)
164  {
165  int j;
166  for(j=i+1;j<=MAX_BUCKET;j++)
167  {
168  if (bucket->buckets[j]==bucket->buckets[i])
169  {
170  dReportError("Bucket %d %d equal", i,j);
171  return FALSE;
172  }
173  }
174  }
175  #ifdef HAVE_COEF_BUCKETS
176  if (bucket->coef[i]!=NULL)
177  {
178  int j;
179  for(j=i+1;j<=MAX_BUCKET;j++)
180  {
181  if (bucket->coef[j]==bucket->coef[i])
182  {
183  dReportError("internal coef %d %d equal", i,j);
184  return FALSE;
185  }
186  }
187  }
188  #endif
189  }
190  return TRUE;
191 }
192 
193 #else // HAVE_PSEUDO_BUCKETS
195 {
196  return TRUE;
197 }
198 #endif // ! HAVE_PSEUDO_BUCKETS
199 #endif // KDEBUG
200 
201 //////////////////////////////////////////////////////////////////////////
202 ///
203 /// Creation/Destruction of buckets
204 ///
205 
206 kBucket_pt kBucketCreate(const ring bucket_ring)
207 {
208  assume(bucket_ring != NULL);
210  bucket->bucket_ring = bucket_ring;
211  return bucket;
212 }
213 void kBucketDestroy(kBucket_pt *bucket_pt)
214 {
215  omFreeBin(*bucket_pt, kBucket_bin);
216  *bucket_pt = NULL;
217 }
218 
219 
221 {
222  kBucket_pt bucket = *bucket_pt;
223  kbTest(bucket);
224  int i;
225  for (i=0; i<= bucket->buckets_used; i++)
226  {
227  p_Delete(&(bucket->buckets[i]), bucket->bucket_ring);
228 #ifdef USE_COEF_BUCKETS
229  p_Delete(&(bucket->coef[i]), bucket->bucket_ring);
230 #endif
231  }
232  omFreeBin(bucket, kBucket_bin);
233  *bucket_pt = NULL;
234 }
235 
236 /////////////////////////////////////////////////////////////////////////////
237 // Convertion from/to Bpolys
238 //
239 #ifndef HAVE_PSEUDO_BUCKETS
240 
241 inline void kBucketMergeLm(kBucket_pt bucket)
242 {
243  kbTest(bucket);
244  if (bucket->buckets[0] != NULL)
245  {
246  poly lm = bucket->buckets[0];
247  int i = 1;
248 #ifdef BUCKET_TWO_BASE
249  int l = 2;
250  while ( bucket->buckets_length[i] >= l)
251  {
252  i++;
253  l = l << 1;
254  }
255 #else
256  int l = 4;
257  while ( bucket->buckets_length[i] >= l)
258  {
259  i++;
260  l = l << 2;
261  }
262 #endif
263 #ifndef USE_COEF_BUCKETS
264  MULTIPLY_BUCKET(bucket,i);
265  pNext(lm) = bucket->buckets[i];
266  bucket->buckets[i] = lm;
267  bucket->buckets_length[i]++;
268  assume(i <= bucket->buckets_used+1);
269  if (i > bucket->buckets_used) bucket->buckets_used = i;
270  bucket->buckets[0] = NULL;
271  bucket->buckets_length[0] = 0;
272  kbTest(bucket);
273 #else
274  if (i > bucket->buckets_used) bucket->buckets_used = i;
275  assume(i!=0);
276  if (bucket->buckets[i]!=NULL)
277  {
278  MULTIPLY_BUCKET(bucket,i);
279  pNext(lm) = bucket->buckets[i];
280  bucket->buckets[i] = lm;
281  bucket->buckets_length[i]++;
282  assume(i <= bucket->buckets_used+1);
283  }
284  else
285  {
286  #if 1
287  assume(bucket->buckets[i]==NULL);
288  assume(bucket->coef[0]==NULL);
289  assume(pLength(lm)==1);
290  assume(pNext(lm)==NULL);
291  number coef=p_GetCoeff(lm,bucket->bucket_ring);
292  //WARNING: not thread_safe
293  p_SetCoeff0(lm, n_Init(1,bucket->bucket_ring), bucket->bucket_ring);
294  bucket->buckets[i]=lm;
295  bucket->buckets_length[i]=1;
296  bucket->coef[i]=p_NSet(n_Copy(coef,bucket->bucket_ring),bucket->bucket_ring);
297 
298  bucket->buckets[i]=lm;
299  bucket->buckets_length[i]=1;
300  #else
301  MULTIPLY_BUCKET(bucket,i);
302  pNext(lm) = bucket->buckets[i];
303  bucket->buckets[i] = lm;
304  bucket->buckets_length[i]++;
305  assume(i <= bucket->buckets_used+1);
306  #endif
307  }
308  bucket->buckets[0]=NULL;
309  bucket->buckets_length[0] = 0;
310  bucket->coef[0]=NULL;
311  kbTest(bucket);
312  #endif
313  }
314 
315 }
316 
318 {
319  int i;
320 
321  for (i = 0;i<=MAX_BUCKET;i++)
322  {
323  if (bucket->buckets[i] != NULL) return FALSE;
324  #ifdef HAVE_COEF_BUCKETS
325  if (bucket->coef[i] != NULL) return FALSE;
326  #endif
327  if (bucket->buckets_length[i] != 0) return FALSE;
328  }
329  return TRUE;
330 }
331 
332 void kBucketInit(kBucket_pt bucket, poly lm, int length)
333 {
334  //assume(false);
335  assume(bucket != NULL);
336  assume(length <= 0 || (unsigned)length == pLength(lm));
337  assume(kBucketIsCleared(bucket));
338 
339  if (lm == NULL) return;
340 
341  if (length <= 0)
342  length = pLength(lm);
343 
344  bucket->buckets[0] = lm;
345  #ifdef HAVE_COEF_BUCKETS
346  assume(bucket->coef[0]==NULL);
347  #endif
348  #ifdef USE_COEF_BUCKETS
349  bucket->coef[0]=NULL;
350  #endif
351  if (lm!=NULL)
352  bucket->buckets_length[0] = 1;
353  else
354  bucket->buckets_length[0]= 0;
355  if (length > 1)
356  {
357  unsigned int i = pLogLength(length-1);
358  bucket->buckets[i] = pNext(lm);
359  pNext(lm) = NULL;
360  bucket->buckets_length[i] = length-1;
361  bucket->buckets_used = i;
362  }
363  else
364  {
365  bucket->buckets_used = 0;
366  }
367 }
368 
370 {
371  assume(bucket->buckets_used<=MAX_BUCKET);
372  MULTIPLY_BUCKET(bucket,1);
373  kbTest(bucket);
374  poly p = bucket->buckets[1];
375  poly lm;
376  int pl = bucket->buckets_length[1];//, i;
377  int i;
378  bucket->buckets[1] = NULL;
379  bucket->buckets_length[1] = 0;
380  #ifdef USE_COEF_BUCKETS
381  assume(bucket->coef[1]==NULL);
382  #endif
383  ring r=bucket->bucket_ring;
384 
385 
386  for (i=1; i<=bucket->buckets_used; i++)
387  {
388  #ifdef USE_COEF_BUCKETS
389  if (bucket->coef[i]!=NULL)
390  {
391  assume(bucket->buckets[i]!=NULL);
392  p = p_Plus_mm_Mult_qq(p, bucket->coef[i], bucket->buckets[i],
393  pl, bucket->buckets_length[i], r);
394  p_Delete(&bucket->coef[i],r);
395  p_Delete(&bucket->buckets[i],r);
396  }
397  else
398  p = p_Add_q(p, bucket->buckets[i],
399  pl, bucket->buckets_length[i], r);
400  #else
401  p = p_Add_q(p, bucket->buckets[i],
402  pl, bucket->buckets_length[i], r);
403  #endif
404  if (i==1) continue;
405  bucket->buckets[i] = NULL;
406  bucket->buckets_length[i] = 0;
407  }
408  #ifdef HAVE_COEF_BUCKETS
409  assume(bucket->coef[0]==NULL);
410  #endif
411  lm = bucket->buckets[0];
412  if (lm != NULL)
413  {
414  pNext(lm) = p;
415  p = lm;
416  pl++;
417  bucket->buckets[0] = NULL;
418  bucket->buckets_length[0] = 0;
419  }
420  if (pl > 0)
421  {
422  i = pLogLength(pl);
423  bucket->buckets[i] = p;
424  bucket->buckets_length[i] = pl;
425  }
426  else
427  {
428  i = 0;
429  }
430  bucket->buckets_used = i;
431  assume(bucket->buckets_used <= MAX_BUCKET);
432  #ifdef USE_COEF_BUCKETS
433  assume(bucket->coef[0]==NULL);
434  assume(bucket->coef[i]==NULL);
435  #endif
436  assume(pLength(p) == (unsigned)pl);
437  //if (TEST_OPT_PROT) { Print("C(%d)",pl); }
438  kbTest(bucket);
439  return i;
440 }
441 
442 void kBucketClear(kBucket_pt bucket, poly *p, int *length)
443 {
444  int i = kBucketCanonicalize(bucket);
445  if (i > 0)
446  {
447  #ifdef USE_COEF_BUCKETS
448  MULTIPLY_BUCKET(bucket,i);
449  //bucket->coef[i]=NULL;
450  #endif
451  *p = bucket->buckets[i];
452  *length = bucket->buckets_length[i];
453  bucket->buckets[i] = NULL;
454  bucket->buckets_length[i] = 0;
455  bucket->buckets_used = 0;
456 
457  }
458  else
459  {
460  *p = NULL;
461  *length = 0;
462  }
463 }
464 
465 void kBucketSetLm(kBucket_pt bucket, poly lm)
466 {
467  kBucketMergeLm(bucket);
468  pNext(lm) = NULL;
469  bucket->buckets[0] = lm;
470  bucket->buckets_length[0] = 1;
471 }
472 
473 #else // HAVE_PSEUDO_BUCKETS
474 
475 void kBucketInit(kBucket_pt bucket, poly lm, int length)
476 {
477  int i;
478 
479  assume(bucket != NULL);
480  assume(length <= 0 || length == pLength(lm));
481 
482  bucket->p = lm;
483  if (length <= 0) bucket->l = pLength(lm);
484  else bucket->l = length;
485 
486 }
487 
488 const poly kBucketGetLm(kBucket_pt bucket)
489 {
490  return bucket->p;
491 }
492 
494 {
495  poly lm = bucket->p;
496  assume(pLength(bucket->p) == bucket->l);
497  pIter(bucket->p);
498  (bucket->l)--;
499  pNext(lm) = NULL;
500  return lm;
501 }
502 
503 void kBucketClear(kBucket_pt bucket, poly *p, int *length)
504 {
505  assume(pLength(bucket->p) == bucket->l);
506  *p = bucket->p;
507  *length = bucket->l;
508  bucket->p = NULL;
509  bucket->l = 0;
510 }
511 
512 #endif // ! HAVE_PSEUDO_BUCKETS
513 //////////////////////////////////////////////////////////////////////////
514 ///
515 /// For changing the ring of the Bpoly to new_tailBin
516 ///
518  ring new_tailRing, omBin new_tailBin,
519  pShallowCopyDeleteProc p_shallow_copy_delete)
520 {
521 #ifndef HAVE_PSEUDO_BUCKETS
522  int i;
523 
524  kBucketCanonicalize(bucket);
525  for (i=0; i<= bucket->buckets_used; i++)
526  if (bucket->buckets[i] != NULL)
527  {
528  MULTIPLY_BUCKET(bucket,i);
529  bucket->buckets[i] = p_shallow_copy_delete(bucket->buckets[i],
530  bucket->bucket_ring,
531  new_tailRing,
532  new_tailBin);
533  }
534 #else
535  bucket->p = p_shallow_copy_delete(p,
536  bucket_ring,
537  new_tailRing,
538  new_tailBin);
539 #endif
540  bucket->bucket_ring = new_tailRing;
541 }
542 
543 //////////////////////////////////////////////////////////////////////////
544 ///
545 /// Bucket number i from bucket is out of length sync, resync
546 ///
547 void kBucketAdjust(kBucket_pt bucket, int i) {
548 
549  MULTIPLY_BUCKET(bucket,i);
550 
551  int l1 = bucket->buckets_length[i];
552  poly p1 = bucket->buckets[i];
553  bucket->buckets[i] = NULL;
554  bucket->buckets_length[i] = 0;
555  i = pLogLength(l1);
556 
557  while (bucket->buckets[i] != NULL)
558  {
559  //kbTest(bucket);
560  MULTIPLY_BUCKET(bucket,i);
561  p1 = p_Add_q(p1, bucket->buckets[i],
562  l1, bucket->buckets_length[i], bucket->bucket_ring);
563  bucket->buckets[i] = NULL;
564  bucket->buckets_length[i] = 0;
565  i = pLogLength(l1);
566  }
567 
568  bucket->buckets[i] = p1;
569  bucket->buckets_length[i]=l1;
570  if (i >= bucket->buckets_used)
571  bucket->buckets_used = i;
572  else
573  kBucketAdjustBucketsUsed(bucket);
574 }
575 
576 //////////////////////////////////////////////////////////////////////////
577 ///
578 /// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
579 ///
580 void kBucket_Mult_n(kBucket_pt bucket, number n)
581 {
582 #ifndef HAVE_PSEUDO_BUCKETS
583  kbTest(bucket);
584  ring r=bucket->bucket_ring;
585  int i;
586 
587  for (i=0; i<= bucket->buckets_used; i++)
588  {
589  if (bucket->buckets[i] != NULL)
590  {
591 #ifdef USE_COEF_BUCKETS
592  if (i<coef_start)
593  bucket->buckets[i] = __p_Mult_nn(bucket->buckets[i], n, r);
594  /* Frank Seelisch on March 11, 2010:
595  This looks a bit strange: The following "if" is indented
596  like the previous line of code. But coded as it is,
597  it should actually be two spaces less indented.
598  Question: Should the following "if" also only be
599  performed when "(i<coef_start)" is true?
600  For the time being, I leave it as it is. */
601  if (rField_is_Ring(r) && !(rField_is_Domain(r)))
602  {
603  bucket->buckets_length[i] = pLength(bucket->buckets[i]);
604  kBucketAdjust(bucket, i);
605  }
606  else
607  if (bucket->coef[i]!=NULL)
608  {
609  bucket->coef[i] = __p_Mult_nn(bucket->coef[i],n,r);
610  }
611  else
612  {
613  bucket->coef[i] = p_NSet(n_Copy(n,r),r);
614  }
615 #else
616  bucket->buckets[i] = __p_Mult_nn(bucket->buckets[i], n, r);
617  if (rField_is_Ring(r) && !(rField_is_Domain(r)))
618  {
619  bucket->buckets_length[i] = pLength(bucket->buckets[i]);
620  kBucketAdjust(bucket, i);
621  }
622 #endif
623  }
624  }
625  kbTest(bucket);
626 #else
627  bucket->p = __p_Mult_nn(bucket->p, n, bucket->bucket_ring);
628 #endif
629 }
630 
631 
632 //////////////////////////////////////////////////////////////////////////
633 ///
634 /// Add to Bucket a poly ,i.e. Bpoly == q+Bpoly
635 ///
636 void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
637 {
638  if (q == NULL) return;
639  assume(*l <= 0 || pLength(q) == *l);
640 
641  int i, l1;
642  ring r = bucket->bucket_ring;
643 
644  if (*l <= 0)
645  {
646  l1 = pLength(q);
647  *l = l1;
648  }
649  else
650  l1 = *l;
651 
652  kBucketMergeLm(bucket);
653  kbTest(bucket);
654  i = pLogLength(l1);
655 
656  while (bucket->buckets[i] != NULL)
657  {
658  //MULTIPLY_BUCKET(bucket,i);
659  #ifdef USE_COEF_BUCKETS
660  if (bucket->coef[i]!=NULL)
661  {
662  q = p_Plus_mm_Mult_qq(q, bucket->coef[i], bucket->buckets[i],
663  l1, bucket->buckets_length[i], r);
664  p_Delete(&bucket->coef[i],r);
665  p_Delete(&bucket->buckets[i],r);
666  }
667  else
668  q = p_Add_q(q, bucket->buckets[i],
669  l1, bucket->buckets_length[i], r);
670  #else
671  q = p_Add_q(q, bucket->buckets[i],
672  l1, bucket->buckets_length[i], r);
673  #endif
674  bucket->buckets[i] = NULL;
675  bucket->buckets_length[i] = 0;
676  i = pLogLength(l1);
677  assume(i<= MAX_BUCKET);
678  assume(bucket->buckets_used<= MAX_BUCKET);
679  }
680 
681  kbTest(bucket);
682  bucket->buckets[i] = q;
683  bucket->buckets_length[i]=l1;
684  if (i >= bucket->buckets_used)
685  bucket->buckets_used = i;
686  else
687  kBucketAdjustBucketsUsed(bucket);
688  kbTest(bucket);
689 }
690 
691 
692 
693 //////////////////////////////////////////////////////////////////////////
694 ///
695 /// Bpoly == Bpoly - m*p; where m is a monom
696 /// Does not destroy p and m
697 /// assume (*l <= 0 || pLength(p) == *l)
698 void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l,
699  poly spNoether)
700 {
701  assume(*l <= 0 || pLength(p) == *l);
702  int i, l1;
703  poly p1 = p;
704  ring r = bucket->bucket_ring;
705 
706  if (*l <= 0)
707  {
708  l1 = pLength(p1);
709  *l = l1;
710  }
711  else
712  l1 = *l;
713 
714  if (m == NULL || p == NULL) return;
715 
716 #ifndef HAVE_PSEUDO_BUCKETS
717  kBucketMergeLm(bucket);
718  kbTest(bucket);
719  i = pLogLength(l1);
720 
721 #if defined(HAVE_PLURAL)
722  if ((rField_is_Ring(r) && !(rField_is_Domain(r)))
723  ||(rIsPluralRing(r)))
724  {
725  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
726  p1=pp_Mult_mm(p,m,r);
727  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
728  l1=pLength(p1);
729  i = pLogLength(l1);
730  }
731  else
732 #endif
733  {
734  if ((i <= bucket->buckets_used) && (bucket->buckets[i] != NULL))
735  {
736  assume(pLength(bucket->buckets[i])==(unsigned)bucket->buckets_length[i]);
737 //#ifdef USE_COEF_BUCKETS
738 // if(bucket->coef[i]!=NULL)
739 // {
740 // poly mult=p_Mult_mm(bucket->coef[i],m,r);
741 // bucket->coef[i]=NULL;
742 // p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], mult, p1,
743 // bucket->buckets_length[i], l1,
744 // spNoether, r);
745 // }
746 // else
747 //#endif
748  MULTIPLY_BUCKET(bucket,i);
749  p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], m, p1,
750  bucket->buckets_length[i], l1,
751  spNoether, r);
752  l1 = bucket->buckets_length[i];
753  bucket->buckets[i] = NULL;
754  bucket->buckets_length[i] = 0;
755  i = pLogLength(l1);
756  }
757  else
758  {
759  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
760  if (spNoether != NULL)
761  {
762  l1 = -1;
763  p1 = r->p_Procs->pp_Mult_mm_Noether(p1, m, spNoether, l1, r);
764  i = pLogLength(l1);
765  }
766  else
767  {
768  p1 = r->p_Procs->pp_Mult_mm(p1, m, r);
769  }
770  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
771  }
772  }
773 
774  while (bucket->buckets[i] != NULL)
775  {
776  //kbTest(bucket);
777  MULTIPLY_BUCKET(bucket,i);
778  p1 = p_Add_q(p1, bucket->buckets[i],
779  l1, bucket->buckets_length[i], r);
780  bucket->buckets[i] = NULL;
781  bucket->buckets_length[i] = 0;
782  i = pLogLength(l1);
783  }
784 
785  bucket->buckets[i] = p1;
786  bucket->buckets_length[i]=l1;
787  if (i >= bucket->buckets_used)
788  bucket->buckets_used = i;
789  else
790  kBucketAdjustBucketsUsed(bucket);
791 #else // HAVE_PSEUDO_BUCKETS
792  bucket->p = p_Minus_mm_Mult_qq(bucket->p, m, p,
793  bucket->l, l1,
794  spNoether, r);
795 #endif
796 }
797 
798 //////////////////////////////////////////////////////////////////////////
799 ///
800 /// Bpoly == Bpoly + m*p; where m is a monom
801 /// Does not destroy p and m
802 /// assume (l <= 0 || pLength(p) == l)
803 void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l)
804 {
805  assume((!rIsPluralRing(bucket->bucket_ring))||p_IsConstant(m, bucket->bucket_ring));
806  assume(l <= 0 || pLength(p) == (unsigned)l);
807  int i, l1;
808  poly p1 = p;
809  ring r = bucket->bucket_ring;
810 
811  if (m == NULL || p == NULL) return;
812 
813  if (l <= 0)
814  {
815  l1 = pLength(p1);
816  l = l1;
817  }
818  else
819  l1 = l;
820 
821  kBucketMergeLm(bucket);
822  kbTest(bucket);
823  i = pLogLength(l1);
824  #ifdef USE_COEF_BUCKETS
825  number n=n_Init(1,r->cf);
826  #endif
827  if (i <= bucket->buckets_used && bucket->buckets[i] != NULL)
828  {
829  //if (FALSE){
830  #ifdef USE_COEF_BUCKETS
831  if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
832  {
833  number orig_coef=p_GetCoeff(bucket->coef[i],r);
834  //we take ownership:
835  p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
836  number add_coef=n_Copy(p_GetCoeff(m,r),r);
837  number gcd=n_Gcd(add_coef, orig_coef,r);
838 
839  if (!(n_IsOne(gcd,r)))
840  {
841  number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
842  number add_coef2=n_ExactDiv(add_coef, gcd,r);
843  n_Delete(&orig_coef,r);
844  n_Delete(&add_coef,r);
845  orig_coef=orig_coef2;
846  add_coef=add_coef2;
847 
848  //p_Mult_nn(bucket->buckets[i], orig_coef,r);
849  n_Delete(&n,r);
850  n=gcd;
851  }
852 
853  //assume(n_IsOne(n,r));
854  number backup=p_GetCoeff(m,r);
855 
856  p_SetCoeff0(m,add_coef,r);
857  bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
858 
859  n_Delete(&orig_coef,r);
860  p_Delete(&bucket->coef[i],r);
861 
862  p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
863  bucket->buckets_length[i], l1, r);
864  l1=bucket->buckets_length[i];
865  bucket->buckets[i]=NULL;
866  bucket->buckets_length[i] = 0;
867  i = pLogLength(l1);
868  assume(l1==pLength(p1));
869 
870  p_SetCoeff(m,backup,r); //deletes add_coef
871  }
872  else
873  #endif
874  {
875  MULTIPLY_BUCKET(bucket,i);
876  p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
877  bucket->buckets_length[i], l1, r);
878  l1 = bucket->buckets_length[i];
879  bucket->buckets[i] = NULL;
880  bucket->buckets_length[i] = 0;
881  i = pLogLength(l1);
882  }
883  }
884  else
885  {
886  #ifdef USE_COEF_BUCKETS
887  number swap_n=p_GetCoeff(m,r);
888 
889  assume(n_IsOne(n,r));
890  p_SetCoeff0(m,n,r);
891  n=swap_n;
892  //p_SetCoeff0(n, swap_n, r);
893  //p_GetCoeff0(n, swap_n,r);
894  #endif
895  p1 = r->p_Procs->pp_Mult_mm(p1, m, r);
896  #ifdef USE_COEF_BUCKETS
897  //m may not be changed
898  p_SetCoeff(m,n_Copy(n,r),r);
899  #endif
900  }
901 
902  while ((bucket->buckets[i] != NULL) && (p1!=NULL))
903  {
904  assume(i!=0);
905  #ifdef USE_COEF_BUCKETS
906  if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
907  {
908  number orig_coef=p_GetCoeff(bucket->coef[i],r);
909  //we take ownership:
910  p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
911  number add_coef=n_Copy(n,r);
912  number gcd=n_Gcd(add_coef, orig_coef,r);
913 
914  if (!(n_IsOne(gcd,r)))
915  {
916  number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
917  number add_coef2=n_ExactDiv(add_coef, gcd,r);
918  n_Delete(&orig_coef,r);
919  n_Delete(&n,r);
920  n_Delete(&add_coef,r);
921  orig_coef=orig_coef2;
922  add_coef=add_coef2;
923  //p_Mult_nn(bucket->buckets[i], orig_coef,r);
924  n=gcd;
925  }
926  //assume(n_IsOne(n,r));
927  bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
928  p1=__p_Mult_nn(p1,add_coef,r);
929 
930  p1 = p_Add_q(p1, bucket->buckets[i],r);
931  l1=pLength(p1);
932 
933  bucket->buckets[i]=NULL;
934  n_Delete(&orig_coef,r);
935  p_Delete(&bucket->coef[i],r);
936  //l1=bucket->buckets_length[i];
937  assume(l1==pLength(p1));
938  }
939  else
940  #endif
941  {
942  //don't do that, pull out gcd
943  #ifdef USE_COEF_BUCKETS
944  if(!(n_IsOne(n,r)))
945  {
946  p1=__p_Mult_nn(p1, n, r);
947  n_Delete(&n,r);
948  n=n_Init(1,r);
949  }
950  #endif
951  MULTIPLY_BUCKET(bucket,i);
952  p1 = p_Add_q(p1, bucket->buckets[i],
953  l1, bucket->buckets_length[i], r);
954  bucket->buckets[i] = NULL;
955  bucket->buckets_length[i] = 0;
956  }
957  i = pLogLength(l1);
958  }
959 
960  bucket->buckets[i] = p1;
961 #ifdef USE_COEF_BUCKETS
962  assume(bucket->coef[i]==NULL);
963 
964  if (!(n_IsOne(n,r)))
965  {
966  bucket->coef[i]=p_NSet(n,r);
967  }
968  else
969  {
970  bucket->coef[i]=NULL;
971  n_Delete(&n,r);
972  }
973 
974  if (p1==NULL)
975  p_Delete(&bucket->coef[i],r);
976 #endif
977  bucket->buckets_length[i]=l1;
978  if (i > bucket->buckets_used)
979  bucket->buckets_used = i;
980  else
981  kBucketAdjustBucketsUsed(bucket);
982 
983  kbTest(bucket);
984 }
985 
986 poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append)
987 {
988  if (q == NULL) return append;
989  poly lm;
990  loop
991  {
992  lm = kBucketGetLm(bucket);
993  if (lm == NULL) return append;
994  if (p_LmCmp(lm, q, bucket->bucket_ring) == 1)
995  {
996  lm = kBucketExtractLm(bucket);
997  pNext(append) = lm;
998  pIter(append);
999  }
1000  else
1001  {
1002  return append;
1003  }
1004  }
1005 }
1006 
1007 /////////////////////////////////////////////////////////////////////////////
1008 //
1009 // Extract all monomials from bucket with component comp
1010 // Return as a polynomial *p with length *l
1011 // In other words, afterwards
1012 // Bpoly = Bpoly - (poly consisting of all monomials with component comp)
1013 // and components of monomials of *p are all 0
1014 //
1015 
1016 // Hmm... for now I'm too lazy to implement those independent of currRing
1017 // But better declare it extern than including polys.h
1018 extern void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r);
1019 
1021  long comp,
1022  poly *r_p, int *l)
1023 {
1024  poly p = NULL, q;
1025  int i, lp = 0, lq;
1026 
1027 #ifndef HAVE_PSEUDO_BUCKETS
1028  kBucketMergeLm(bucket);
1029  for (i=1; i<=bucket->buckets_used; i++)
1030  {
1031  if (bucket->buckets[i] != NULL)
1032  {
1033  MULTIPLY_BUCKET(bucket,i);
1034  p_TakeOutComp(&(bucket->buckets[i]), comp, &q, &lq, bucket->bucket_ring);
1035  if (q != NULL)
1036  {
1037  assume(pLength(q) == (unsigned)lq);
1038  bucket->buckets_length[i] -= lq;
1039  assume(pLength(bucket->buckets[i]) == (unsigned)bucket->buckets_length[i]);
1040  p = p_Add_q(p, q, lp, lq, bucket->bucket_ring);
1041  }
1042  }
1043  }
1044  kBucketAdjustBucketsUsed(bucket);
1045 #else
1046  p_TakeOutComp(&(bucket->p), comp, &p, &lp,bucket->bucket_ring);
1047  (bucket->l) -= lp;
1048 #endif
1049  *r_p = p;
1050  *l = lp;
1051 
1052  kbTest(bucket);
1053 }
1054 
1055 /////////////////////////////////////////////////////////////////////////////
1056 // Reduction of Bpoly with a given poly
1057 //
1058 
1059 extern int ksCheckCoeff(number *a, number *b);
1060 
1062  poly p1, int l1,
1063  poly spNoether)
1064 {
1065  ring r=bucket->bucket_ring;
1066  assume((!rIsPluralRing(r))||p_LmEqual(p1,kBucketGetLm(bucket), r));
1067  assume(p1 != NULL &&
1068  p_DivisibleBy(p1, kBucketGetLm(bucket), r));
1069  assume(pLength(p1) == (unsigned) l1);
1070 
1071  poly a1 = pNext(p1), lm = kBucketExtractLm(bucket);
1072  BOOLEAN reset_vec=FALSE;
1073  number rn;
1074 
1075  /* we shall reduce bucket=bn*lm+... by p1=an*t+a1 where t=lm(p1)
1076  and an,bn shall be defined further down only if lc(p1)!=1
1077  we already know: an|bn and t|lm */
1078  if(a1==NULL)
1079  {
1080  p_LmDelete(&lm, r);
1081  return n_Init(1,r->cf);
1082  }
1083 
1084  if (! n_IsOne(pGetCoeff(p1),r->cf))
1085  {
1086  number an = pGetCoeff(p1), bn = pGetCoeff(lm);
1087 //StringSetS("##### an = "); nWrite(an); PrintS(StringEndS("\n")); // NOTE/TODO: use StringAppendS("\n"); omFree(s);
1088 //StringSetS("##### bn = "); nWrite(bn); PrintS(StringEndS("\n")); // NOTE/TODO: use StringAppendS("\n"); omFree(s);
1089  /* ksCheckCoeff: divide out gcd from an and bn: */
1090  int ct = ksCheckCoeff(&an, &bn,r->cf);
1091  /* the previous command returns ct=0 or ct=2 iff an!=1
1092  note: an is now 1 or -1 */
1093 
1094  /* setup factor for p1 which cancels leading terms */
1095  p_SetCoeff(lm, bn, r);
1096  if ((ct == 0) || (ct == 2))
1097  {
1098  /* next line used to be here before but is WRONG:
1099  kBucket_Mult_n(bucket, an);
1100  its use would result in a wrong sign for the tail of bucket
1101  in the reduction */
1102 
1103  /* correct factor for cancelation by changing sign if an=-1 */
1104  if (rField_is_Ring(r))
1105  lm = __p_Mult_nn(lm, an, r);
1106  else
1107  kBucket_Mult_n(bucket, an);
1108  }
1109  rn = an;
1110  }
1111  else
1112  {
1113  rn = n_Init(1,r->cf);
1114  }
1115 
1116  if (p_GetComp(p1, r) != p_GetComp(lm, r))
1117  {
1118  p_SetCompP(a1, p_GetComp(lm, r), r);
1119  reset_vec = TRUE;
1120  p_SetComp(lm, p_GetComp(p1, r), r);
1121  p_Setm(lm, r);
1122  }
1123 
1124  p_ExpVectorSub(lm, p1, r);
1125  l1--;
1126 
1127  assume((unsigned)l1==pLength(a1));
1128 #if 0
1129  BOOLEAN backuped=FALSE;
1130  number coef;
1131  //@Viktor, don't ignore coefficients on monomials
1132  if(l1==1) {
1133 
1134  //if (rField_is_Q(r)) {
1135  //avoid this for function fields, as gcds are expensive at the moment
1136 
1137 
1138  coef=p_GetCoeff(a1,r);
1139  lm=p_Mult_nn(lm, coef, r);
1140  p_SetCoeff0(a1, n_Init(1,r), r);
1141  backuped=TRUE;
1142  //WARNING: not thread_safe
1143  //deletes coef as side effect
1144  //}
1145  }
1146 #endif
1147 
1148  kBucket_Minus_m_Mult_p(bucket, lm, a1, &l1, spNoether);
1149 
1150 #if 0
1151  if (backuped)
1152  p_SetCoeff0(a1,coef,r);
1153 #endif
1154 
1155  p_LmDelete(&lm, r);
1156  if (reset_vec) p_SetCompP(a1, 0, r);
1157  kbTest(bucket);
1158  return rn;
1159 }
1160 
1161 #ifndef USE_COEF_BUCKETS
1163 {
1164  if (bucket->buckets[0]==NULL) return;
1165 
1166  ring r=bucket->bucket_ring;
1167  if (rField_is_Ring(r)) return;
1168 
1169  coeffs cf=r->cf;
1170  if (cf->cfSubringGcd==ndGcd) /* trivial gcd*/ return;
1171 
1172  number nn=pGetCoeff(bucket->buckets[0]);
1173  //if ((bucket->buckets_used==0)
1174  //&&(!n_IsOne(nn,cf)))
1175  //{
1176  // if (TEST_OPT_PROT) PrintS("@");
1177  // p_SetCoeff(bucket->buckets[0],n_Init(1,cf),r);
1178  // return;
1179  //}
1180 
1181  if (n_Size(nn,cf)<2) return;
1182 
1183  //kBucketAdjustBucketsUsed(bucket);
1184  number coef=n_Copy(nn,cf);
1185  // find an initial guess of a gcd
1186  for (int i=1; i<=bucket->buckets_used;i++)
1187  {
1188  if (bucket->buckets[i]!=NULL)
1189  {
1190  number t=p_InitContent(bucket->buckets[i],r);
1191  if (n_Size(t,cf)<2)
1192  {
1193  n_Delete(&t,cf);
1194  n_Delete(&coef,cf);
1195  return;
1196  }
1197  number t2=n_SubringGcd(coef,t,cf);
1198  n_Delete(&t,cf);
1199  n_Delete(&coef,cf);
1200  coef=t2;
1201  if (n_Size(coef,cf)<2) { n_Delete(&coef,cf);return;}
1202  }
1203  }
1204  // find the gcd
1205  for (int i=0; i<=bucket->buckets_used;i++)
1206  {
1207  if (bucket->buckets[i]!=NULL)
1208  {
1209  poly p=bucket->buckets[i];
1210  while(p!=NULL)
1211  {
1212  number t=n_SubringGcd(coef,pGetCoeff(p),cf);
1213  if (n_Size(t,cf)<2)
1214  {
1215  n_Delete(&t,cf);
1216  n_Delete(&coef,cf);
1217  return;
1218  }
1219  pIter(p);
1220  }
1221  }
1222  }
1223  // divided by the gcd
1224  if (TEST_OPT_PROT) PrintS("@");
1225  for (int i=bucket->buckets_used;i>=0;i--)
1226  {
1227  if (bucket->buckets[i]!=NULL)
1228  {
1229  poly p=bucket->buckets[i];
1230  while(p!=NULL)
1231  {
1232  number d = n_ExactDiv(pGetCoeff(p),coef,cf);
1233  p_SetCoeff(p,d,r);
1234  pIter(p);
1235  }
1236  }
1237  }
1238  n_Delete(&coef,cf);
1239 }
1240 #else
1241 static BOOLEAN nIsPseudoUnit(number n, ring r)
1242 {
1243  if (rField_is_Zp(r))
1244  return TRUE;
1245 
1246  if (rParameter(r)==NULL)
1247  {
1248  return (n_Size(n,r->cf)==1);
1249  }
1250  //if (r->parameter!=NULL)
1251  return (n_IsOne(n,r->cf) || n_IsMOne(n,r->cf));
1252 }
1253 
1254 void kBucketSimpleContent(kBucket_pt bucket)
1255 {
1256  ring r=bucket->bucket_ring;
1257  int i;
1258  //PrintS("HHHHHHHHHHHHH");
1259  for (i=0;i<=MAX_BUCKET;i++)
1260  {
1261  //if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]!=NULL))
1262  // PrintS("H2H2H2");
1263  if (i==0)
1264  {
1265  assume(bucket->buckets[i]==NULL);
1266  }
1267  if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]==NULL))
1268  return;
1269  }
1270  for (i=0;i<=MAX_BUCKET;i++)
1271  {
1272  //if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]!=NULL))
1273  // PrintS("H2H2H2");
1274  if (i==0)
1275  {
1276  assume(bucket->buckets[i]==NULL);
1277  }
1278  if ((bucket->buckets[i]!=NULL)
1279  && (nIsPseudoUnit(p_GetCoeff(bucket->coef[i],r),r)))
1280  return;
1281  }
1282  //return;
1283 
1284  number coef=n_Init(0,r);
1285  //ATTENTION: will not work correct for GB over ring
1286  //if (TEST_OPT_PROT)
1287  // PrintS("CCCCCCCCCCCCC");
1288  for (i=MAX_BUCKET;i>=0;i--)
1289  {
1290  if (i==0)
1291  {
1292  assume(bucket->buckets[i]==NULL);
1293  }
1294  if (bucket->buckets[i]!=NULL)
1295  {
1296  assume(bucket->coef[i]!=NULL);
1297  assume(!(n_IsZero(pGetCoeff(bucket->coef[i]),r)));
1298 
1299  //in this way it should crash on programming errors, yeah
1300  number temp=n_Gcd(coef, pGetCoeff(bucket->coef[i]),r);
1301  n_Delete(&coef,r );
1302  coef=temp;
1303  if (nIsPseudoUnit(coef,r))
1304  {
1305  n_Delete(&coef,r);
1306  return;
1307  }
1308  assume(!(n_IsZero(coef,r)));
1309  }
1310  }
1311  if (n_IsZero(coef,r))
1312  {
1313  n_Delete(&coef,r);
1314  return;
1315  }
1316  if (TEST_OPT_PROT)
1317  PrintS("S");
1318  for(i=0;i<=MAX_BUCKET;i++)
1319  {
1320  if (bucket->buckets[i]!=NULL)
1321  {
1322  assume(!(n_IsZero(coef,r)));
1323  assume(bucket->coef[i]!=NULL);
1324  number lc=p_GetCoeff(bucket->coef[i],r);
1325  p_SetCoeff(bucket->coef[i], n_ExactDiv(lc,coef,r),r);
1326  assume(!(n_IsZero(p_GetCoeff(bucket->coef[i],r),r)));
1327  }
1328  }
1329  n_Delete(&coef,r);
1330 }
1331 #endif
1332 
1333 
1335 {
1336  assume(bucket->buckets[i]!=NULL);
1337 
1338  poly p=bucket->buckets[i];
1339  bucket->buckets_length[i]--;
1340 #ifdef USE_COEF_BUCKETS
1341  ring r=bucket->bucket_ring;
1342  if (bucket->coef[i]!=NULL)
1343  {
1344  poly next=pNext(p);
1345  if (next==NULL)
1346  {
1347  MULTIPLY_BUCKET(bucket,i);
1348  p=bucket->buckets[i];
1349  bucket->buckets[i]=NULL;
1350  return p;
1351  }
1352  else
1353  {
1354  bucket->buckets[i]=next;
1355  number c=p_GetCoeff(bucket->coef[i],r);
1356  pNext(p)=NULL;
1357  p=__p_Mult_nn(p,c,r);
1358  assume(p!=NULL);
1359  return p;
1360  }
1361  }
1362  else
1363 #endif
1364  {
1365  bucket->buckets[i]=pNext(bucket->buckets[i]);
1366  pNext(p)=NULL;
1367  assume(p!=NULL);
1368  return p;
1369  }
1370 }
1371 
1372 /*
1373 * input - output: a, b
1374 * returns:
1375 * a := a/gcd(a,b), b := b/gcd(a,b)
1376 * and return value
1377 * 0 -> a != 1, b != 1
1378 * 1 -> a == 1, b != 1
1379 * 2 -> a != 1, b == 1
1380 * 3 -> a == 1, b == 1
1381 * this value is used to control the spolys
1382 */
1383 int ksCheckCoeff(number *a, number *b, const coeffs r)
1384 {
1385  int c = 0;
1386  number an = *a, bn = *b;
1387  n_Test(an,r);
1388  n_Test(bn,r);
1389 
1390  number cn = n_SubringGcd(an, bn, r);
1391 
1392  if(n_IsOne(cn, r))
1393  {
1394  an = n_Copy(an, r);
1395  bn = n_Copy(bn, r);
1396  }
1397  else
1398  {
1399  an = n_ExactDiv(an, cn, r); n_Normalize(an,r);
1400  bn = n_ExactDiv(bn, cn, r); n_Normalize(bn,r);
1401  }
1402  n_Delete(&cn, r);
1403  if (n_IsOne(an, r))
1404  {
1405  c = 1;
1406  }
1407  if (n_IsOne(bn, r))
1408  {
1409  c += 2;
1410  }
1411  *a = an;
1412  *b = bn;
1413  return c;
1414 }
1415 
kBucketSimpleContent
void kBucketSimpleContent(kBucket_pt bucket)
Definition: kbuckets.cc:1162
ksCheckCoeff
int ksCheckCoeff(number *a, number *b)
FALSE
#define FALSE
Definition: auxiliary.h:94
dReportError
int dReportError(const char *fmt,...)
Definition: dError.cc:45
kBucketSetLm
void kBucketSetLm(kBucket_pt bucket, poly lm)
omalloc.h
kBucketCanonicalize
int kBucketCanonicalize(kBucket_pt bucket)
p_GetCoeff
#define p_GetCoeff(p, r)
Definition: monomials.h:57
p_GetComp
#define p_GetComp(p, r)
Definition: monomials.h:71
j
int j
Definition: facHensel.cc:105
p_SetCoeff0
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:67
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:102
n_ExactDiv
static FORCE_INLINE number n_ExactDiv(number a, number b, const coeffs r)
assume that there is a canonical subring in cf and we know that division is possible for these a and ...
Definition: coeffs.h:623
rField_is_Domain
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:480
LOG4
static int LOG4(int v)
Some internal stuff.
Definition: kbuckets.cc:53
lq
Definition: lq.h:40
omGetSpecBin
#define omGetSpecBin(size)
Definition: omBin.h:11
kBucket_pt
kBucket * kBucket_pt
Definition: ring.h:31
kBucketPolyRed
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1061
SI_LOG2
static int SI_LOG2(int v)
Definition: auxiliary.h:119
p_SetCompP
static void p_SetCompP(poly p, int i, ring r)
Definition: p_polys.h:254
MAX_BUCKET
#define MAX_BUCKET
Bucket definition (should be no one elses business, though)
Definition: kbuckets.h:172
p_Plus_mm_Mult_qq
static poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq, const ring r)
Definition: p_polys.h:1129
cf
CanonicalForm cf
Definition: cfModGcd.cc:4024
p_Minus_mm_Mult_qq
static poly p_Minus_mm_Mult_qq(poly p, const poly m, const poly q, int &lp, int lq, const poly spNoether, const ring r)
Definition: p_polys.h:1006
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
kBucketExtractLmOfBucket
poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i)
Definition: kbuckets.cc:1334
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
p_InitContent
number p_InitContent(poly ph, const ring r)
Definition: p_polys.cc:2549
kBucket::l
int l
Definition: kbuckets.h:180
p_Test
#define p_Test(p, r)
Definition: p_polys.h:163
pLogLength
static unsigned int pLogLength(unsigned int l)
Definition: kbuckets.cc:68
options.h
pp_Mult_mm
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:987
auxiliary.h
omAlloc0Bin
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
kBucketGetLm
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:488
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:469
loop
#define loop
Definition: structs.h:78
b
CanonicalForm b
Definition: cfModGcd.cc:4044
__p_Mult_nn
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:927
n_Normalize
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition: coeffs.h:579
p_ExpVectorSub
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition: p_polys.h:1386
p_LmEqual
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1658
rIsPluralRing
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:404
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:192
next
ListNode * next
Definition: janet.h:31
kBucket_bin
static omBin kBucket_bin
Definition: kbuckets.cc:42
omCheckAddrBin
#define omCheckAddrBin(addr, bin)
Definition: omAllocDecl.h:325
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:493
TRUE
#define TRUE
Definition: auxiliary.h:98
i
int i
Definition: cfEzgcd.cc:125
kBucket_Add_q
void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
Add to Bucket a poly ,i.e. Bpoly == q+Bpoly.
Definition: kbuckets.cc:636
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:213
PrintS
void PrintS(const char *s)
Definition: reporter.cc:284
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:475
kbTest
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:194
kBucket_Minus_m_Mult_p
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition: kbuckets.cc:698
rField_is_Ring
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:477
kBucket_Mult_n
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition: kbuckets.cc:580
pFalseReturn
#define pFalseReturn(cond)
Definition: monomials.h:146
kBucketShallowCopyDelete
void kBucketShallowCopyDelete(kBucket_pt bucket, ring new_tailRing, omBin new_tailBin, pShallowCopyDeleteProc p_shallow_copy_delete)
For changing the ring of the Bpoly to new_tailBin.
Definition: kbuckets.cc:517
ndGcd
number ndGcd(number, number, const coeffs r)
Definition: numbers.cc:161
p_LmDelete
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:711
coeffs
kBucket_Plus_mm_Mult_pp
void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l)
Bpoly == Bpoly + m*p; where m is a monom Does not destroy p and m assume (l <= 0 || pLength(p) == l)
Definition: kbuckets.cc:803
pIter
#define pIter(p)
Definition: monomials.h:44
p_polys.h
n_Init
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
p_DivisibleBy
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1824
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1507
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition: facAlgFuncUtil.cc:32
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:503
n_InpNeg
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
kbuckets.h
ring.h
omBin
omBin_t * omBin
Definition: omStructs.h:12
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:857
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:892
kBucket::bucket_ring
ring bucket_ring
Definition: kbuckets.h:189
kBucket::p
poly p
Definition: kbuckets.h:179
p_NSet
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1435
kBucketDeleteAndDestroy
void kBucketDeleteAndDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:220
kBucketTakeOutComp
void kBucketTakeOutComp(kBucket_pt bucket, long comp, poly *r_p, int *l)
Definition: kbuckets.cc:1020
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:412
n_IsMOne
static FORCE_INLINE BOOLEAN n_IsMOne(number n, const coeffs r)
TRUE iff 'n' represents the additive inverse of the one element, i.e. -1.
Definition: coeffs.h:473
pSetCoeff0
#define pSetCoeff0(p, n)
Definition: monomials.h:66
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:452
n_Gcd
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:687
m
int m
Definition: cfEzgcd.cc:121
assume
#define assume(x)
Definition: mod2.h:390
NULL
#define NULL
Definition: omList.c:10
p_TakeOutComp
void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r)
Definition: p_polys.cc:3446
kBucketAdjust
void kBucketAdjust(kBucket_pt bucket, int i)
Bucket number i from bucket is out of length sync, resync.
Definition: kbuckets.cc:547
kBucketIsCleared
BOOLEAN kBucketIsCleared(kBucket_pt bucket)
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:247
l
int l
Definition: cfEzgcd.cc:93
n_SubringGcd
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:689
kBucket
Definition: kbuckets.h:176
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:233
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
MULTIPLY_BUCKET
#define MULTIPLY_BUCKET(B, I)
Definition: kbuckets.cc:40
p
int p
Definition: cfModGcd.cc:4019
kBucket_ExtractLarger
poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append)
Extract all monomials of bucket which are larger than q Append those to append, and return last monom...
Definition: kbuckets.cc:986
pShallowCopyDeleteProc
poly(* pShallowCopyDeleteProc)(poly s_p, ring source_r, ring dest_r, omBin dest_bin)
returns a poly from dest_r which is a ShallowCopy of s_p from source_r assumes that source_r->N == de...
Definition: ring.h:51
p_IsConstant
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1923
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:206
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition: facSparseHensel.h:25
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:51
rParameter
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:616
n_Size
static FORCE_INLINE int n_Size(number n, const coeffs r)
return a non-negative measure for the complexity of n; return 0 only when n represents zero; (used fo...
Definition: coeffs.h:571
n_Test
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:739
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
rField_is_Zp
static BOOLEAN rField_is_Zp(const ring r)
Definition: ring.h:495
numbers.h
pNext
#define pNext(p)
Definition: monomials.h:43
p_Mult_nn
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:914
coeffs.h