kbuckets.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 //#include <kernel/mod2.h>
5 
6 
7 
8 
9 #include <omalloc/omalloc.h>
10 #include <misc/auxiliary.h>
11 
13 //#include <kernel/pShallowCopyDelete.h>
14 #include <coeffs/coeffs.h>
15 #include <polys/monomials/ring.h>
16 //#include <kernel/GBEngine/kutil.h>
17 #include <polys/kbuckets.h>
18 
19 // #include <polys/operations/pShallowCopyDelete.h>
20 
21 
22 #ifdef HAVE_COEF_BUCKETS
23 #define USE_COEF_BUCKETS
24 #endif
25 
26 #ifdef USE_COEF_BUCKETS
27 #ifdef HAVE_RINGS_OLD
28 #define MULTIPLY_BUCKET(B,I) do \
29  { if (B->coef[I]!=NULL) \
30  { \
31  assume(p_IsConstant(B->Coef[i],B->bucket->ring)); \
32  B->buckets[I]=p_Mult_q(B->buckets[I],B->coef[I],B->bucket_ring); \
33  B->coef[I]=NULL; \
34  } \
35  } while(0) \
36  if (rField_is_Ring(B->bucket_ring)) B->buckets_length[i] = pLength(B->buckets[i]);
37 #else
38 #define MULTIPLY_BUCKET(B,I) do \
39  { if (B->coef[I]!=NULL) \
40  { \
41  B->buckets[I]=p_Mult_q(B->buckets[I],B->coef[I],B->bucket_ring); \
42  B->coef[I]=NULL; \
43  } \
44  } while(0)
45 #endif
46 #else
47 #define MULTIPLY_BUCKET(B,I)
48 #endif
50 #ifdef USE_COEF_BUCKETS
51 static int coef_start=1;
52 #endif
53 //////////////////////////////////////////////////////////////////////////
54 ///
55 /// Some internal stuff
56 ///
57 
58 // returns ceil(log_4(l))
59 inline unsigned int pLogLength(unsigned int l)
60 {
61  unsigned int i = 0;
62 
63  if (l == 0) return 0;
64  l--;
65 #ifdef BUCKET_TWO_BASE
66  while ((l = (l >> 1))) i++;
67 #else
68  while ((l = (l >> 2))) i++;
69 #endif
70  return i+1;
71 }
72 
73 // returns ceil(log_4(pLength(p)))
74 inline unsigned int pLogLength(poly p)
75 {
76  return pLogLength((unsigned int) pLength(p));
77 }
78 
79 #ifdef KDEBUG
80 
81 #ifndef HAVE_PSEUDO_BUCKETS
82 BOOLEAN kbTest_i(kBucket_pt bucket, int i)
83 {//sBucketSortMerge
84  #ifdef USE_COEF_BUCKETS
85  assume(bucket->coef[0]==NULL);
86  if ((bucket->coef[i]!=NULL) && (bucket->buckets[i]==NULL))
87  {
88  dReportError("Bucket %d coef not NULL", i);
89  }
90  if (bucket->coef[i]!=NULL)
91  {
92  assume(bucket->buckets[i]!=NULL);
93  p_Test(bucket->coef[i],bucket->bucket_ring);
94  }
95  #endif
96  pFalseReturn(p_Test(bucket->buckets[i], bucket->bucket_ring));
97  if (bucket->buckets_length[i] != pLength(bucket->buckets[i]))
98  {
99  dReportError("Bucket %d lengths difference should:%d has:%d",
100  i, bucket->buckets_length[i], pLength(bucket->buckets[i]));
101  }
102  else if (i > 0 && (int) pLogLength(bucket->buckets_length[i]) > i)
103  {
104  dReportError("Bucket %d too long %d",
105  i, bucket->buckets_length[i]);
106  }
107  if (i==0 && bucket->buckets_length[0] > 1)
108  {
109  dReportError("Bucket 0 too long");
110  }
111  return TRUE;
112 }
113 
114 
115 BOOLEAN kbTest(kBucket_pt bucket)
116 {
117  #ifdef HAVE_COEF_BUCKETS
118  assume(bucket->coef[0]==NULL);
119  #endif
120  int i;
121  poly lm = bucket->buckets[0];
122 
123  omCheckAddrBin(bucket, kBucket_bin);
124  assume(bucket->buckets_used <= MAX_BUCKET);
125  if (! kbTest_i(bucket, 0)) return FALSE;
126  for (i=1; i<= (int) bucket->buckets_used; i++)
127  {
128  if (!kbTest_i(bucket, i)) return FALSE;
129  if (lm != NULL && bucket->buckets[i] != NULL
130  && p_LmCmp(lm, bucket->buckets[i], bucket->bucket_ring) != 1)
131  {
132  dReportError("Bucket %d larger or equal than lm", i);
133  if (p_LmCmp(lm, bucket->buckets[i], bucket->bucket_ring) ==0)
134  dReportError("Bucket %d equal to lm", i);
135  return FALSE;
136  }
137  if (!p_Test(bucket->buckets[i],bucket->bucket_ring))
138  {
139  dReportError("Bucket %d is not =0(4)", i);
140  return FALSE;
141  }
142  }
143 
144  for (; i<=MAX_BUCKET; i++)
145  {
146  if (bucket->buckets[i] != NULL || bucket->buckets_length[i] != 0)
147  {
148  dReportError("Bucket %d not zero", i);
149  return FALSE;
150  }
151  }
152  for(i=0;i<=MAX_BUCKET;i++)
153  {
154  if (bucket->buckets[i]!=NULL)
155  {
156  int j;
157  for(j=i+1;j<=MAX_BUCKET;j++)
158  {
159  if (bucket->buckets[j]==bucket->buckets[i])
160  {
161  dReportError("Bucket %d %d equal", i,j);
162  return FALSE;
163  }
164  }
165  }
166  #ifdef HAVE_COEF_BUCKETS
167  if (bucket->coef[i]!=NULL)
168  {
169  int j;
170  for(j=i+1;j<=MAX_BUCKET;j++)
171  {
172  if (bucket->coef[j]==bucket->coef[i])
173  {
174  dReportError("internal coef %d %d equal", i,j);
175  return FALSE;
176  }
177  }
178  }
179  #endif
180  }
181  return TRUE;
182 }
183 
184 #else // HAVE_PSEUDO_BUCKETS
186 {
187  return TRUE;
188 }
189 #endif // ! HAVE_PSEUDO_BUCKETS
190 #endif // KDEBUG
191 
192 //////////////////////////////////////////////////////////////////////////
193 ///
194 /// Creation/Destruction of buckets
195 ///
196 
197 kBucket_pt kBucketCreate(ring bucket_ring)
198 {
199  assume(bucket_ring != NULL);
201  bucket->bucket_ring = bucket_ring;
202  return bucket;
203 }
204 void kBucketDestroy(kBucket_pt *bucket_pt)
205 {
206  omFreeBin(*bucket_pt, kBucket_bin);
207  *bucket_pt = NULL;
208 }
209 
210 
212 {
213  kBucket_pt bucket = *bucket_pt;
214  kbTest(bucket);
215  int i;
216  for (i=0; i<= bucket->buckets_used; i++)
217  {
218 
219  if (bucket->buckets[i] != NULL)
220  {
221  p_Delete(&(bucket->buckets[i]), bucket->bucket_ring);
222 #ifdef USE_COEF_BUCKETS
223  if (bucket->coef[i]!=NULL)
224  p_Delete(&(bucket->coef[i]), bucket->bucket_ring);
225 #endif
226  }
227  }
228  omFreeBin(bucket, kBucket_bin);
229  *bucket_pt = NULL;
230 }
231 
232 /////////////////////////////////////////////////////////////////////////////
233 // Convertion from/to Bpolys
234 //
235 #ifndef HAVE_PSEUDO_BUCKETS
236 
237 inline void kBucketMergeLm(kBucket_pt bucket)
238 {
239  kbTest(bucket);
240  if (bucket->buckets[0] != NULL)
241  {
242  poly lm = bucket->buckets[0];
243  int i = 1;
244 #ifdef BUCKET_TWO_BASE
245  int l = 2;
246  while ( bucket->buckets_length[i] >= l)
247  {
248  i++;
249  l = l << 1;
250  }
251 #else
252  int l = 4;
253  while ( bucket->buckets_length[i] >= l)
254  {
255  i++;
256  l = l << 2;
257  }
258 #endif
259 #ifndef USE_COEF_BUCKETS
260  MULTIPLY_BUCKET(bucket,i);
261  pNext(lm) = bucket->buckets[i];
262  bucket->buckets[i] = lm;
263  bucket->buckets_length[i]++;
264  assume(i <= bucket->buckets_used+1);
265  if (i > bucket->buckets_used) bucket->buckets_used = i;
266  bucket->buckets[0] = NULL;
267  bucket->buckets_length[0] = 0;
268  kbTest(bucket);
269 #else
270  if (i > bucket->buckets_used) bucket->buckets_used = i;
271  assume(i!=0);
272  if (bucket->buckets[i]!=NULL)
273  {
274  MULTIPLY_BUCKET(bucket,i);
275  pNext(lm) = bucket->buckets[i];
276  bucket->buckets[i] = lm;
277  bucket->buckets_length[i]++;
278  assume(i <= bucket->buckets_used+1);
279  }
280  else
281  {
282  #if 1
283  assume(bucket->buckets[i]==NULL);
284  assume(bucket->coef[0]==NULL);
285  assume(pLength(lm)==1);
286  assume(pNext(lm)==NULL);
287  number coef=p_GetCoeff(lm,bucket->bucket_ring);
288  //WARNING: not thread_safe
289  p_SetCoeff0(lm, n_Init(1,bucket->bucket_ring), bucket->bucket_ring);
290  bucket->buckets[i]=lm;
291  bucket->buckets_length[i]=1;
292  bucket->coef[i]=p_NSet(n_Copy(coef,bucket->bucket_ring),bucket->bucket_ring);
293 
294  bucket->buckets[i]=lm;
295  bucket->buckets_length[i]=1;
296  #else
297  MULTIPLY_BUCKET(bucket,i);
298  pNext(lm) = bucket->buckets[i];
299  bucket->buckets[i] = lm;
300  bucket->buckets_length[i]++;
301  assume(i <= bucket->buckets_used+1);
302  #endif
303  }
304  bucket->buckets[0]=NULL;
305  bucket->buckets_length[0] = 0;
306  bucket->coef[0]=NULL;
307  kbTest(bucket);
308  #endif
309  }
310 
311 }
312 
314 {
315  int i;
316 
317  for (i = 0;i<=MAX_BUCKET;i++)
318  {
319  if (bucket->buckets[i] != NULL) return FALSE;
320  #ifdef HAVE_COEF_BUCKETS
321  if (bucket->coef[i] != NULL) return FALSE;
322  #endif
323  if (bucket->buckets_length[i] != 0) return FALSE;
324  }
325  return TRUE;
326 }
327 
328 void kBucketInit(kBucket_pt bucket, poly lm, int length)
329 {
330  //assume(false);
331  assume(bucket != NULL);
332  assume(length <= 0 || length == pLength(lm));
333  assume(kBucketIsCleared(bucket));
334 
335  if (lm == NULL) return;
336 
337  if (length <= 0)
338  length = pLength(lm);
339 
340  bucket->buckets[0] = lm;
341  #ifdef HAVE_COEF_BUCKETS
342  assume(bucket->coef[0]==NULL);
343  #endif
344  #ifdef USE_COEF_BUCKETS
345  bucket->coef[0]=NULL;
346  #endif
347  if (lm!=NULL)
348  bucket->buckets_length[0] = 1;
349  else
350  bucket->buckets_length[0]= 0;
351  if (length > 1)
352  {
353  unsigned int i = pLogLength(length-1);
354  bucket->buckets[i] = pNext(lm);
355  pNext(lm) = NULL;
356  bucket->buckets_length[i] = length-1;
357  bucket->buckets_used = i;
358  }
359  else
360  {
361  bucket->buckets_used = 0;
362  }
363 }
364 
366 {
367  assume(bucket->buckets_used<=MAX_BUCKET);
368  MULTIPLY_BUCKET(bucket,1);
369  kbTest(bucket);
370  poly p = bucket->buckets[1];
371  poly lm;
372  int pl = bucket->buckets_length[1];//, i;
373  int i;
374  bucket->buckets[1] = NULL;
375  bucket->buckets_length[1] = 0;
376  #ifdef USE_COEF_BUCKETS
377  assume(bucket->coef[1]==NULL);
378  #endif
379  ring r=bucket->bucket_ring;
380 
381 
382  for (i=1; i<=bucket->buckets_used; i++)
383  {
384  #ifdef USE_COEF_BUCKETS
385  if (bucket->coef[i]!=NULL)
386  {
387  assume(bucket->buckets[i]!=NULL);
388  p = p_Plus_mm_Mult_qq(p, bucket->coef[i], bucket->buckets[i],
389  pl, bucket->buckets_length[i], r);
390  p_Delete(&bucket->coef[i],r);
391  p_Delete(&bucket->buckets[i],r);
392  }
393  else
394  p = p_Add_q(p, bucket->buckets[i],
395  pl, bucket->buckets_length[i], r);
396  #else
397  p = p_Add_q(p, bucket->buckets[i],
398  pl, bucket->buckets_length[i], r);
399  #endif
400  if (i==1) continue;
401  bucket->buckets[i] = NULL;
402  bucket->buckets_length[i] = 0;
403  }
404  #ifdef HAVE_COEF_BUCKETS
405  assume(bucket->coef[0]==NULL);
406  #endif
407  lm = bucket->buckets[0];
408  if (lm != NULL)
409  {
410  pNext(lm) = p;
411  p = lm;
412  pl++;
413  bucket->buckets[0] = NULL;
414  bucket->buckets_length[0] = 0;
415  }
416  if (pl > 0)
417  {
418  i = pLogLength(pl);
419  bucket->buckets[i] = p;
420  bucket->buckets_length[i] = pl;
421  }
422  else
423  {
424  i = 0;
425  }
426  bucket->buckets_used = i;
427  assume(bucket->buckets_used <= MAX_BUCKET);
428  #ifdef USE_COEF_BUCKETS
429  assume(bucket->coef[0]==NULL);
430  assume(bucket->coef[i]==NULL);
431  #endif
432  assume(pLength(p) == (int) pl);
433  //if (TEST_OPT_PROT) { Print("C(%d)",pl); }
434  kbTest(bucket);
435  return i;
436 }
437 
438 void kBucketClear(kBucket_pt bucket, poly *p, int *length)
439 {
440  int i = kBucketCanonicalize(bucket);
441  if (i > 0)
442  {
443  #ifdef USE_COEF_BUCKETS
444  MULTIPLY_BUCKET(bucket,i);
445  //bucket->coef[i]=NULL;
446  #endif
447  *p = bucket->buckets[i];
448  *length = bucket->buckets_length[i];
449  bucket->buckets[i] = NULL;
450  bucket->buckets_length[i] = 0;
451  bucket->buckets_used = 0;
452 
453  }
454  else
455  {
456  *p = NULL;
457  *length = 0;
458  }
459 }
460 
461 void kBucketSetLm(kBucket_pt bucket, poly lm)
462 {
463  kBucketMergeLm(bucket);
464  pNext(lm) = NULL;
465  bucket->buckets[0] = lm;
466  bucket->buckets_length[0] = 1;
467 }
468 
469 #else // HAVE_PSEUDO_BUCKETS
470 
471 void kBucketInit(kBucket_pt bucket, poly lm, int length)
472 {
473  int i;
474 
475  assume(bucket != NULL);
476  assume(length <= 0 || length == pLength(lm));
477 
478  bucket->p = lm;
479  if (length <= 0) bucket->l = pLength(lm);
480  else bucket->l = length;
481 
482 }
483 
485 {
486  return bucket->p;
487 }
488 
490 {
491  poly lm = bucket->p;
492  assume(pLength(bucket->p) == bucket->l);
493  pIter(bucket->p);
494  (bucket->l)--;
495  pNext(lm) = NULL;
496  return lm;
497 }
498 
499 void kBucketClear(kBucket_pt bucket, poly *p, int *length)
500 {
501  assume(pLength(bucket->p) == bucket->l);
502  *p = bucket->p;
503  *length = bucket->l;
504  bucket->p = NULL;
505  bucket->l = 0;
506 }
507 
508 #endif // ! HAVE_PSEUDO_BUCKETS
509 //////////////////////////////////////////////////////////////////////////
510 ///
511 /// For changing the ring of the Bpoly to new_tailBin
512 ///
514  ring new_tailRing, omBin new_tailBin,
515  pShallowCopyDeleteProc p_shallow_copy_delete)
516 {
517 #ifndef HAVE_PSEUDO_BUCKETS
518  int i;
519 
520  kBucketCanonicalize(bucket);
521  for (i=0; i<= bucket->buckets_used; i++)
522  if (bucket->buckets[i] != NULL)
523  {
524  MULTIPLY_BUCKET(bucket,i);
525  bucket->buckets[i] = p_shallow_copy_delete(bucket->buckets[i],
526  bucket->bucket_ring,
527  new_tailRing,
528  new_tailBin);
529  }
530 #else
531  bucket->p = p_shallow_copy_delete(p,
532  bucket_ring,
533  new_tailRing,
534  new_tailBin);
535 #endif
536  bucket->bucket_ring = new_tailRing;
537 }
538 
539 //////////////////////////////////////////////////////////////////////////
540 ///
541 /// Bucket number i from bucket is out of length sync, resync
542 ///
543 void kBucketAdjust(kBucket_pt bucket, int i) {
544 
545  MULTIPLY_BUCKET(bucket,i);
546 
547  int l1 = bucket->buckets_length[i];
548  poly p1 = bucket->buckets[i];
549  bucket->buckets[i] = NULL;
550  bucket->buckets_length[i] = 0;
551  i = pLogLength(l1);
552 
553  while (bucket->buckets[i] != NULL)
554  {
555  //kbTest(bucket);
556  MULTIPLY_BUCKET(bucket,i);
557  p1 = p_Add_q(p1, bucket->buckets[i],
558  l1, bucket->buckets_length[i], bucket->bucket_ring);
559  bucket->buckets[i] = NULL;
560  bucket->buckets_length[i] = 0;
561  i = pLogLength(l1);
562  }
563 
564  bucket->buckets[i] = p1;
565  bucket->buckets_length[i]=l1;
566  if (i >= bucket->buckets_used)
567  bucket->buckets_used = i;
568  else
569  kBucketAdjustBucketsUsed(bucket);
570 }
571 
572 //////////////////////////////////////////////////////////////////////////
573 ///
574 /// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
575 ///
576 void kBucket_Mult_n(kBucket_pt bucket, number n)
577 {
578 #ifndef HAVE_PSEUDO_BUCKETS
579  kbTest(bucket);
580  ring r=bucket->bucket_ring;
581  int i;
582 
583  for (i=0; i<= bucket->buckets_used; i++)
584  {
585  if (bucket->buckets[i] != NULL)
586  {
587 #ifdef USE_COEF_BUCKETS
588  if (i<coef_start)
589  bucket->buckets[i] = p_Mult_nn(bucket->buckets[i], n, r);
590 #ifdef HAVE_RINGS
591  /* Frank Seelisch on March 11, 2010:
592  This looks a bit strange: The following "if" is indented
593  like the previous line of code. But coded as it is,
594  it should actually be two spaces less indented.
595  Question: Should the following "if" also only be
596  performed when "(i<coef_start)" is true?
597  For the time being, I leave it as it is. */
598  if (rField_is_Ring(r) && !(rField_is_Domain(r)))
599  {
600  bucket->buckets_length[i] = pLength(bucket->buckets[i]);
601  kBucketAdjust(bucket, i);
602  }
603 #endif
604  else
605  if (bucket->coef[i]!=NULL)
606  {
607  bucket->coef[i] = p_Mult_nn(bucket->coef[i],n,r);
608  }
609  else
610  {
611  bucket->coef[i] = p_NSet(n_Copy(n,r),r);
612  }
613 #else
614  bucket->buckets[i] = p_Mult_nn(bucket->buckets[i], n, r);
615 #ifdef HAVE_RINGS
616  if (rField_is_Ring(r) && !(rField_is_Domain(r)))
617  {
618  bucket->buckets_length[i] = pLength(bucket->buckets[i]);
619  kBucketAdjust(bucket, i);
620  }
621 #endif
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_RINGS)||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])==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)
804 {
805  assume((!rIsPluralRing(bucket->bucket_ring))||p_IsConstant(m, bucket->bucket_ring));
806  assume(l <= 0 || pLength(p) == 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) && (bucket->coef[i]!=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 
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) == lq);
1038  bucket->buckets_length[i] -= lq;
1039  assume(pLength(bucket->buckets[i]) == 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) == (int) 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(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 #else
1164 static BOOLEAN nIsPseudoUnit(number n, ring r)
1165 {
1166  if (rField_is_Zp(r))
1167  return TRUE;
1168 
1169  if (rParameter(r)==NULL)
1170  {
1171  return (n_Size(n,r->cf)==1);
1172  }
1173  //if (r->parameter!=NULL)
1174  return (n_IsOne(n,r->cf) || n_IsMOne(n,r->cf));
1175 }
1176 
1177 void kBucketSimpleContent(kBucket_pt bucket)
1178 {
1179  ring r=bucket->bucket_ring;
1180  int i;
1181  //PrintS("HHHHHHHHHHHHH");
1182  for (i=0;i<=MAX_BUCKET;i++)
1183  {
1184  //if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]!=NULL))
1185  // PrintS("H2H2H2");
1186  if (i==0)
1187  {
1188  assume(bucket->buckets[i]==NULL);
1189  }
1190  if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]==NULL))
1191  return;
1192  }
1193  for (i=0;i<=MAX_BUCKET;i++)
1194  {
1195  //if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]!=NULL))
1196  // PrintS("H2H2H2");
1197  if (i==0)
1198  {
1199  assume(bucket->buckets[i]==NULL);
1200  }
1201  if ((bucket->buckets[i]!=NULL)
1202  && (nIsPseudoUnit(p_GetCoeff(bucket->coef[i],r),r)))
1203  return;
1204  }
1205  //return;
1206 
1207  number coef=n_Init(0,r);
1208  //ATTENTION: will not work correct for GB over ring
1209  //if (TEST_OPT_PROT)
1210  // PrintS("CCCCCCCCCCCCC");
1211  for (i=MAX_BUCKET;i>=0;i--)
1212  {
1213  if (i==0)
1214  {
1215  assume(bucket->buckets[i]==NULL);
1216  }
1217  if (bucket->buckets[i]!=NULL)
1218  {
1219  assume(bucket->coef[i]!=NULL);
1220  assume(!(n_IsZero(pGetCoeff(bucket->coef[i]),r)));
1221 
1222  //in this way it should crash on programming errors, yeah
1223  number temp=n_Gcd(coef, pGetCoeff(bucket->coef[i]),r);
1224  n_Delete(&coef,r );
1225  coef=temp;
1226  if (nIsPseudoUnit(coef,r))
1227  {
1228  n_Delete(&coef,r);
1229  return;
1230  }
1231  assume(!(n_IsZero(coef,r)));
1232  }
1233  }
1234  if (n_IsZero(coef,r))
1235  {
1236  n_Delete(&coef,r);
1237  return;
1238  }
1239  if (TEST_OPT_PROT)
1240  PrintS("S");
1241  for(i=0;i<=MAX_BUCKET;i++)
1242  {
1243  if (bucket->buckets[i]!=NULL)
1244  {
1245  assume(!(n_IsZero(coef,r)));
1246  assume(bucket->coef[i]!=NULL);
1247  number lc=p_GetCoeff(bucket->coef[i],r);
1248  p_SetCoeff(bucket->coef[i], n_ExactDiv(lc,coef,r),r);
1249  assume(!(n_IsZero(p_GetCoeff(bucket->coef[i],r),r)));
1250  }
1251  }
1252  n_Delete(&coef,r);
1253 }
1254 #endif
1255 
1256 
1258 {
1259  assume(bucket->buckets[i]!=NULL);
1260 
1261  poly p=bucket->buckets[i];
1262  bucket->buckets_length[i]--;
1263 #ifdef USE_COEF_BUCKETS
1264  ring r=bucket->bucket_ring;
1265  if (bucket->coef[i]!=NULL)
1266  {
1267  poly next=pNext(p);
1268  if (next==NULL)
1269  {
1270  MULTIPLY_BUCKET(bucket,i);
1271  p=bucket->buckets[i];
1272  bucket->buckets[i]=NULL;
1273  return p;
1274  }
1275  else
1276  {
1277  bucket->buckets[i]=next;
1278  number c=p_GetCoeff(bucket->coef[i],r);
1279  pNext(p)=NULL;
1280  p=p_Mult_nn(p,c,r);
1281  assume(p!=NULL);
1282  return p;
1283  }
1284  }
1285  else
1286 #endif
1287  {
1288  bucket->buckets[i]=pNext(bucket->buckets[i]);
1289  pNext(p)=NULL;
1290  assume(p!=NULL);
1291  return p;
1292  }
1293 }
1294 
1295 /*
1296 * input - output: a, b
1297 * returns:
1298 * a := a/gcd(a,b), b := b/gcd(a,b)
1299 * and return value
1300 * 0 -> a != 1, b != 1
1301 * 1 -> a == 1, b != 1
1302 * 2 -> a != 1, b == 1
1303 * 3 -> a == 1, b == 1
1304 * this value is used to control the spolys
1305 */
1306 int ksCheckCoeff(number *a, number *b, const coeffs r)
1307 {
1308  int c = 0;
1309  number an = *a, bn = *b;
1310  n_Test(an,r);
1311  n_Test(bn,r);
1312 
1313  number cn = n_SubringGcd(an, bn, r);
1314 
1315  if(n_IsOne(cn, r))
1316  {
1317  an = n_Copy(an, r);
1318  bn = n_Copy(bn, r);
1319  }
1320  else
1321  {
1322  an = n_Div(an, cn, r); n_Normalize(an,r);
1323  bn = n_Div(bn, cn, r); n_Normalize(bn,r);
1324  }
1325  n_Delete(&cn, r);
1326  if (n_IsOne(an, r))
1327  {
1328  c = 1;
1329  }
1330  if (n_IsOne(bn, r))
1331  {
1332  c += 2;
1333  }
1334  *a = an;
1335  *b = bn;
1336  return c;
1337 }
1338 
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:499
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:185
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
poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i)
Definition: kbuckets.cc:1257
#define MULTIPLY_BUCKET(B, I)
Definition: kbuckets.cc:47
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:513
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:471
const poly a
Definition: syzextra.cc:212
omBin_t * omBin
Definition: omStructs.h:12
static omBin kBucket_bin
Definition: kbuckets.cc:49
#define TEST_OPT_PROT
Definition: options.h:98
loop
Definition: myNF.cc:98
#define FALSE
Definition: auxiliary.h:140
return P p
Definition: myNF.cc:203
void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r)
Definition: p_polys.cc:3378
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1061
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
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:236
kBucket * kBucket_pt
Definition: kbuckets.h:15
#define p_GetComp(p, r)
Definition: monomials.h:72
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
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:484
int ksCheckCoeff(number *a, number *b)
#define MAX_BUCKET
Bucket definition (should be no one elses business, though)
Definition: kbuckets.h:174
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:962
#define TRUE
Definition: auxiliary.h:144
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:440
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition: coeffs.h:579
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
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
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition: kbuckets.cc:576
static bool rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:361
kBucket_pt kBucketCreate(ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:197
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:401
static int pLength(poly a)
Definition: p_polys.h:189
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:489
CanonicalForm lc(const CanonicalForm &f)
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
#define pIter(p)
Definition: monomials.h:44
#define pFalseReturn(cond)
Definition: monomials.h:147
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
const ring r
Definition: syzextra.cc:208
Coefficient rings, fields and other domains suitable for Singular polynomials.
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:204
static void p_SetCompP(poly p, int i, ring r)
Definition: p_polys.h:243
int j
Definition: myNF.cc:70
ring bucket_ring
Definition: kbuckets.h:191
#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.
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:923
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1685
void kBucketSetLm(kBucket_pt bucket, poly lm)
P bucket
Definition: myNF.cc:79
All the auxiliary stuff.
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1472
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
void kBucketSimpleContent(kBucket_pt)
Definition: kbuckets.cc:1162
#define omCheckAddrBin(addr, bin)
Definition: omAllocDecl.h:325
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition: p_polys.h:1368
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:902
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
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
void kBucketAdjust(kBucket_pt bucket, int i)
Bucket number i from bucket is out of length sync, resync.
Definition: kbuckets.cc:543
#define p_Test(p, r)
Definition: p_polys.h:160
static BOOLEAN rField_is_Zp(const ring r)
Definition: ring.h:455
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
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1519
unsigned int pLogLength(unsigned int l)
Some internal stuff.
Definition: kbuckets.cc:59
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:52
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:437
#define NULL
Definition: omList.c:10
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:452
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
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
int gcd(int a, int b)
Definition: walkSupport.cc:839
int l
Definition: kbuckets.h:182
#define pNext(p)
Definition: monomials.h:43
poly p
Definition: kbuckets.h:181
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:622
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:436
#define pSetCoeff0(p, n)
Definition: monomials.h:67
#define p_GetCoeff(p, r)
Definition: monomials.h:57
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:981
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:687
int dReportError(const char *fmt,...)
Definition: dError.cc:45
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:707
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:68
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
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
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:884
BOOLEAN kBucketIsCleared(kBucket_pt bucket)
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
int BOOLEAN
Definition: auxiliary.h:131
int kBucketCanonicalize(kBucket_pt bucket)
const poly b
Definition: syzextra.cc:213
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
void kBucketDeleteAndDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:211
void kBucketTakeOutComp(kBucket_pt bucket, long comp, poly *r_p, int *l)
Definition: kbuckets.cc:1020
int l
Definition: cfEzgcd.cc:94
static poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq, const ring r)
Definition: p_polys.h:1111
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
ListNode * next
Definition: janet.h:31