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