source: git/kernel/kbuckets.cc @ 585bbcb

spielwiese
Last change on this file since 585bbcb was dc5c491, checked in by Michael Brickenstein <bricken@…>, 20 years ago
*bricken: bugfix (compile time) for case of not USE_COEF_BUCKETS git-svn-id: file:///usr/local/Singular/svn/trunk@7530 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 18.9 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: kbuckets.cc,v 1.2 2004-10-07 18:10:01 bricken Exp $ */
5
6#include "mod2.h"
7#include "structs.h"
8#include "omalloc.h"
9#include "p_polys.h"
10#include "febase.h"
11#include "pShallowCopyDelete.h"
12#include "kbuckets.h"
13#include "numbers.h"
14#include "p_Procs.h"
15
16#ifdef HAVE_COEF_BUCKETS
17#define USE_COEF_BUCKETS
18#endif
19
20#ifdef USE_COEF_BUCKETS
21#define MULTIPLY_BUCKET(B,I) do                                        \
22  { if (B->coef[I]!=NULL)                                              \
23    {                                                                  \
24      B->buckets[I]=p_Mult_q(B->buckets[I],B->coef[I],B->bucket_ring); \
25      B->coef[I]=NULL;                                                 \
26    }                                                                  \
27  } while(0)
28#else
29#define MULTIPLY_BUCKET(B,I)
30#endif
31static omBin kBucket_bin = omGetSpecBin(sizeof(kBucket));
32
33//////////////////////////////////////////////////////////////////////////
34///
35/// Some internal stuff
36///
37
38// returns ceil(log_4(l))
39inline unsigned int pLogLength(unsigned int l)
40{
41  unsigned int i = 0;
42
43  if (l == 0) return 0;
44  l--;
45#ifdef BUCKET_TWO_BASE
46  while ((l = (l >> 1))) i++;
47#else
48  while ((l = (l >> 2))) i++;
49#endif
50  return i+1;
51}
52
53// returns ceil(log_4(pLength(p)))
54inline unsigned int pLogLength(poly p)
55{
56  return pLogLength((unsigned int) pLength(p));
57}
58
59#ifdef KDEBUG
60
61#ifndef HAVE_PSEUDO_BUCKETS
62BOOLEAN kbTest_i(kBucket_pt bucket, int i)
63{
64  #ifdef USE_COEF_BUCKETS
65  assume(bucket->coef[0]==NULL);
66  if ((bucket->coef[i]!=NULL) && (bucket->buckets[i]==NULL))
67  {
68    dReportError("Bucket %d coef not NULL", i);
69  }
70  if (bucket->coef[i]!=NULL)
71    _p_Test(bucket->coef[i],bucket->bucket_ring,PDEBUG);
72  #endif
73  pFalseReturn(p_Test(bucket->buckets[i], bucket->bucket_ring));
74  if (bucket->buckets_length[i] != pLength(bucket->buckets[i]))
75  {
76    dReportError("Bucket %d lengths difference should:%d has:%d",
77                 i, bucket->buckets_length[i], pLength(bucket->buckets[i]));
78  }
79  else if (i > 0 && (int) pLogLength(bucket->buckets_length[i]) > i)
80  {
81    dReportError("Bucket %d too long %d",
82                 i, bucket->buckets_length[i]);
83  }
84  if (i==0 && bucket->buckets_length[0] > 1)
85  {
86    dReportError("Bucket 0 too long");
87  }
88  return TRUE;
89}
90
91
92BOOLEAN kbTest(kBucket_pt bucket)
93{
94  int i;
95  poly lm = bucket->buckets[0];
96
97  omCheckAddrBin(bucket, kBucket_bin);
98  if (! kbTest_i(bucket, 0)) return FALSE;
99  for (i=1; i<= (int) bucket->buckets_used; i++)
100  {
101    if (!kbTest_i(bucket, i)) return FALSE;
102    if (lm != NULL &&  bucket->buckets[i] != NULL
103        && p_LmCmp(lm, bucket->buckets[i], bucket->bucket_ring) != 1)
104    {
105      dReportError("Bucket %d larger than lm", i);
106      return FALSE;
107    }
108    if (!p_Test(bucket->buckets[i],bucket->bucket_ring))
109    {
110      dReportError("Bucket %d is not =0(4)", i);
111      return FALSE;
112    }
113  }
114
115  for (; i<=MAX_BUCKET; i++)
116  {
117    if (bucket->buckets[i] != NULL || bucket->buckets_length[i] != 0)
118    {
119      dReportError("Bucket %d not zero", i);
120      return FALSE;
121    }
122  }
123  return TRUE;
124}
125
126#else // HAVE_PSEUDO_BUCKETS
127BOOLEAN kbTest(kBucket_pt bucket)
128{
129  return TRUE;
130}
131#endif // ! HAVE_PSEUDO_BUCKETS
132#endif // KDEBUG
133
134//////////////////////////////////////////////////////////////////////////
135///
136/// Creation/Destruction of buckets
137///
138
139kBucket_pt kBucketCreate(ring bucket_ring)
140{
141  assume(bucket_ring != NULL);
142  kBucket_pt bucket = (kBucket_pt) omAlloc0Bin(kBucket_bin);
143  bucket->bucket_ring = bucket_ring;
144  return bucket;
145}
146void kBucketDestroy(kBucket_pt *bucket_pt)
147{
148  omFreeBin(*bucket_pt, kBucket_bin);
149  *bucket_pt = NULL;
150}
151
152
153void kBucketDeleteAndDestroy(kBucket_pt *bucket_pt)
154{
155  kBucket_pt bucket = *bucket_pt;
156  kbTest(bucket);
157  int i;
158  for (i=0; i<= bucket->buckets_used; i++)
159  {
160    if (bucket->buckets[i] != NULL)
161    {
162      p_Delete(&(bucket->buckets[i]), bucket->bucket_ring);
163#ifdef USE_COEF_BUCKETS
164      if (bucket->coef[i]!=NULL)
165        p_Delete(&(bucket->coef[i]), bucket->bucket_ring);
166#endif
167    }
168  }
169  omFreeBin(bucket, kBucket_bin);
170  *bucket_pt = NULL;
171}
172
173/////////////////////////////////////////////////////////////////////////////
174// Convertion from/to Bpolys
175//
176#ifndef HAVE_PSEUDO_BUCKETS
177
178inline void kBucketMergeLm(kBucket_pt bucket)
179{
180  if (bucket->buckets[0] != NULL)
181  {
182    poly lm = bucket->buckets[0];
183    int i = 1;
184#ifdef BUCKET_TWO_BASE
185    int l = 2;
186    while ( bucket->buckets_length[i] >= l)
187    {
188      i++;
189      l = l << 1;
190    }
191#else
192    int l = 4;
193    while ( bucket->buckets_length[i] >= l)
194    {
195      i++;
196      l = l << 2;
197    }
198#endif
199    MULTIPLY_BUCKET(bucket,i);
200    pNext(lm) = bucket->buckets[i];
201    bucket->buckets[i] = lm;
202    bucket->buckets_length[i]++;
203    assume(i <= bucket->buckets_used+1);
204    if (i > bucket->buckets_used)  bucket->buckets_used = i;
205    bucket->buckets[0] = NULL;
206    bucket->buckets_length[0] = 0;
207  }
208}
209
210static BOOLEAN kBucketIsCleared(kBucket_pt bucket)
211{
212  int i;
213
214  for (i = 0;i<=MAX_BUCKET;i++)
215  {
216    if (bucket->buckets[i] != NULL) return FALSE;
217    if (bucket->buckets_length[i] != 0) return FALSE;
218  }
219  return TRUE;
220}
221
222void kBucketInit(kBucket_pt bucket, poly lm, int length)
223{
224  assume(bucket != NULL);
225  assume(length <= 0 || length == pLength(lm));
226  assume(kBucketIsCleared(bucket));
227
228  if (lm == NULL) return;
229
230  if (length <= 0)
231    length = pLength(lm);
232
233  bucket->buckets[0] = lm;
234  bucket->buckets_length[0] = 1;
235  if (length > 1)
236  {
237    unsigned int i = pLogLength(length-1);
238    bucket->buckets[i] = pNext(lm);
239    pNext(lm) = NULL;
240    bucket->buckets_length[i] = length-1;
241    bucket->buckets_used = i;
242  }
243  else
244  {
245    bucket->buckets_used = 0;
246  }
247}
248
249int kBucketCanonicalize(kBucket_pt bucket)
250{
251  kbTest(bucket);
252  poly p = bucket->buckets[1];
253  poly lm;
254  int pl = bucket->buckets_length[1], i;
255  bucket->buckets[1] = NULL;
256  bucket->buckets_length[1] = 0;
257  ring r=bucket->bucket_ring;
258
259
260  for (i=2; i<=bucket->buckets_used; i++)
261  {
262  #ifdef USE_COEF_BUCKETS
263    if (bucket->coef[i]!=NULL)
264    {
265      p = p_Plus_mm_Mult_qq(p, bucket->coef[i], bucket->buckets[i],
266                 pl, bucket->buckets_length[i], r);
267      p_Delete(&bucket->coef[i],r);
268      p_Delete(&bucket->buckets[i],r);
269    }
270    else
271    p = p_Add_q(p, bucket->buckets[i],
272                 pl, bucket->buckets_length[i], r);
273  #else
274    p = p_Add_q(p, bucket->buckets[i],
275                 pl, bucket->buckets_length[i], r);
276  #endif
277    bucket->buckets[i] = NULL;
278    bucket->buckets_length[i] = 0;
279  }
280
281  lm = bucket->buckets[0];
282  if (lm != NULL)
283  {
284    pNext(lm) = p;
285    p = lm;
286    pl++;
287    bucket->buckets[0] = NULL;
288    bucket->buckets_length[0] = 0;
289  }
290  if (pl > 0)
291  {
292    i = pLogLength(pl);
293    bucket->buckets[i] = p;
294    bucket->buckets_length[i] = pl;
295  }
296  else
297  {
298    i = 0;
299  }
300  bucket->buckets_used = i;
301  assume(pLength(p) == (int) pl);
302  kbTest(bucket);
303  return i;
304}
305
306void kBucketClear(kBucket_pt bucket, poly *p, int *length)
307{
308  int i = kBucketCanonicalize(bucket);
309  if (i > 0)
310  {
311    *p = bucket->buckets[i];
312    *length = bucket->buckets_length[i];
313    bucket->buckets[i] = NULL;
314    bucket->buckets_length[i] = 0;
315    bucket->buckets_used = 0;
316#ifdef USE_COEF_BUCKETS
317    bucket->coef[i]=NULL;
318#endif
319  }
320  else
321  {
322    *p = NULL;
323    *length = 0;
324  }
325}
326
327void kBucketSetLm(kBucket_pt bucket, poly lm)
328{
329  kBucketMergeLm(bucket);
330  pNext(lm) = NULL;
331  bucket->buckets[0] = lm;
332  bucket->buckets_length[0] = 1;
333}
334
335#else // HAVE_PSEUDO_BUCKETS
336
337void kBucketInit(kBucket_pt bucket, poly lm, int length)
338{
339  int i;
340
341  assume(bucket != NULL);
342  assume(length <= 0 || length == pLength(lm));
343
344  bucket->p = lm;
345  if (length <= 0) bucket->l = pLength(lm);
346  else bucket->l = length;
347
348}
349
350const poly kBucketGetLm(kBucket_pt bucket)
351{
352  return bucket->p;
353}
354
355poly kBucketExtractLm(kBucket_pt bucket)
356{
357  poly lm = bucket->p;
358  assume(pLength(bucket->p) == bucket->l);
359  pIter(bucket->p);
360  (bucket->l)--;
361  pNext(lm) = NULL;
362  return lm;
363}
364
365void kBucketClear(kBucket_pt bucket, poly *p, int *length)
366{
367  assume(pLength(bucket->p) == bucket->l);
368  *p = bucket->p;
369  *length = bucket->l;
370  bucket->p = NULL;
371  bucket->l = 0;
372}
373
374#endif // ! HAVE_PSEUDO_BUCKETS
375//////////////////////////////////////////////////////////////////////////
376///
377/// For changing the ring of the Bpoly to new_tailBin
378///
379void kBucketShallowCopyDelete(kBucket_pt bucket,
380                              ring new_tailRing, omBin new_tailBin,
381                              pShallowCopyDeleteProc p_shallow_copy_delete)
382{
383#ifndef HAVE_PSEUDO_BUCKETS
384  int i;
385
386  kBucketCanonicalize(bucket);
387  for (i=0; i<= bucket->buckets_used; i++)
388    if (bucket->buckets[i] != NULL)
389    {
390      MULTIPLY_BUCKET(bucket,i);
391      bucket->buckets[i] = p_shallow_copy_delete(bucket->buckets[i],
392                                                 bucket->bucket_ring,
393                                                 new_tailRing,
394                                                 new_tailBin);
395    }
396#else
397  bucket->p = p_shallow_copy_delete(p,
398                                    bucket_ring,
399                                    new_tailRing,
400                                    new_tailBin);
401#endif
402  bucket->bucket_ring = new_tailRing;
403}
404
405
406
407//////////////////////////////////////////////////////////////////////////
408///
409/// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
410///
411void kBucket_Mult_n(kBucket_pt bucket, number n)
412{
413#ifndef HAVE_PSEUDO_BUCKETS
414  kbTest(bucket);
415  ring r=bucket->bucket_ring;
416  int i;
417
418  for (i=0; i<= bucket->buckets_used; i++)
419  {
420    if (bucket->buckets[i] != NULL)
421    {
422#ifdef USE_COEF_BUCKETS
423      if (i<2)
424        bucket->buckets[i] = p_Mult_nn(bucket->buckets[i], n, r);
425      else
426      if (bucket->coef[i]!=NULL)
427      {
428        bucket->coef[i] = p_Mult_nn(bucket->coef[i],n,r);
429      }
430      else
431      {
432        bucket->coef[i] = p_NSet(n_Copy(n,bucket->bucket_ring),r);
433      }
434#else
435      bucket->buckets[i] = p_Mult_nn(bucket->buckets[i], n, r);
436#endif
437    }
438  }
439  kbTest(bucket);
440#else
441  bucket->p = p_Mult_nn(bucket->p, n, bucket->bucket_ring);
442#endif
443}
444
445
446//////////////////////////////////////////////////////////////////////////
447///
448/// Add to Bucket a poly ,i.e. Bpoly == n*Bpoly
449///
450void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
451{
452  if (q == NULL) return;
453  assume(*l <= 0 || pLength(q) == *l);
454
455  int i, l1;
456  ring r = bucket->bucket_ring;
457
458  if (*l <= 0)
459  {
460    l1 = pLength(q);
461    *l = l1;
462  }
463  else
464    l1 = *l;
465
466  kBucketMergeLm(bucket);
467  kbTest(bucket);
468  i = pLogLength(l1);
469
470  while (bucket->buckets[i] != NULL)
471  {
472    //MULTIPLY_BUCKET(bucket,i);
473  #ifdef USE_COEF_BUCKETS
474    if (bucket->coef[i]!=NULL)
475    {
476      q = p_Plus_mm_Mult_qq(q, bucket->coef[i], bucket->buckets[i],
477                 l1, bucket->buckets_length[i], r);
478      p_Delete(&bucket->coef[i],r);
479      p_Delete(&bucket->buckets[i],r);
480    }
481    else
482    q = p_Add_q(q, bucket->buckets[i],
483                 l1, bucket->buckets_length[i], r);
484  #else
485    q = p_Add_q(q, bucket->buckets[i],
486                 l1, bucket->buckets_length[i], r);
487  #endif
488    bucket->buckets[i] = NULL;
489    bucket->buckets_length[i] = 0;
490    i = pLogLength(l1);
491  }
492
493  bucket->buckets[i] = q;
494  bucket->buckets_length[i]=l1;
495  if (i >= bucket->buckets_used)
496    bucket->buckets_used = i;
497  else
498    kBucketAdjustBucketsUsed(bucket);
499  kbTest(bucket);
500}
501
502
503
504//////////////////////////////////////////////////////////////////////////
505///
506/// Bpoly == Bpoly - m*p; where m is a monom
507/// Does not destroy p and m
508/// assume (*l <= 0 || pLength(p) == *l)
509void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l,
510                            poly spNoether)
511{
512  assume(*l <= 0 || pLength(p) == *l);
513  int i, l1;
514  poly p1 = p;
515  poly last;
516  ring r = bucket->bucket_ring;
517
518  if (*l <= 0)
519  {
520    l1 = pLength(p1);
521    *l = l1;
522  }
523  else
524    l1 = *l;
525
526  if (m == NULL || p == NULL) return;
527
528#ifndef HAVE_PSEUDO_BUCKETS
529  kBucketMergeLm(bucket);
530  kbTest(bucket);
531  i = pLogLength(l1);
532
533  if ((i <= bucket->buckets_used) && (bucket->buckets[i] != NULL))
534  {
535    assume(pLength(bucket->buckets[i])==bucket->buckets_length[i]);
536//#ifdef USE_COEF_BUCKETS
537//     if(bucket->coef[i]!=NULL)
538//     {
539//       poly mult=p_Mult_mm(bucket->coef[i],m,r);
540//       bucket->coef[i]=NULL;
541//       p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], mult, p1,
542//                               bucket->buckets_length[i], l1,
543//                             spNoether, r);
544//     }
545//     else
546//#endif
547    MULTIPLY_BUCKET(bucket,i);
548    p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], m, p1,
549                            bucket->buckets_length[i], l1,
550                            spNoether, r);
551    l1 = bucket->buckets_length[i];
552    bucket->buckets[i] = NULL;
553    bucket->buckets_length[i] = 0;
554    i = pLogLength(l1);
555  }
556  else
557  {
558    pSetCoeff0(m, nNeg(pGetCoeff(m)));
559    if (spNoether != NULL)
560    {
561      l1 = -1;
562      p1 = r->p_Procs->pp_Mult_mm_Noether(p1, m, spNoether, l1, r, last);
563      i = pLogLength(l1);
564    }
565    else
566      p1 = r->p_Procs->pp_Mult_mm(p1, m, r, last);
567    pSetCoeff0(m, nNeg(pGetCoeff(m)));
568  }
569
570  while (bucket->buckets[i] != NULL)
571  {
572    //kbTest(bucket);
573    MULTIPLY_BUCKET(bucket,i);
574    p1 = p_Add_q(p1, bucket->buckets[i],
575                 l1, bucket->buckets_length[i], r);
576    bucket->buckets[i] = NULL;
577    bucket->buckets_length[i] = 0;
578    i = pLogLength(l1);
579  }
580
581  bucket->buckets[i] = p1;
582  bucket->buckets_length[i]=l1;
583  if (i >= bucket->buckets_used)
584    bucket->buckets_used = i;
585  else
586    kBucketAdjustBucketsUsed(bucket);
587#else // HAVE_PSEUDO_BUCKETS
588  bucket->p = p_Minus_mm_Mult_qq(bucket->p, m,  p,
589                               bucket->l, l1,
590                               spNoether, r);
591#endif
592}
593
594//////////////////////////////////////////////////////////////////////////
595///
596/// Bpoly == Bpoly + m*p; where m is a monom
597/// Does not destroy p and m
598/// assume (l <= 0 || pLength(p) == l)
599void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l)
600{
601  assume(l <= 0 || pLength(p) == l);
602  int i, l1;
603  poly p1 = p;
604  poly last;
605  ring r = bucket->bucket_ring;
606
607  if (l <= 0)
608  {
609    l1 = pLength(p1);
610    l = l1;
611  }
612  else
613    l1 = l;
614
615  if (m == NULL || p == NULL) return;
616
617  kBucketMergeLm(bucket);
618  kbTest(bucket);
619  i = pLogLength(l1);
620
621  if (i <= bucket->buckets_used && bucket->buckets[i] != NULL)
622  {
623    MULTIPLY_BUCKET(bucket,i);
624    p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
625                           bucket->buckets_length[i], l1, r);
626    l1 = bucket->buckets_length[i];
627    bucket->buckets[i] = NULL;
628    bucket->buckets_length[i] = 0;
629    i = pLogLength(l1);
630  }
631  else
632  {
633    p1 = r->p_Procs->pp_Mult_mm(p1, m, r, last);
634  }
635
636  while (bucket->buckets[i] != NULL)
637  {
638    MULTIPLY_BUCKET(bucket,i);
639    p1 = p_Add_q(p1, bucket->buckets[i],
640                 l1, bucket->buckets_length[i], r);
641    bucket->buckets[i] = NULL;
642    bucket->buckets_length[i] = 0;
643    i = pLogLength(l1);
644  }
645
646  bucket->buckets[i] = p1;
647  bucket->buckets_length[i]=l1;
648  if (i >= bucket->buckets_used)
649    bucket->buckets_used = i;
650  else
651    kBucketAdjustBucketsUsed(bucket);
652
653  kbTest(bucket);
654}
655
656poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append)
657{
658  if (q == NULL) return append;
659  poly lm;
660  loop
661  {
662    lm = kBucketGetLm(bucket);
663    if (lm == NULL) return append;
664    if (p_LmCmp(lm, q, bucket->bucket_ring) == 1)
665    {
666      lm = kBucketExtractLm(bucket);
667      pNext(append) = lm;
668      pIter(append);
669    }
670    else
671    {
672      return append;
673    }
674  }
675}
676
677/////////////////////////////////////////////////////////////////////////////
678//
679// Extract all monomials from bucket with component comp
680// Return as a polynomial *p with length *l
681// In other words, afterwards
682// Bpoly = Bpoly - (poly consisting of all monomials with component comp)
683// and components of monomials of *p are all 0
684//
685
686// Hmm... for now I'm too lazy to implement those independent of currRing
687// But better declare it extern than including polys.h
688extern void pTakeOutComp(poly *p, Exponent_t comp, poly *q, int *lq);
689void pDecrOrdTakeOutComp(poly *p, Exponent_t comp, Order_t order,
690                         poly *q, int *lq);
691
692void kBucketTakeOutComp(kBucket_pt bucket,
693                        Exponent_t comp,
694                        poly *r_p, int *l)
695{
696  poly p = NULL, q;
697  int i, lp = 0, lq;
698
699#ifndef HAVE_PSEUDO_BUCKETS
700  kBucketMergeLm(bucket);
701  for (i=1; i<=bucket->buckets_used; i++)
702  {
703    if (bucket->buckets[i] != NULL)
704    {
705      MULTIPLY_BUCKET(bucket,i);
706      pTakeOutComp(&(bucket->buckets[i]), comp, &q, &lq);
707      if (q != NULL)
708      {
709        assume(pLength(q) == lq);
710        bucket->buckets_length[i] -= lq;
711        assume(pLength(bucket->buckets[i]) == bucket->buckets_length[i]);
712        p = p_Add_q(p, q, lp, lq, bucket->bucket_ring);
713      }
714    }
715  }
716  kBucketAdjustBucketsUsed(bucket);
717#else
718  pTakeOutComp(&(bucket->p), comp, &p, &lp);
719  (bucket->l) -= lp;
720#endif
721  *r_p = p;
722  *l = lp;
723
724  kbTest(bucket);
725}
726
727void kBucketDecrOrdTakeOutComp(kBucket_pt bucket,
728                               Exponent_t comp, Order_t order,
729                               poly *r_p, int *l)
730{
731  poly p = NULL, q;
732  int i, lp = 0, lq;
733
734#ifndef HAVE_PSEUDO_BUCKETS
735  kBucketMergeLm(bucket);
736  for (i=1; i<=bucket->buckets_used; i++)
737  {
738    if (bucket->buckets[i] != NULL)
739    {
740      MULTIPLY_BUCKET(bucket,i);
741      pDecrOrdTakeOutComp(&(bucket->buckets[i]), comp, order, &q, &lq);
742      if (q != NULL)
743      {
744        bucket->buckets_length[i] -= lq;
745        p = p_Add_q(p, q, lp, lq, bucket->bucket_ring);
746      }
747    }
748  }
749  kBucketAdjustBucketsUsed(bucket);
750#else
751  pDecrOrdTakeOutComp(&(bucket->p), comp, order, &p, &lp);
752  (bucket->l) -= lp;
753#endif
754
755  *r_p = p;
756  *l = lp;
757}
758
759/////////////////////////////////////////////////////////////////////////////
760// Reduction of Bpoly with a given poly
761//
762
763extern int ksCheckCoeff(number *a, number *b);
764
765number kBucketPolyRed(kBucket_pt bucket,
766                      poly p1, int l1,
767                      poly spNoether)
768{
769  assume(p1 != NULL &&
770         p_DivisibleBy(p1,  kBucketGetLm(bucket), bucket->bucket_ring));
771  assume(pLength(p1) == (int) l1);
772
773  poly a1 = pNext(p1), lm = kBucketExtractLm(bucket);
774  BOOLEAN reset_vec=FALSE;
775  number rn;
776
777  if(a1==NULL)
778  {
779    p_DeleteLm(&lm, bucket->bucket_ring);
780    return nInit(1);
781  }
782
783  if (! nIsOne(pGetCoeff(p1)))
784  {
785    number an = pGetCoeff(p1), bn = pGetCoeff(lm);
786    int ct = ksCheckCoeff(&an, &bn);
787    p_SetCoeff(lm, bn, bucket->bucket_ring);
788    if ((ct == 0) || (ct == 2)) kBucket_Mult_n(bucket, an);
789    rn = an;
790  }
791  else
792  {
793    rn = nInit(1);
794  }
795
796  if (p_GetComp(p1, bucket->bucket_ring) != p_GetComp(lm, bucket->bucket_ring))
797  {
798    p_SetCompP(a1, p_GetComp(lm, bucket->bucket_ring), bucket->bucket_ring);
799    reset_vec = TRUE;
800    p_SetComp(lm, p_GetComp(p1, bucket->bucket_ring), bucket->bucket_ring);
801    p_Setm(lm, bucket->bucket_ring);
802  }
803
804  p_ExpVectorSub(lm,p1, bucket->bucket_ring);
805  l1--;
806
807  kBucket_Minus_m_Mult_p(bucket, lm, a1, &l1, spNoether);
808
809  p_DeleteLm(&lm, bucket->bucket_ring);
810  if (reset_vec) p_SetCompP(a1, 0, bucket->bucket_ring);
811  kbTest(bucket);
812  return rn;
813}
814
815
Note: See TracBrowser for help on using the repository browser.