My Project  UNKNOWN_GIT_VERSION
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
42 static omBin kBucket_bin = omGetSpecBin(sizeof(kBucket));
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
194 BOOLEAN kbTest(kBucket_pt bucket)
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 
220 void kBucketDeleteAndDestroy(kBucket_pt *bucket_pt)
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 #ifndef HAVE_PSEUDO_BUCKETS
372  assume(bucket->buckets_used<=MAX_BUCKET);
373  MULTIPLY_BUCKET(bucket,1);
374  kbTest(bucket);
375  poly p = bucket->buckets[1];
376  poly lm;
377  int pl = bucket->buckets_length[1];//, i;
378  int i;
379  bucket->buckets[1] = NULL;
380  bucket->buckets_length[1] = 0;
381  #ifdef USE_COEF_BUCKETS
382  assume(bucket->coef[1]==NULL);
383  #endif
384  ring r=bucket->bucket_ring;
385 
386 
387  for (i=1; i<=bucket->buckets_used; i++)
388  {
389  #ifdef USE_COEF_BUCKETS
390  if (bucket->coef[i]!=NULL)
391  {
392  assume(bucket->buckets[i]!=NULL);
393  p = p_Plus_mm_Mult_qq(p, bucket->coef[i], bucket->buckets[i],
394  pl, bucket->buckets_length[i], r);
395  p_Delete(&bucket->coef[i],r);
396  p_Delete(&bucket->buckets[i],r);
397  }
398  else
399  p = p_Add_q(p, bucket->buckets[i],
400  pl, bucket->buckets_length[i], r);
401  #else
402  p = p_Add_q(p, bucket->buckets[i],
403  pl, bucket->buckets_length[i], r);
404  #endif
405  if (i==1) continue;
406  bucket->buckets[i] = NULL;
407  bucket->buckets_length[i] = 0;
408  }
409  #ifdef HAVE_COEF_BUCKETS
410  assume(bucket->coef[0]==NULL);
411  #endif
412  lm = bucket->buckets[0];
413  if (lm != NULL)
414  {
415  pNext(lm) = p;
416  p = lm;
417  pl++;
418  bucket->buckets[0] = NULL;
419  bucket->buckets_length[0] = 0;
420  }
421  if (pl > 0)
422  {
423  i = pLogLength(pl);
424  bucket->buckets[i] = p;
425  bucket->buckets_length[i] = pl;
426  }
427  else
428  {
429  i = 0;
430  }
431  bucket->buckets_used = i;
432  assume(bucket->buckets_used <= MAX_BUCKET);
433  #ifdef USE_COEF_BUCKETS
434  assume(bucket->coef[0]==NULL);
435  assume(bucket->coef[i]==NULL);
436  #endif
437  assume(pLength(p) == (unsigned)pl);
438  //if (TEST_OPT_PROT) { Print("C(%d)",pl); }
439  kbTest(bucket);
440  return i;
441 #endif
442 }
443 
444 void kBucketNormalize(kBucket_pt bucket)
445 {
446 #ifdef HAVE_PSEUDO_BUCKETS
447  p_Normalize(bucket->p,bucket->bucket_ring);
448 #else
449  MULTIPLY_BUCKET(bucket,1);
450  for (int i=0; i<=bucket->buckets_used; i++)
451  {
452  p_Normalize(bucket->buckets[i],bucket->bucket_ring);
453  }
454 #endif
455 }
456 
457 void kBucketClear(kBucket_pt bucket, poly *p, int *length)
458 {
459  int i = kBucketCanonicalize(bucket);
460  if (i > 0)
461  {
462  #ifdef USE_COEF_BUCKETS
463  MULTIPLY_BUCKET(bucket,i);
464  //bucket->coef[i]=NULL;
465  #endif
466  *p = bucket->buckets[i];
467  *length = bucket->buckets_length[i];
468  bucket->buckets[i] = NULL;
469  bucket->buckets_length[i] = 0;
470  bucket->buckets_used = 0;
471 
472  }
473  else
474  {
475  *p = NULL;
476  *length = 0;
477  }
478 }
479 
480 void kBucketSetLm(kBucket_pt bucket, poly lm)
481 {
482  kBucketMergeLm(bucket);
483  pNext(lm) = NULL;
484  bucket->buckets[0] = lm;
485  bucket->buckets_length[0] = 1;
486 }
487 
488 #else // HAVE_PSEUDO_BUCKETS
489 
490 void kBucketInit(kBucket_pt bucket, poly lm, int length)
491 {
492  int i;
493 
494  assume(bucket != NULL);
495  assume(length <= 0 || length == pLength(lm));
496 
497  bucket->p = lm;
498  if (length <= 0) bucket->l = pLength(lm);
499  else bucket->l = length;
500 
501 }
502 
503 const poly kBucketGetLm(kBucket_pt bucket)
504 {
505  return bucket->p;
506 }
507 
508 poly kBucketExtractLm(kBucket_pt bucket)
509 {
510  poly lm = bucket->p;
511  assume(pLength(bucket->p) == bucket->l);
512  pIter(bucket->p);
513  (bucket->l)--;
514  pNext(lm) = NULL;
515  return lm;
516 }
517 
518 void kBucketClear(kBucket_pt bucket, poly *p, int *length)
519 {
520  assume(pLength(bucket->p) == bucket->l);
521  *p = bucket->p;
522  *length = bucket->l;
523  bucket->p = NULL;
524  bucket->l = 0;
525 }
526 
527 #endif // ! HAVE_PSEUDO_BUCKETS
528 //////////////////////////////////////////////////////////////////////////
529 ///
530 /// For changing the ring of the Bpoly to new_tailBin
531 ///
533  ring new_tailRing, omBin new_tailBin,
534  pShallowCopyDeleteProc p_shallow_copy_delete)
535 {
536 #ifndef HAVE_PSEUDO_BUCKETS
537  int i;
538 
539  kBucketCanonicalize(bucket);
540  for (i=0; i<= bucket->buckets_used; i++)
541  if (bucket->buckets[i] != NULL)
542  {
543  MULTIPLY_BUCKET(bucket,i);
544  bucket->buckets[i] = p_shallow_copy_delete(bucket->buckets[i],
545  bucket->bucket_ring,
546  new_tailRing,
547  new_tailBin);
548  }
549 #else
550  bucket->p = p_shallow_copy_delete(p,
551  bucket_ring,
552  new_tailRing,
553  new_tailBin);
554 #endif
555  bucket->bucket_ring = new_tailRing;
556 }
557 
558 //////////////////////////////////////////////////////////////////////////
559 ///
560 /// Bucket number i from bucket is out of length sync, resync
561 ///
562 void kBucketAdjust(kBucket_pt bucket, int i) {
563 
564  MULTIPLY_BUCKET(bucket,i);
565 
566  int l1 = bucket->buckets_length[i];
567  poly p1 = bucket->buckets[i];
568  bucket->buckets[i] = NULL;
569  bucket->buckets_length[i] = 0;
570  i = pLogLength(l1);
571 
572  while (bucket->buckets[i] != NULL)
573  {
574  //kbTest(bucket);
575  MULTIPLY_BUCKET(bucket,i);
576  p1 = p_Add_q(p1, bucket->buckets[i],
577  l1, bucket->buckets_length[i], bucket->bucket_ring);
578  bucket->buckets[i] = NULL;
579  bucket->buckets_length[i] = 0;
580  i = pLogLength(l1);
581  }
582 
583  bucket->buckets[i] = p1;
584  bucket->buckets_length[i]=l1;
585  if (i >= bucket->buckets_used)
586  bucket->buckets_used = i;
587  else
588  kBucketAdjustBucketsUsed(bucket);
589 }
590 
591 //////////////////////////////////////////////////////////////////////////
592 ///
593 /// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
594 ///
595 void kBucket_Mult_n(kBucket_pt bucket, number n)
596 {
597 #ifndef HAVE_PSEUDO_BUCKETS
598  kbTest(bucket);
599  ring r=bucket->bucket_ring;
600  int i;
601 
602  for (i=0; i<= bucket->buckets_used; i++)
603  {
604  if (bucket->buckets[i] != NULL)
605  {
606 #ifdef USE_COEF_BUCKETS
607  if (i<coef_start)
608  bucket->buckets[i] = __p_Mult_nn(bucket->buckets[i], n, r);
609  /* Frank Seelisch on March 11, 2010:
610  This looks a bit strange: The following "if" is indented
611  like the previous line of code. But coded as it is,
612  it should actually be two spaces less indented.
613  Question: Should the following "if" also only be
614  performed when "(i<coef_start)" is true?
615  For the time being, I leave it as it is. */
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  else
622  if (bucket->coef[i]!=NULL)
623  {
624  bucket->coef[i] = __p_Mult_nn(bucket->coef[i],n,r);
625  }
626  else
627  {
628  bucket->coef[i] = p_NSet(n_Copy(n,r),r);
629  }
630 #else
631  bucket->buckets[i] = __p_Mult_nn(bucket->buckets[i], n, r);
632  if (rField_is_Ring(r) && !(rField_is_Domain(r)))
633  {
634  bucket->buckets_length[i] = pLength(bucket->buckets[i]);
635  kBucketAdjust(bucket, i);
636  }
637 #endif
638  }
639  }
640  kbTest(bucket);
641 #else
642  bucket->p = __p_Mult_nn(bucket->p, n, bucket->bucket_ring);
643 #endif
644 }
645 
646 
647 //////////////////////////////////////////////////////////////////////////
648 ///
649 /// Add to Bucket a poly ,i.e. Bpoly == q+Bpoly
650 ///
651 void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
652 {
653  if (q == NULL) return;
654  assume(*l <= 0 || pLength(q) == *l);
655 
656  int i, l1;
657  ring r = bucket->bucket_ring;
658 
659  if (*l <= 0)
660  {
661  l1 = pLength(q);
662  *l = l1;
663  }
664  else
665  l1 = *l;
666 
667  kBucketMergeLm(bucket);
668  kbTest(bucket);
669  i = pLogLength(l1);
670 
671  while (bucket->buckets[i] != NULL)
672  {
673  //MULTIPLY_BUCKET(bucket,i);
674  #ifdef USE_COEF_BUCKETS
675  if (bucket->coef[i]!=NULL)
676  {
677  q = p_Plus_mm_Mult_qq(q, bucket->coef[i], bucket->buckets[i],
678  l1, bucket->buckets_length[i], r);
679  p_Delete(&bucket->coef[i],r);
680  p_Delete(&bucket->buckets[i],r);
681  }
682  else
683  q = p_Add_q(q, bucket->buckets[i],
684  l1, bucket->buckets_length[i], r);
685  #else
686  q = p_Add_q(q, bucket->buckets[i],
687  l1, bucket->buckets_length[i], r);
688  #endif
689  bucket->buckets[i] = NULL;
690  bucket->buckets_length[i] = 0;
691  i = pLogLength(l1);
692  assume(i<= MAX_BUCKET);
693  assume(bucket->buckets_used<= MAX_BUCKET);
694  }
695 
696  kbTest(bucket);
697  bucket->buckets[i] = q;
698  bucket->buckets_length[i]=l1;
699  if (i >= bucket->buckets_used)
700  bucket->buckets_used = i;
701  else
702  kBucketAdjustBucketsUsed(bucket);
703  kbTest(bucket);
704 }
705 
706 
707 
708 //////////////////////////////////////////////////////////////////////////
709 ///
710 /// Bpoly == Bpoly - m*p; where m is a monom
711 /// Does not destroy p and m
712 /// assume (*l <= 0 || pLength(p) == *l)
713 void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l,
714  poly spNoether)
715 {
716  assume(*l <= 0 || pLength(p) == *l);
717  int i, l1;
718  poly p1 = p;
719  ring r = bucket->bucket_ring;
720 
721  if (*l <= 0)
722  {
723  l1 = pLength(p1);
724  *l = l1;
725  }
726  else
727  l1 = *l;
728 
729  if (m == NULL || p == NULL) return;
730 
731 #ifndef HAVE_PSEUDO_BUCKETS
732  kBucketMergeLm(bucket);
733  kbTest(bucket);
734  i = pLogLength(l1);
735 
736 #if defined(HAVE_PLURAL)
737  if ((rField_is_Ring(r) && !(rField_is_Domain(r)))
738  ||(rIsPluralRing(r)))
739  {
740  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
741  p1=pp_Mult_mm(p,m,r);
742  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
743  l1=pLength(p1);
744  i = pLogLength(l1);
745  }
746  else
747 #endif
748  {
749  if ((i <= bucket->buckets_used) && (bucket->buckets[i] != NULL))
750  {
751  assume(pLength(bucket->buckets[i])==(unsigned)bucket->buckets_length[i]);
752 //#ifdef USE_COEF_BUCKETS
753 // if(bucket->coef[i]!=NULL)
754 // {
755 // poly mult=p_Mult_mm(bucket->coef[i],m,r);
756 // bucket->coef[i]=NULL;
757 // p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], mult, p1,
758 // bucket->buckets_length[i], l1,
759 // spNoether, r);
760 // }
761 // else
762 //#endif
763  MULTIPLY_BUCKET(bucket,i);
764  p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], m, p1,
765  bucket->buckets_length[i], l1,
766  spNoether, r);
767  l1 = bucket->buckets_length[i];
768  bucket->buckets[i] = NULL;
769  bucket->buckets_length[i] = 0;
770  i = pLogLength(l1);
771  }
772  else
773  {
774  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
775  if (spNoether != NULL)
776  {
777  l1 = -1;
778  p1 = r->p_Procs->pp_Mult_mm_Noether(p1, m, spNoether, l1, r);
779  i = pLogLength(l1);
780  }
781  else
782  {
783  p1 = r->p_Procs->pp_Mult_mm(p1, m, r);
784  }
785  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
786  }
787  }
788 
789  while (bucket->buckets[i] != NULL)
790  {
791  //kbTest(bucket);
792  MULTIPLY_BUCKET(bucket,i);
793  p1 = p_Add_q(p1, bucket->buckets[i],
794  l1, bucket->buckets_length[i], r);
795  bucket->buckets[i] = NULL;
796  bucket->buckets_length[i] = 0;
797  i = pLogLength(l1);
798  }
799 
800  bucket->buckets[i] = p1;
801  bucket->buckets_length[i]=l1;
802  if (i >= bucket->buckets_used)
803  bucket->buckets_used = i;
804  else
805  kBucketAdjustBucketsUsed(bucket);
806 #else // HAVE_PSEUDO_BUCKETS
807  bucket->p = p_Minus_mm_Mult_qq(bucket->p, m, p,
808  bucket->l, l1,
809  spNoether, r);
810 #endif
811 }
812 
813 //////////////////////////////////////////////////////////////////////////
814 ///
815 /// Bpoly == Bpoly + m*p; where m is a monom
816 /// Does not destroy p and m
817 /// assume (l <= 0 || pLength(p) == l)
818 void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l)
819 {
820  assume((!rIsPluralRing(bucket->bucket_ring))||p_IsConstant(m, bucket->bucket_ring));
821  assume(l <= 0 || pLength(p) == (unsigned)l);
822  int i, l1;
823  poly p1 = p;
824  ring r = bucket->bucket_ring;
825 
826  if (m == NULL || p == NULL) return;
827 
828  if (l <= 0)
829  {
830  l1 = pLength(p1);
831  l = l1;
832  }
833  else
834  l1 = l;
835 
836  kBucketMergeLm(bucket);
837  kbTest(bucket);
838  i = pLogLength(l1);
839  #ifdef USE_COEF_BUCKETS
840  number n=n_Init(1,r->cf);
841  #endif
842  if (i <= bucket->buckets_used && bucket->buckets[i] != NULL)
843  {
844  //if (FALSE){
845  #ifdef USE_COEF_BUCKETS
846  if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
847  {
848  number orig_coef=p_GetCoeff(bucket->coef[i],r);
849  //we take ownership:
850  p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
851  number add_coef=n_Copy(p_GetCoeff(m,r),r);
852  number gcd=n_Gcd(add_coef, orig_coef,r);
853 
854  if (!(n_IsOne(gcd,r)))
855  {
856  number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
857  number add_coef2=n_ExactDiv(add_coef, gcd,r);
858  n_Delete(&orig_coef,r);
859  n_Delete(&add_coef,r);
860  orig_coef=orig_coef2;
861  add_coef=add_coef2;
862 
863  //p_Mult_nn(bucket->buckets[i], orig_coef,r);
864  n_Delete(&n,r);
865  n=gcd;
866  }
867 
868  //assume(n_IsOne(n,r));
869  number backup=p_GetCoeff(m,r);
870 
871  p_SetCoeff0(m,add_coef,r);
872  bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
873 
874  n_Delete(&orig_coef,r);
875  p_Delete(&bucket->coef[i],r);
876 
877  p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
878  bucket->buckets_length[i], l1, r);
879  l1=bucket->buckets_length[i];
880  bucket->buckets[i]=NULL;
881  bucket->buckets_length[i] = 0;
882  i = pLogLength(l1);
883  assume(l1==pLength(p1));
884 
885  p_SetCoeff(m,backup,r); //deletes add_coef
886  }
887  else
888  #endif
889  {
890  MULTIPLY_BUCKET(bucket,i);
891  p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
892  bucket->buckets_length[i], l1, r);
893  l1 = bucket->buckets_length[i];
894  bucket->buckets[i] = NULL;
895  bucket->buckets_length[i] = 0;
896  i = pLogLength(l1);
897  }
898  }
899  else
900  {
901  #ifdef USE_COEF_BUCKETS
902  number swap_n=p_GetCoeff(m,r);
903 
904  assume(n_IsOne(n,r));
905  p_SetCoeff0(m,n,r);
906  n=swap_n;
907  //p_SetCoeff0(n, swap_n, r);
908  //p_GetCoeff0(n, swap_n,r);
909  #endif
910  p1 = r->p_Procs->pp_Mult_mm(p1, m, r);
911  #ifdef USE_COEF_BUCKETS
912  //m may not be changed
913  p_SetCoeff(m,n_Copy(n,r),r);
914  #endif
915  }
916 
917  while ((bucket->buckets[i] != NULL) && (p1!=NULL))
918  {
919  assume(i!=0);
920  #ifdef USE_COEF_BUCKETS
921  if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
922  {
923  number orig_coef=p_GetCoeff(bucket->coef[i],r);
924  //we take ownership:
925  p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
926  number add_coef=n_Copy(n,r);
927  number gcd=n_Gcd(add_coef, orig_coef,r);
928 
929  if (!(n_IsOne(gcd,r)))
930  {
931  number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
932  number add_coef2=n_ExactDiv(add_coef, gcd,r);
933  n_Delete(&orig_coef,r);
934  n_Delete(&n,r);
935  n_Delete(&add_coef,r);
936  orig_coef=orig_coef2;
937  add_coef=add_coef2;
938  //p_Mult_nn(bucket->buckets[i], orig_coef,r);
939  n=gcd;
940  }
941  //assume(n_IsOne(n,r));
942  bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
943  p1=__p_Mult_nn(p1,add_coef,r);
944 
945  p1 = p_Add_q(p1, bucket->buckets[i],r);
946  l1=pLength(p1);
947 
948  bucket->buckets[i]=NULL;
949  n_Delete(&orig_coef,r);
950  p_Delete(&bucket->coef[i],r);
951  //l1=bucket->buckets_length[i];
952  assume(l1==pLength(p1));
953  }
954  else
955  #endif
956  {
957  //don't do that, pull out gcd
958  #ifdef USE_COEF_BUCKETS
959  if(!(n_IsOne(n,r)))
960  {
961  p1=__p_Mult_nn(p1, n, r);
962  n_Delete(&n,r);
963  n=n_Init(1,r);
964  }
965  #endif
966  MULTIPLY_BUCKET(bucket,i);
967  p1 = p_Add_q(p1, bucket->buckets[i],
968  l1, bucket->buckets_length[i], r);
969  bucket->buckets[i] = NULL;
970  bucket->buckets_length[i] = 0;
971  }
972  i = pLogLength(l1);
973  }
974 
975  bucket->buckets[i] = p1;
976 #ifdef USE_COEF_BUCKETS
977  assume(bucket->coef[i]==NULL);
978 
979  if (!(n_IsOne(n,r)))
980  {
981  bucket->coef[i]=p_NSet(n,r);
982  }
983  else
984  {
985  bucket->coef[i]=NULL;
986  n_Delete(&n,r);
987  }
988 
989  if (p1==NULL)
990  p_Delete(&bucket->coef[i],r);
991 #endif
992  bucket->buckets_length[i]=l1;
993  if (i > bucket->buckets_used)
994  bucket->buckets_used = i;
995  else
996  kBucketAdjustBucketsUsed(bucket);
997 
998  kbTest(bucket);
999 }
1001 poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append)
1002 {
1003  if (q == NULL) return append;
1004  poly lm;
1005  loop
1006  {
1007  lm = kBucketGetLm(bucket);
1008  if (lm == NULL) return append;
1009  if (p_LmCmp(lm, q, bucket->bucket_ring) == 1)
1010  {
1011  lm = kBucketExtractLm(bucket);
1012  pNext(append) = lm;
1013  pIter(append);
1014  }
1015  else
1016  {
1017  return append;
1018  }
1019  }
1020 }
1021 
1022 /////////////////////////////////////////////////////////////////////////////
1023 //
1024 // Extract all monomials from bucket with component comp
1025 // Return as a polynomial *p with length *l
1026 // In other words, afterwards
1027 // Bpoly = Bpoly - (poly consisting of all monomials with component comp)
1028 // and components of monomials of *p are all 0
1029 //
1030 
1031 // Hmm... for now I'm too lazy to implement those independent of currRing
1032 // But better declare it extern than including polys.h
1033 extern void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r);
1035 void kBucketTakeOutComp(kBucket_pt bucket,
1036  long comp,
1037  poly *r_p, int *l)
1038 {
1039  poly p = NULL, q;
1040  int i, lp = 0, lq;
1041 
1042 #ifndef HAVE_PSEUDO_BUCKETS
1043  kBucketMergeLm(bucket);
1044  for (i=1; i<=bucket->buckets_used; i++)
1045  {
1046  if (bucket->buckets[i] != NULL)
1047  {
1048  MULTIPLY_BUCKET(bucket,i);
1049  p_TakeOutComp(&(bucket->buckets[i]), comp, &q, &lq, bucket->bucket_ring);
1050  if (q != NULL)
1051  {
1052  assume(pLength(q) == (unsigned)lq);
1053  bucket->buckets_length[i] -= lq;
1054  assume(pLength(bucket->buckets[i]) == (unsigned)bucket->buckets_length[i]);
1055  p = p_Add_q(p, q, lp, lq, bucket->bucket_ring);
1056  }
1057  }
1058  }
1059  kBucketAdjustBucketsUsed(bucket);
1060 #else
1061  p_TakeOutComp(&(bucket->p), comp, &p, &lp,bucket->bucket_ring);
1062  (bucket->l) -= lp;
1063 #endif
1064  *r_p = p;
1065  *l = lp;
1066 
1067  kbTest(bucket);
1068 }
1069 
1070 /////////////////////////////////////////////////////////////////////////////
1071 // Reduction of Bpoly with a given poly
1072 //
1073 
1074 extern int ksCheckCoeff(number *a, number *b);
1076 number kBucketPolyRed(kBucket_pt bucket,
1077  poly p1, int l1,
1078  poly spNoether)
1079 {
1080  ring r=bucket->bucket_ring;
1081  assume((!rIsPluralRing(r))||p_LmEqual(p1,kBucketGetLm(bucket), r));
1082  assume(p1 != NULL &&
1083  p_DivisibleBy(p1, kBucketGetLm(bucket), r));
1084  assume(pLength(p1) == (unsigned) l1);
1085 
1086  poly a1 = pNext(p1), lm = kBucketExtractLm(bucket);
1087  BOOLEAN reset_vec=FALSE;
1088  number rn;
1089 
1090  /* we shall reduce bucket=bn*lm+... by p1=an*t+a1 where t=lm(p1)
1091  and an,bn shall be defined further down only if lc(p1)!=1
1092  we already know: an|bn and t|lm */
1093  if(a1==NULL)
1094  {
1095  p_LmDelete(&lm, r);
1096  return n_Init(1,r->cf);
1097  }
1098 
1099  if (! n_IsOne(pGetCoeff(p1),r->cf))
1100  {
1101  number an = pGetCoeff(p1), bn = pGetCoeff(lm);
1102 //StringSetS("##### an = "); nWrite(an); PrintS(StringEndS("\n")); // NOTE/TODO: use StringAppendS("\n"); omFree(s);
1103 //StringSetS("##### bn = "); nWrite(bn); PrintS(StringEndS("\n")); // NOTE/TODO: use StringAppendS("\n"); omFree(s);
1104  /* ksCheckCoeff: divide out gcd from an and bn: */
1105  int ct = ksCheckCoeff(&an, &bn,r->cf);
1106  /* the previous command returns ct=0 or ct=2 iff an!=1
1107  note: an is now 1 or -1 */
1108 
1109  /* setup factor for p1 which cancels leading terms */
1110  p_SetCoeff(lm, bn, r);
1111  if ((ct == 0) || (ct == 2))
1112  {
1113  /* next line used to be here before but is WRONG:
1114  kBucket_Mult_n(bucket, an);
1115  its use would result in a wrong sign for the tail of bucket
1116  in the reduction */
1117 
1118  /* correct factor for cancelation by changing sign if an=-1 */
1119  if (rField_is_Ring(r))
1120  lm = __p_Mult_nn(lm, an, r);
1121  else
1122  kBucket_Mult_n(bucket, an);
1123  }
1124  rn = an;
1125  }
1126  else
1127  {
1128  rn = n_Init(1,r->cf);
1129  }
1130 
1131  if (p_GetComp(p1, r) != p_GetComp(lm, r))
1132  {
1133  p_SetCompP(a1, p_GetComp(lm, r), r);
1134  reset_vec = TRUE;
1135  p_SetComp(lm, p_GetComp(p1, r), r);
1136  p_Setm(lm, r);
1137  }
1138 
1139  p_ExpVectorSub(lm, p1, r);
1140  l1--;
1141 
1142  assume((unsigned)l1==pLength(a1));
1143 #if 0
1144  BOOLEAN backuped=FALSE;
1145  number coef;
1146  //@Viktor, don't ignore coefficients on monomials
1147  if(l1==1) {
1148 
1149  //if (rField_is_Q(r)) {
1150  //avoid this for function fields, as gcds are expensive at the moment
1151 
1152 
1153  coef=p_GetCoeff(a1,r);
1154  lm=p_Mult_nn(lm, coef, r);
1155  p_SetCoeff0(a1, n_Init(1,r), r);
1156  backuped=TRUE;
1157  //WARNING: not thread_safe
1158  //deletes coef as side effect
1159  //}
1160  }
1161 #endif
1162 
1163  kBucket_Minus_m_Mult_p(bucket, lm, a1, &l1, spNoether);
1164 
1165 #if 0
1166  if (backuped)
1167  p_SetCoeff0(a1,coef,r);
1168 #endif
1169 
1170  p_LmDelete(&lm, r);
1171  if (reset_vec) p_SetCompP(a1, 0, r);
1172  kbTest(bucket);
1173  return rn;
1174 }
1175 
1176 #ifndef USE_COEF_BUCKETS
1177 void kBucketSimpleContent(kBucket_pt bucket)
1178 {
1179  if (bucket->buckets[0]==NULL) return;
1180 
1181  ring r=bucket->bucket_ring;
1182  if (rField_is_Ring(r)) return;
1183 
1184  coeffs cf=r->cf;
1185  if (cf->cfSubringGcd==ndGcd) /* trivial gcd*/ return;
1186 
1187  number nn=pGetCoeff(bucket->buckets[0]);
1188  //if ((bucket->buckets_used==0)
1189  //&&(!n_IsOne(nn,cf)))
1190  //{
1191  // if (TEST_OPT_PROT) PrintS("@");
1192  // p_SetCoeff(bucket->buckets[0],n_Init(1,cf),r);
1193  // return;
1194  //}
1195 
1196  if (n_Size(nn,cf)<2) return;
1197 
1198  //kBucketAdjustBucketsUsed(bucket);
1199  number coef=n_Copy(nn,cf);
1200  // find an initial guess of a gcd
1201  for (int i=1; i<=bucket->buckets_used;i++)
1202  {
1203  if (bucket->buckets[i]!=NULL)
1204  {
1205  number t=p_InitContent(bucket->buckets[i],r);
1206  if (n_Size(t,cf)<2)
1207  {
1208  n_Delete(&t,cf);
1209  n_Delete(&coef,cf);
1210  return;
1211  }
1212  number t2=n_SubringGcd(coef,t,cf);
1213  n_Delete(&t,cf);
1214  n_Delete(&coef,cf);
1215  coef=t2;
1216  if (n_Size(coef,cf)<2) { n_Delete(&coef,cf);return;}
1217  }
1218  }
1219  // find the gcd
1220  for (int i=0; i<=bucket->buckets_used;i++)
1221  {
1222  if (bucket->buckets[i]!=NULL)
1223  {
1224  poly p=bucket->buckets[i];
1225  while(p!=NULL)
1226  {
1227  number t=n_SubringGcd(coef,pGetCoeff(p),cf);
1228  if (n_Size(t,cf)<2)
1229  {
1230  n_Delete(&t,cf);
1231  n_Delete(&coef,cf);
1232  return;
1233  }
1234  pIter(p);
1235  }
1236  }
1237  }
1238  // divided by the gcd
1239  if (TEST_OPT_PROT) PrintS("@");
1240  for (int i=bucket->buckets_used;i>=0;i--)
1241  {
1242  if (bucket->buckets[i]!=NULL)
1243  {
1244  poly p=bucket->buckets[i];
1245  while(p!=NULL)
1246  {
1247  number d = n_ExactDiv(pGetCoeff(p),coef,cf);
1248  p_SetCoeff(p,d,r);
1249  pIter(p);
1250  }
1251  }
1252  }
1253  n_Delete(&coef,cf);
1254 }
1255 #else
1256 static BOOLEAN nIsPseudoUnit(number n, ring r)
1257 {
1258  if (rField_is_Zp(r))
1259  return TRUE;
1260 
1261  if (rParameter(r)==NULL)
1262  {
1263  return (n_Size(n,r->cf)==1);
1264  }
1265  //if (r->parameter!=NULL)
1266  return (n_IsOne(n,r->cf) || n_IsMOne(n,r->cf));
1267 }
1268 
1269 void kBucketSimpleContent(kBucket_pt bucket)
1270 {
1271  ring r=bucket->bucket_ring;
1272  int i;
1273  //PrintS("HHHHHHHHHHHHH");
1274  for (i=0;i<=MAX_BUCKET;i++)
1275  {
1276  //if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]!=NULL))
1277  // PrintS("H2H2H2");
1278  if (i==0)
1279  {
1280  assume(bucket->buckets[i]==NULL);
1281  }
1282  if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]==NULL))
1283  return;
1284  }
1285  for (i=0;i<=MAX_BUCKET;i++)
1286  {
1287  //if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]!=NULL))
1288  // PrintS("H2H2H2");
1289  if (i==0)
1290  {
1291  assume(bucket->buckets[i]==NULL);
1292  }
1293  if ((bucket->buckets[i]!=NULL)
1294  && (nIsPseudoUnit(p_GetCoeff(bucket->coef[i],r),r)))
1295  return;
1296  }
1297  //return;
1298 
1299  number coef=n_Init(0,r);
1300  //ATTENTION: will not work correct for GB over ring
1301  //if (TEST_OPT_PROT)
1302  // PrintS("CCCCCCCCCCCCC");
1303  for (i=MAX_BUCKET;i>=0;i--)
1304  {
1305  if (i==0)
1306  {
1307  assume(bucket->buckets[i]==NULL);
1308  }
1309  if (bucket->buckets[i]!=NULL)
1310  {
1311  assume(bucket->coef[i]!=NULL);
1312  assume(!(n_IsZero(pGetCoeff(bucket->coef[i]),r)));
1313 
1314  //in this way it should crash on programming errors, yeah
1315  number temp=n_Gcd(coef, pGetCoeff(bucket->coef[i]),r);
1316  n_Delete(&coef,r );
1317  coef=temp;
1318  if (nIsPseudoUnit(coef,r))
1319  {
1320  n_Delete(&coef,r);
1321  return;
1322  }
1323  assume(!(n_IsZero(coef,r)));
1324  }
1325  }
1326  if (n_IsZero(coef,r))
1327  {
1328  n_Delete(&coef,r);
1329  return;
1330  }
1331  if (TEST_OPT_PROT)
1332  PrintS("S");
1333  for(i=0;i<=MAX_BUCKET;i++)
1334  {
1335  if (bucket->buckets[i]!=NULL)
1336  {
1337  assume(!(n_IsZero(coef,r)));
1338  assume(bucket->coef[i]!=NULL);
1339  number lc=p_GetCoeff(bucket->coef[i],r);
1340  p_SetCoeff(bucket->coef[i], n_ExactDiv(lc,coef,r),r);
1341  assume(!(n_IsZero(p_GetCoeff(bucket->coef[i],r),r)));
1342  }
1343  }
1344  n_Delete(&coef,r);
1345 }
1346 #endif
1347 
1349 poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i)
1350 {
1351  assume(bucket->buckets[i]!=NULL);
1352 
1353  poly p=bucket->buckets[i];
1354  bucket->buckets_length[i]--;
1355 #ifdef USE_COEF_BUCKETS
1356  ring r=bucket->bucket_ring;
1357  if (bucket->coef[i]!=NULL)
1358  {
1359  poly next=pNext(p);
1360  if (next==NULL)
1361  {
1362  MULTIPLY_BUCKET(bucket,i);
1363  p=bucket->buckets[i];
1364  bucket->buckets[i]=NULL;
1365  return p;
1366  }
1367  else
1368  {
1369  bucket->buckets[i]=next;
1370  number c=p_GetCoeff(bucket->coef[i],r);
1371  pNext(p)=NULL;
1372  p=__p_Mult_nn(p,c,r);
1373  assume(p!=NULL);
1374  return p;
1375  }
1376  }
1377  else
1378 #endif
1379  {
1380  bucket->buckets[i]=pNext(bucket->buckets[i]);
1381  pNext(p)=NULL;
1382  assume(p!=NULL);
1383  return p;
1384  }
1385 }
1386 
1387 /*
1388 * input - output: a, b
1389 * returns:
1390 * a := a/gcd(a,b), b := b/gcd(a,b)
1391 * and return value
1392 * 0 -> a != 1, b != 1
1393 * 1 -> a == 1, b != 1
1394 * 2 -> a != 1, b == 1
1395 * 3 -> a == 1, b == 1
1396 * this value is used to control the spolys
1397 */
1398 int ksCheckCoeff(number *a, number *b, const coeffs r)
1399 {
1400  int c = 0;
1401  number an = *a, bn = *b;
1402  n_Test(an,r);
1403  n_Test(bn,r);
1404 
1405  number cn = n_SubringGcd(an, bn, r);
1406 
1407  if(n_IsOne(cn, r))
1408  {
1409  an = n_Copy(an, r);
1410  bn = n_Copy(bn, r);
1411  }
1412  else
1413  {
1414  an = n_ExactDiv(an, cn, r); n_Normalize(an,r);
1415  bn = n_ExactDiv(bn, cn, r); n_Normalize(bn,r);
1416  }
1417  n_Delete(&cn, r);
1418  if (n_IsOne(an, r))
1419  {
1420  c = 1;
1421  }
1422  if (n_IsOne(bn, r))
1423  {
1424  c += 2;
1425  }
1426  *a = an;
1427  *b = bn;
1428  return c;
1429 }
1430 
kBucketSimpleContent
void kBucketSimpleContent(kBucket_pt bucket)
Definition: kbuckets.cc:1176
ksCheckCoeff
int ksCheckCoeff(number *a, number *b)
FALSE
#define FALSE
Definition: auxiliary.h:94
dReportError
int dReportError(const char *fmt,...)
Definition: dError.cc:43
kBucketSetLm
void kBucketSetLm(kBucket_pt bucket, poly lm)
omalloc.h
kBucketCanonicalize
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
p_GetCoeff
#define p_GetCoeff(p, r)
Definition: monomials.h:48
p_GetComp
#define p_GetComp(p, r)
Definition: monomials.h:62
j
int j
Definition: facHensel.cc:105
p_SetCoeff0
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:58
p_Normalize
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3720
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:101
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:621
rField_is_Domain
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:477
LOG4
static int LOG4(int v)
Some internal stuff.
Definition: kbuckets.cc:52
lq
Definition: lq.h:38
omGetSpecBin
#define omGetSpecBin(size)
Definition: omBin.h:10
kBucket_pt
kBucket * kBucket_pt
Definition: ring.h:24
kBucketPolyRed
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1075
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:246
MAX_BUCKET
#define MAX_BUCKET
Bucket definition (should be no one elses business, though)
Definition: kbuckets.h:174
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:1105
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:992
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
kBucketExtractLmOfBucket
poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i)
Definition: kbuckets.cc:1348
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:454
p_InitContent
number p_InitContent(poly ph, const ring r)
Definition: p_polys.cc:2546
kBucket::l
int l
Definition: kbuckets.h:182
p_Test
#define p_Test(p, r)
Definition: p_polys.h:156
pLogLength
static unsigned int pLogLength(unsigned int l)
Definition: kbuckets.cc:67
options.h
pp_Mult_mm
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:973
auxiliary.h
omAlloc0Bin
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:204
kBucketGetLm
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:502
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:463
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:467
loop
#define loop
Definition: structs.h:77
b
CanonicalForm b
Definition: cfModGcd.cc:4044
__p_Mult_nn
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:913
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:577
p_ExpVectorSub
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition: p_polys.h:1359
p_LmEqual
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1629
rIsPluralRing
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:397
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:184
next
ListNode * next
Definition: janet.h:31
kBucket_bin
static omBin kBucket_bin
Definition: kbuckets.cc:41
omCheckAddrBin
#define omCheckAddrBin(addr, bin)
Definition: omAllocDecl.h:323
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:507
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:650
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:212
PrintS
void PrintS(const char *s)
Definition: reporter.cc:283
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
kBucketNormalize
void kBucketNormalize(kBucket_pt bucket)
apply n_Normalize to all coefficients
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:489
kbTest
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:193
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:712
rField_is_Ring
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:474
kBucket_Mult_n
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition: kbuckets.cc:594
pFalseReturn
#define pFalseReturn(cond)
Definition: monomials.h:136
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:531
ndGcd
number ndGcd(number, number, const coeffs r)
Definition: numbers.cc:162
p_LmDelete
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:699
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:817
pIter
#define pIter(p)
Definition: monomials.h:35
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:537
p_DivisibleBy
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1809
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1479
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:517
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:556
kbuckets.h
ring.h
omBin
omBin_t * omBin
Definition: omStructs.h:11
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:878
kBucket::bucket_ring
ring bucket_ring
Definition: kbuckets.h:191
kBucket::p
poly p
Definition: kbuckets.h:181
p_NSet
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1432
kBucketDeleteAndDestroy
void kBucketDeleteAndDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:219
kBucketTakeOutComp
void kBucketTakeOutComp(kBucket_pt bucket, long comp, poly *r_p, int *l)
Definition: kbuckets.cc:1034
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:401
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:471
pSetCoeff0
#define pSetCoeff0(p, n)
Definition: monomials.h:57
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:450
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:685
m
int m
Definition: cfEzgcd.cc:121
assume
#define assume(x)
Definition: mod2.h:384
NULL
#define NULL
Definition: omList.c:9
p_TakeOutComp
void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r)
Definition: p_polys.cc:3443
kBucketAdjust
void kBucketAdjust(kBucket_pt bucket, int i)
Bucket number i from bucket is out of length sync, resync.
Definition: kbuckets.cc:561
kBucketIsCleared
BOOLEAN kBucketIsCleared(kBucket_pt bucket)
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:239
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:687
kBucket
Definition: kbuckets.h:177
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:225
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:39
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:1000
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:44
p_IsConstant
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1907
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:205
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:42
rParameter
static const char ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:614
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:569
n_Test
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:737
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:257
rField_is_Zp
static BOOLEAN rField_is_Zp(const ring r)
Definition: ring.h:490
numbers.h
pNext
#define pNext(p)
Definition: monomials.h:34
p_Mult_nn
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:900
coeffs.h