My Project  debian-1:4.1.2-p1+ds-2
Macros | Functions | Variables
kbuckets.cc File Reference
#include "misc/auxiliary.h"
#include "misc/options.h"
#include "polys/monomials/p_polys.h"
#include "coeffs/coeffs.h"
#include "coeffs/numbers.h"
#include "polys/monomials/ring.h"
#include "polys/kbuckets.h"
#include "polys/shiftop.h"

Go to the source code of this file.

Macros

#define MULTIPLY_BUCKET(B, I)
 

Functions

static int LOG4 (int v)
 Some internal stuff. More...
 
static unsigned int pLogLength (unsigned int l)
 
static unsigned int pLogLength (poly p)
 
BOOLEAN kbTest (kBucket_pt bucket)
 Tests. More...
 
kBucket_pt kBucketCreate (const ring bucket_ring)
 Creation/Destruction of buckets. More...
 
void kBucketDestroy (kBucket_pt *bucket_pt)
 
void kBucketDeleteAndDestroy (kBucket_pt *bucket_pt)
 
void kBucketInit (kBucket_pt bucket, poly lm, int length)
 
const poly kBucketGetLm (kBucket_pt bucket)
 
poly kBucketExtractLm (kBucket_pt bucket)
 
void kBucketClear (kBucket_pt bucket, poly *p, int *length)
 
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. More...
 
void kBucketAdjust (kBucket_pt bucket, int i)
 Bucket number i from bucket is out of length sync, resync. More...
 
void kBucket_Mult_n (kBucket_pt bucket, number n)
 Multiply Bucket by number ,i.e. Bpoly == n*Bpoly. More...
 
void kBucket_Add_q (kBucket_pt bucket, poly q, int *l)
 Add to Bucket a poly ,i.e. Bpoly == q+Bpoly. More...
 
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) More...
 
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) More...
 
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 monomial of append. More...
 
void p_TakeOutComp (poly *p, long comp, poly *q, int *lq, const ring r)
 
void kBucketTakeOutComp (kBucket_pt bucket, long comp, poly *r_p, int *l)
 
int ksCheckCoeff (number *a, number *b)
 
number kBucketPolyRed (kBucket_pt bucket, poly p1, int l1, poly spNoether)
 
void kBucketSimpleContent (kBucket_pt bucket)
 
poly kBucketExtractLmOfBucket (kBucket_pt bucket, int i)
 
int ksCheckCoeff (number *a, number *b, const coeffs r)
 

Variables

STATIC_VAR omBin kBucket_bin = omGetSpecBin(sizeof(kBucket))
 

Macro Definition Documentation

◆ MULTIPLY_BUCKET

#define MULTIPLY_BUCKET (   B,
 
)

Definition at line 43 of file kbuckets.cc.

Function Documentation

◆ kbTest()

BOOLEAN kbTest ( kBucket_pt  bucket)

Tests.

Definition at line 197 of file kbuckets.cc.

198 {
199  return TRUE;
200 }
#define TRUE
Definition: auxiliary.h:100

◆ kBucket_Add_q()

void kBucket_Add_q ( kBucket_pt  bucket,
poly  q,
int *  l 
)

Add to Bucket a poly ,i.e. Bpoly == q+Bpoly.

Add to Bucket a poly ,i.e. Bpoly == Bpoly + q.

Definition at line 654 of file kbuckets.cc.

655 {
656  if (q == NULL) return;
657  assume(*l <= 0 || pLength(q) == *l);
658 
659  int i, l1;
660  ring r = bucket->bucket_ring;
661 
662  if (*l <= 0)
663  {
664  l1 = pLength(q);
665  *l = l1;
666  }
667  else
668  l1 = *l;
669 
670  kBucketMergeLm(bucket);
671  kbTest(bucket);
672  i = pLogLength(l1);
673 
674  while (bucket->buckets[i] != NULL)
675  {
676  //MULTIPLY_BUCKET(bucket,i);
677  #ifdef USE_COEF_BUCKETS
678  if (bucket->coef[i]!=NULL)
679  {
680  q = p_Plus_mm_Mult_qq(q, bucket->coef[i], bucket->buckets[i],
681  l1, bucket->buckets_length[i], r);
682  p_Delete(&bucket->coef[i],r);
683  p_Delete(&bucket->buckets[i],r);
684  }
685  else
686  q = p_Add_q(q, bucket->buckets[i],
687  l1, bucket->buckets_length[i], r);
688  #else
689  q = p_Add_q(q, bucket->buckets[i],
690  l1, bucket->buckets_length[i], r);
691  #endif
692  bucket->buckets[i] = NULL;
693  bucket->buckets_length[i] = 0;
694  i = pLogLength(l1);
695  assume(i<= MAX_BUCKET);
696  assume(bucket->buckets_used<= MAX_BUCKET);
697  }
698 
699  kbTest(bucket);
700  bucket->buckets[i] = q;
701  bucket->buckets_length[i]=l1;
702  if (i >= bucket->buckets_used)
703  bucket->buckets_used = i;
704  else
705  kBucketAdjustBucketsUsed(bucket);
706  kbTest(bucket);
707 }
int l
Definition: cfEzgcd.cc:93
int i
Definition: cfEzgcd.cc:125
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:197
static unsigned int pLogLength(unsigned int l)
Definition: kbuckets.cc:71
ring bucket_ring
Definition: kbuckets.h:192
#define MAX_BUCKET
Bucket definition (should be no one elses business, though)
Definition: kbuckets.h:175
#define assume(x)
Definition: mod2.h:390
#define NULL
Definition: omList.c:12
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:895
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:860
static unsigned pLength(poly a)
Definition: p_polys.h:191
static poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq, const ring r)
Definition: p_polys.h:1122

◆ 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 monomial of append.

Definition at line 1004 of file kbuckets.cc.

1005 {
1006  if (q == NULL) return append;
1007  poly lm;
1008  loop
1009  {
1010  lm = kBucketGetLm(bucket);
1011  if (lm == NULL) return append;
1012  if (p_LmCmp(lm, q, bucket->bucket_ring) == 1)
1013  {
1014  lm = kBucketExtractLm(bucket);
1015  pNext(append) = lm;
1016  pIter(append);
1017  }
1018  else
1019  {
1020  return append;
1021  }
1022  }
1023 }
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:511
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:506
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1500
#define loop
Definition: structs.h:80

◆ 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)

Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m (TODO: rename into kBucket_Minus_mm_Mult_pp!?) assume (*l <= 0 || pLength(p) == *l)

Definition at line 716 of file kbuckets.cc.

718 {
719  assume(*l <= 0 || pLength(p) == *l);
720  int i, l1;
721  poly p1 = p;
722  ring r = bucket->bucket_ring;
723 
724  if (*l <= 0)
725  {
726  l1 = pLength(p1);
727  *l = l1;
728  }
729  else
730  l1 = *l;
731 
732  if (m == NULL || p == NULL) return;
733 
734 #ifndef HAVE_PSEUDO_BUCKETS
735  kBucketMergeLm(bucket);
736  kbTest(bucket);
737  i = pLogLength(l1);
738 
739 #if defined(HAVE_PLURAL)
740  if ((rField_is_Ring(r) && !(rField_is_Domain(r)))
741  ||(rIsPluralRing(r)))
742  {
743  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
744  p1=r->p_Procs->pp_mm_Mult(p,m,r);
745  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
746  l1=pLength(p1);
747  i = pLogLength(l1);
748  }
749  else
750 #endif
751  {
752  if ((i <= bucket->buckets_used) && (bucket->buckets[i] != NULL))
753  {
754  assume(pLength(bucket->buckets[i])==(unsigned)bucket->buckets_length[i]);
755 //#ifdef USE_COEF_BUCKETS
756 // if(bucket->coef[i]!=NULL)
757 // {
758 // poly mult=p_Mult_mm(bucket->coef[i],m,r);
759 // bucket->coef[i]=NULL;
760 // p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], mult, p1,
761 // bucket->buckets_length[i], l1,
762 // spNoether, r);
763 // }
764 // else
765 //#endif
766  MULTIPLY_BUCKET(bucket,i);
767  p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], m, p1,
768  bucket->buckets_length[i], l1,
769  spNoether, r);
770  l1 = bucket->buckets_length[i];
771  bucket->buckets[i] = NULL;
772  bucket->buckets_length[i] = 0;
773  i = pLogLength(l1);
774  }
775  else
776  {
777  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
778  if (spNoether != NULL)
779  {
780  l1 = -1;
781  p1 = r->p_Procs->pp_Mult_mm_Noether(p1, m, spNoether, l1, r);
782  i = pLogLength(l1);
783  }
784  else
785  {
786  p1 = r->p_Procs->pp_mm_Mult(p1, m, r);
787  }
788  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
789  }
790  }
791 
792  while (bucket->buckets[i] != NULL)
793  {
794  //kbTest(bucket);
795  MULTIPLY_BUCKET(bucket,i);
796  p1 = p_Add_q(p1, bucket->buckets[i],
797  l1, bucket->buckets_length[i], r);
798  bucket->buckets[i] = NULL;
799  bucket->buckets_length[i] = 0;
800  i = pLogLength(l1);
801  }
802 
803  bucket->buckets[i] = p1;
804  bucket->buckets_length[i]=l1;
805  if (i >= bucket->buckets_used)
806  bucket->buckets_used = i;
807  else
808  kBucketAdjustBucketsUsed(bucket);
809 #else // HAVE_PSEUDO_BUCKETS
810  bucket->p = p_Minus_mm_Mult_qq(bucket->p, m, p,
811  bucket->l, l1,
812  spNoether, r);
813 #endif
814 }
int m
Definition: cfEzgcd.cc:121
int p
Definition: cfModGcd.cc:4019
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:557
#define MULTIPLY_BUCKET(B, I)
Definition: kbuckets.cc:43
int l
Definition: kbuckets.h:183
poly p
Definition: kbuckets.h:182
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
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:1009
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:479
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:397
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:482

◆ kBucket_Mult_n()

void kBucket_Mult_n ( kBucket_pt  bucket,
number  n 
)

Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.

Definition at line 598 of file kbuckets.cc.

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  if (rField_is_Ring(r) && !(rField_is_Domain(r)))
636  {
637  bucket->buckets_length[i] = pLength(bucket->buckets[i]);
638  kBucketAdjust(bucket, i);
639  }
640 #endif
641  }
642  }
643  kbTest(bucket);
644 #else
645  bucket->p = __p_Mult_nn(bucket->p, n, bucket->bucket_ring);
646 #endif
647 }
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:451
void kBucketAdjust(kBucket_pt bucket, int i)
Bucket number i from bucket is out of length sync, resync.
Definition: kbuckets.cc:565
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1455
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:930

◆ 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 at line 821 of file kbuckets.cc.

822 {
823  assume((!rIsPluralRing(bucket->bucket_ring))||p_IsConstant(m, bucket->bucket_ring));
824  assume(l <= 0 || pLength(p) == (unsigned)l);
825  int i, l1;
826  poly p1 = p;
827  ring r = bucket->bucket_ring;
828 
829  if (m == NULL || p == NULL) return;
830 
831  if (l <= 0)
832  {
833  l1 = pLength(p1);
834  l = l1;
835  }
836  else
837  l1 = l;
838 
839  kBucketMergeLm(bucket);
840  kbTest(bucket);
841  i = pLogLength(l1);
842  #ifdef USE_COEF_BUCKETS
843  number n=n_Init(1,r->cf);
844  #endif
845  if (i <= bucket->buckets_used && bucket->buckets[i] != NULL)
846  {
847  //if (FALSE){
848  #ifdef USE_COEF_BUCKETS
849  if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
850  {
851  number orig_coef=p_GetCoeff(bucket->coef[i],r);
852  //we take ownership:
853  p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
854  number add_coef=n_Copy(p_GetCoeff(m,r),r);
855  number gcd=n_Gcd(add_coef, orig_coef,r);
856 
857  if (!(n_IsOne(gcd,r)))
858  {
859  number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
860  number add_coef2=n_ExactDiv(add_coef, gcd,r);
861  n_Delete(&orig_coef,r);
862  n_Delete(&add_coef,r);
863  orig_coef=orig_coef2;
864  add_coef=add_coef2;
865 
866  //p_Mult_nn(bucket->buckets[i], orig_coef,r);
867  n_Delete(&n,r);
868  n=gcd;
869  }
870 
871  //assume(n_IsOne(n,r));
872  number backup=p_GetCoeff(m,r);
873 
874  p_SetCoeff0(m,add_coef,r);
875  bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
876 
877  n_Delete(&orig_coef,r);
878  p_Delete(&bucket->coef[i],r);
879 
880  p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
881  bucket->buckets_length[i], l1, r);
882  l1=bucket->buckets_length[i];
883  bucket->buckets[i]=NULL;
884  bucket->buckets_length[i] = 0;
885  i = pLogLength(l1);
886  assume(l1==pLength(p1));
887 
888  p_SetCoeff(m,backup,r); //deletes add_coef
889  }
890  else
891  #endif
892  {
893  MULTIPLY_BUCKET(bucket,i);
894  p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
895  bucket->buckets_length[i], l1, r);
896  l1 = bucket->buckets_length[i];
897  bucket->buckets[i] = NULL;
898  bucket->buckets_length[i] = 0;
899  i = pLogLength(l1);
900  }
901  }
902  else
903  {
904  #ifdef USE_COEF_BUCKETS
905  number swap_n=p_GetCoeff(m,r);
906 
907  assume(n_IsOne(n,r));
908  p_SetCoeff0(m,n,r);
909  n=swap_n;
910  //p_SetCoeff0(n, swap_n, r);
911  //p_GetCoeff0(n, swap_n,r);
912  #endif
913  p1 = r->p_Procs->pp_Mult_mm(p1, m, r);
914  #ifdef USE_COEF_BUCKETS
915  //m may not be changed
916  p_SetCoeff(m,n_Copy(n,r),r);
917  #endif
918  }
919 
920  while ((bucket->buckets[i] != NULL) && (p1!=NULL))
921  {
922  assume(i!=0);
923  #ifdef USE_COEF_BUCKETS
924  if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
925  {
926  number orig_coef=p_GetCoeff(bucket->coef[i],r);
927  //we take ownership:
928  p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
929  number add_coef=n_Copy(n,r);
930  number gcd=n_Gcd(add_coef, orig_coef,r);
931 
932  if (!(n_IsOne(gcd,r)))
933  {
934  number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
935  number add_coef2=n_ExactDiv(add_coef, gcd,r);
936  n_Delete(&orig_coef,r);
937  n_Delete(&n,r);
938  n_Delete(&add_coef,r);
939  orig_coef=orig_coef2;
940  add_coef=add_coef2;
941  //p_Mult_nn(bucket->buckets[i], orig_coef,r);
942  n=gcd;
943  }
944  //assume(n_IsOne(n,r));
945  bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
946  p1=__p_Mult_nn(p1,add_coef,r);
947 
948  p1 = p_Add_q(p1, bucket->buckets[i],r);
949  l1=pLength(p1);
950 
951  bucket->buckets[i]=NULL;
952  n_Delete(&orig_coef,r);
953  p_Delete(&bucket->coef[i],r);
954  //l1=bucket->buckets_length[i];
955  assume(l1==pLength(p1));
956  }
957  else
958  #endif
959  {
960  //don't do that, pull out gcd
961  #ifdef USE_COEF_BUCKETS
962  if(!(n_IsOne(n,r)))
963  {
964  p1=__p_Mult_nn(p1, n, r);
965  n_Delete(&n,r);
966  n=n_Init(1,r);
967  }
968  #endif
969  MULTIPLY_BUCKET(bucket,i);
970  p1 = p_Add_q(p1, bucket->buckets[i],
971  l1, bucket->buckets_length[i], r);
972  bucket->buckets[i] = NULL;
973  bucket->buckets_length[i] = 0;
974  }
975  i = pLogLength(l1);
976  }
977 
978  bucket->buckets[i] = p1;
979 #ifdef USE_COEF_BUCKETS
980  assume(bucket->coef[i]==NULL);
981 
982  if (!(n_IsOne(n,r)))
983  {
984  bucket->coef[i]=p_NSet(n,r);
985  }
986  else
987  {
988  bucket->coef[i]=NULL;
989  n_Delete(&n,r);
990  }
991 
992  if (p1==NULL)
993  p_Delete(&bucket->coef[i],r);
994 #endif
995  bucket->buckets_length[i]=l1;
996  if (i > bucket->buckets_used)
997  bucket->buckets_used = i;
998  else
999  kBucketAdjustBucketsUsed(bucket);
1000 
1001  kbTest(bucket);
1002 }
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:686
static FORCE_INLINE number n_ExactDiv(number a, number b, const coeffs r)
assume that there is a canonical subring in cf and we know that division is possible for these a and ...
Definition: coeffs.h:622
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
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:538
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:468
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:60
#define p_GetCoeff(p, r)
Definition: monomials.h:50
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:411
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1931
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ kBucketAdjust()

void kBucketAdjust ( kBucket_pt  bucket,
int  i 
)

Bucket number i from bucket is out of length sync, resync.

Definition at line 565 of file kbuckets.cc.

565  {
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 }

◆ kBucketClear()

void kBucketClear ( kBucket_pt  bucket,
poly *  p,
int *  length 
)

Definition at line 521 of file kbuckets.cc.

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 }
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263

◆ kBucketCreate()

kBucket_pt kBucketCreate ( const ring  bucket_ring)

Creation/Destruction of buckets.

Definition at line 209 of file kbuckets.cc.

210 {
211  assume(bucket_ring != NULL);
213  bucket->bucket_ring = bucket_ring;
214  return bucket;
215 }
STATIC_VAR omBin kBucket_bin
Definition: kbuckets.cc:45
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
kBucket * kBucket_pt
Definition: ring.h:24

◆ kBucketDeleteAndDestroy()

void kBucketDeleteAndDestroy ( kBucket_pt bucket_pt)

Definition at line 223 of file kbuckets.cc.

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 }
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259

◆ kBucketDestroy()

void kBucketDestroy ( kBucket_pt bucket_pt)

Definition at line 216 of file kbuckets.cc.

217 {
218  omFreeBin(*bucket_pt, kBucket_bin);
219  *bucket_pt = NULL;
220 }

◆ kBucketExtractLm()

poly kBucketExtractLm ( kBucket_pt  bucket)
inline

Definition at line 511 of file kbuckets.cc.

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 }

◆ kBucketExtractLmOfBucket()

poly kBucketExtractLmOfBucket ( kBucket_pt  bucket,
int  i 
)

Definition at line 1375 of file kbuckets.cc.

1376 {
1377  assume(bucket->buckets[i]!=NULL);
1378 
1379  poly p=bucket->buckets[i];
1380  bucket->buckets_length[i]--;
1381 #ifdef USE_COEF_BUCKETS
1382  ring r=bucket->bucket_ring;
1383  if (bucket->coef[i]!=NULL)
1384  {
1385  poly next=pNext(p);
1386  if (next==NULL)
1387  {
1388  MULTIPLY_BUCKET(bucket,i);
1389  p=bucket->buckets[i];
1390  bucket->buckets[i]=NULL;
1391  return p;
1392  }
1393  else
1394  {
1395  bucket->buckets[i]=next;
1396  number c=p_GetCoeff(bucket->coef[i],r);
1397  pNext(p)=NULL;
1398  p=__p_Mult_nn(p,c,r);
1399  assume(p!=NULL);
1400  return p;
1401  }
1402  }
1403  else
1404 #endif
1405  {
1406  bucket->buckets[i]=pNext(bucket->buckets[i]);
1407  pNext(p)=NULL;
1408  assume(p!=NULL);
1409  return p;
1410  }
1411 }
ListNode * next
Definition: janet.h:31

◆ kBucketGetLm()

const poly kBucketGetLm ( kBucket_pt  bucket)

Definition at line 506 of file kbuckets.cc.

507 {
508  return bucket->p;
509 }

◆ kBucketInit()

void kBucketInit ( kBucket_pt  bucket,
poly  lm,
int  length 
)

Definition at line 493 of file kbuckets.cc.

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 }

◆ kBucketPolyRed()

number kBucketPolyRed ( kBucket_pt  bucket,
poly  p1,
int  l1,
poly  spNoether 
)

Definition at line 1079 of file kbuckets.cc.

1082 {
1083  ring r=bucket->bucket_ring;
1084  assume((!rIsPluralRing(r))||p_LmEqual(p1,kBucketGetLm(bucket), r));
1085  assume(p1 != NULL &&
1086  p_DivisibleBy(p1, kBucketGetLm(bucket), r));
1087  assume(pLength(p1) == (unsigned) l1);
1088 
1089  poly a1 = pNext(p1), lm = kBucketExtractLm(bucket);
1090  BOOLEAN reset_vec=FALSE;
1091  number rn;
1092 
1093  /* we shall reduce bucket=bn*lm+... by p1=an*t+a1 where t=lm(p1)
1094  and an,bn shall be defined further down only if lc(p1)!=1
1095  we already know: an|bn and t|lm */
1096  if(a1==NULL)
1097  {
1098  p_LmDelete(&lm, r);
1099  return n_Init(1,r->cf);
1100  }
1101 
1102  if (! n_IsOne(pGetCoeff(p1),r->cf))
1103  {
1104  number an = pGetCoeff(p1), bn = pGetCoeff(lm);
1105 //StringSetS("##### an = "); nWrite(an); PrintS(StringEndS("\n")); // NOTE/TODO: use StringAppendS("\n"); omFree(s);
1106 //StringSetS("##### bn = "); nWrite(bn); PrintS(StringEndS("\n")); // NOTE/TODO: use StringAppendS("\n"); omFree(s);
1107  /* ksCheckCoeff: divide out gcd from an and bn: */
1108  int ct = ksCheckCoeff(&an, &bn,r->cf);
1109  /* the previous command returns ct=0 or ct=2 iff an!=1
1110  note: an is now 1 or -1 */
1111 
1112  /* setup factor for p1 which cancels leading terms */
1113  p_SetCoeff(lm, bn, r);
1114  if ((ct == 0) || (ct == 2))
1115  {
1116  /* next line used to be here before but is WRONG:
1117  kBucket_Mult_n(bucket, an);
1118  its use would result in a wrong sign for the tail of bucket
1119  in the reduction */
1120 
1121  /* correct factor for cancelation by changing sign if an=-1 */
1122  if (rField_is_Ring(r))
1123  lm = __p_Mult_nn(lm, an, r);
1124  else
1125  kBucket_Mult_n(bucket, an);
1126  }
1127  rn = an;
1128  }
1129  else
1130  {
1131  rn = n_Init(1,r->cf);
1132  }
1133 
1134  if (p_GetComp(p1, r) != p_GetComp(lm, r))
1135  {
1136  p_SetCompP(a1, p_GetComp(lm, r), r);
1137  reset_vec = TRUE;
1138  p_SetComp(lm, p_GetComp(p1, r), r);
1139  p_Setm(lm, r);
1140  }
1141 
1142  p_ExpVectorSub(lm, p1, r);
1143  l1--;
1144 
1145  assume((unsigned)l1==pLength(a1));
1146 
1147 #ifdef HAVE_SHIFTBBA
1148  poly lmRight;
1149  if (r->isLPring) {
1150  int firstBlock = p_mFirstVblock(p1, r);
1151  k_SplitFrame(lm, lmRight, firstBlock, r);
1152  }
1153 #endif
1154 #if 0
1155  BOOLEAN backuped=FALSE;
1156  number coef;
1157  //@Viktor, don't ignore coefficients on monomials
1158  if(l1==1) {
1159 
1160  //if (rField_is_Q(r)) {
1161  //avoid this for function fields, as gcds are expensive at the moment
1162 
1163 
1164  coef=p_GetCoeff(a1,r);
1165  lm=p_Mult_nn(lm, coef, r);
1166  p_SetCoeff0(a1, n_Init(1,r), r);
1167  backuped=TRUE;
1168  //WARNING: not thread_safe
1169  //deletes coef as side effect
1170  //}
1171  }
1172 #endif
1173 
1174 #ifdef HAVE_SHIFTBBA
1175  if (r->isLPring)
1176  {
1177  kBucket_Minus_m_Mult_p(bucket, lm, r->p_Procs->pp_Mult_mm(a1, lmRight, r), &l1, spNoether);
1178  }
1179  else
1180 #endif
1181  {
1182  kBucket_Minus_m_Mult_p(bucket, lm, a1, &l1, spNoether);
1183  }
1184 
1185 #if 0
1186  if (backuped)
1187  p_SetCoeff0(a1,coef,r);
1188 #endif
1189 
1190  p_LmDelete(&lm, r);
1191 #ifdef HAVE_SHIFTBBA
1192  if (r->isLPring)
1193  {
1194  p_LmDelete(&lmRight, r);
1195  }
1196 #endif
1197  if (reset_vec) p_SetCompP(a1, 0, r);
1198  kbTest(bucket);
1199  return rn;
1200 }
int BOOLEAN
Definition: auxiliary.h:87
#define FALSE
Definition: auxiliary.h:96
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:716
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition: kbuckets.cc:598
int ksCheckCoeff(number *a, number *b)
#define p_GetComp(p, r)
Definition: monomials.h:64
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:710
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1651
static void p_SetCompP(poly p, int i, ring r)
Definition: p_polys.h:253
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:246
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition: p_polys.h:1379
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1832
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:917
int p_mFirstVblock(poly p, const ring ri)
Definition: shiftop.cc:473
void k_SplitFrame(poly &m1, poly &m2, int at, const ring r)
Definition: shiftop.cc:593

◆ 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 at line 535 of file kbuckets.cc.

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 }
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...

◆ kBucketSimpleContent()

void kBucketSimpleContent ( kBucket_pt  bucket)

Definition at line 1203 of file kbuckets.cc.

1204 {
1205  if (bucket->buckets[0]==NULL) return;
1206 
1207  ring r=bucket->bucket_ring;
1208  if (rField_is_Ring(r)) return;
1209 
1210  coeffs cf=r->cf;
1211  if (cf->cfSubringGcd==ndGcd) /* trivial gcd*/ return;
1212 
1213  number nn=pGetCoeff(bucket->buckets[0]);
1214  //if ((bucket->buckets_used==0)
1215  //&&(!n_IsOne(nn,cf)))
1216  //{
1217  // if (TEST_OPT_PROT) PrintS("@");
1218  // p_SetCoeff(bucket->buckets[0],n_Init(1,cf),r);
1219  // return;
1220  //}
1221 
1222  if (n_Size(nn,cf)<2) return;
1223 
1224  //kBucketAdjustBucketsUsed(bucket);
1225  number coef=n_Copy(nn,cf);
1226  // find an initial guess of a gcd
1227  for (int i=1; i<=bucket->buckets_used;i++)
1228  {
1229  if (bucket->buckets[i]!=NULL)
1230  {
1231  number t=p_InitContent(bucket->buckets[i],r);
1232  if (n_Size(t,cf)<2)
1233  {
1234  n_Delete(&t,cf);
1235  n_Delete(&coef,cf);
1236  return;
1237  }
1238  number t2=n_SubringGcd(coef,t,cf);
1239  n_Delete(&t,cf);
1240  n_Delete(&coef,cf);
1241  coef=t2;
1242  if (n_Size(coef,cf)<2) { n_Delete(&coef,cf);return;}
1243  }
1244  }
1245  // find the gcd
1246  for (int i=0; i<=bucket->buckets_used;i++)
1247  {
1248  if (bucket->buckets[i]!=NULL)
1249  {
1250  poly p=bucket->buckets[i];
1251  while(p!=NULL)
1252  {
1253  number t=n_SubringGcd(coef,pGetCoeff(p),cf);
1254  if (n_Size(t,cf)<2)
1255  {
1256  n_Delete(&t,cf);
1257  n_Delete(&coef,cf);
1258  return;
1259  }
1260  pIter(p);
1261  }
1262  }
1263  }
1264  // divided by the gcd
1265  if (TEST_OPT_PROT) PrintS("@");
1266  for (int i=bucket->buckets_used;i>=0;i--)
1267  {
1268  if (bucket->buckets[i]!=NULL)
1269  {
1270  poly p=bucket->buckets[i];
1271  while(p!=NULL)
1272  {
1273  number d = n_ExactDiv(pGetCoeff(p),coef,cf);
1274  p_SetCoeff(p,d,r);
1275  pIter(p);
1276  }
1277  }
1278  }
1279  n_Delete(&coef,cf);
1280 }
CanonicalForm cf
Definition: cfModGcd.cc:4024
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:570
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:688
The main handler for Singular numbers which are suitable for Singular polynomials.
number ndGcd(number, number, const coeffs r)
Definition: numbers.cc:161
#define TEST_OPT_PROT
Definition: options.h:101
number p_InitContent(poly ph, const ring r)
Definition: p_polys.cc:2581
void PrintS(const char *s)
Definition: reporter.cc:284

◆ kBucketTakeOutComp()

void kBucketTakeOutComp ( kBucket_pt  bucket,
long  comp,
poly *  r_p,
int *  l 
)

Definition at line 1038 of file kbuckets.cc.

1041 {
1042  poly p = NULL, q;
1043  int i, lp = 0, lq;
1044 
1045 #ifndef HAVE_PSEUDO_BUCKETS
1046  kBucketMergeLm(bucket);
1047  for (i=1; i<=bucket->buckets_used; i++)
1048  {
1049  if (bucket->buckets[i] != NULL)
1050  {
1051  MULTIPLY_BUCKET(bucket,i);
1052  p_TakeOutComp(&(bucket->buckets[i]), comp, &q, &lq, bucket->bucket_ring);
1053  if (q != NULL)
1054  {
1055  assume(pLength(q) == (unsigned)lq);
1056  bucket->buckets_length[i] -= lq;
1057  assume(pLength(bucket->buckets[i]) == (unsigned)bucket->buckets_length[i]);
1058  p = p_Add_q(p, q, lp, lq, bucket->bucket_ring);
1059  }
1060  }
1061  }
1062  kBucketAdjustBucketsUsed(bucket);
1063 #else
1064  p_TakeOutComp(&(bucket->p), comp, &p, &lp,bucket->bucket_ring);
1065  (bucket->l) -= lp;
1066 #endif
1067  *r_p = p;
1068  *l = lp;
1069 
1070  kbTest(bucket);
1071 }
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r)
Definition: p_polys.cc:3455
Definition: lq.h:40

◆ ksCheckCoeff() [1/2]

int ksCheckCoeff ( number *  a,
number *  b 
)

◆ ksCheckCoeff() [2/2]

int ksCheckCoeff ( number *  a,
number *  b,
const coeffs  r 
)

Definition at line 1424 of file kbuckets.cc.

1425 {
1426  int c = 0;
1427  number an = *a, bn = *b;
1428  n_Test(an,r);
1429  n_Test(bn,r);
1430 
1431  number cn = n_SubringGcd(an, bn, r);
1432 
1433  if(n_IsOne(cn, r))
1434  {
1435  an = n_Copy(an, r);
1436  bn = n_Copy(bn, r);
1437  }
1438  else
1439  {
1440  an = n_ExactDiv(an, cn, r); n_Normalize(an,r);
1441  bn = n_ExactDiv(bn, cn, r); n_Normalize(bn,r);
1442  }
1443  n_Delete(&cn, r);
1444  if (n_IsOne(an, r))
1445  {
1446  c = 1;
1447  }
1448  if (n_IsOne(bn, r))
1449  {
1450  c += 2;
1451  }
1452  *a = an;
1453  *b = bn;
1454  return c;
1455 }
CanonicalForm b
Definition: cfModGcd.cc:4044
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition: coeffs.h:578

◆ LOG4()

static int LOG4 ( int  v)
inlinestatic

Some internal stuff.

Definition at line 56 of file kbuckets.cc.

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 }
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37

◆ p_TakeOutComp()

void p_TakeOutComp ( poly *  p,
long  comp,
poly *  q,
int *  lq,
const ring  r 
)

Definition at line 3455 of file p_polys.cc.

3456 {
3457  spolyrec pp, qq;
3458  poly p, q, p_prev;
3459  int l = 0;
3460 
3461 #ifndef SING_NDEBUG
3462  int lp = pLength(*r_p);
3463 #endif
3464 
3465  pNext(&pp) = *r_p;
3466  p = *r_p;
3467  p_prev = &pp;
3468  q = &qq;
3469 
3470  while(p != NULL)
3471  {
3472  while (__p_GetComp(p,r) == comp)
3473  {
3474  pNext(q) = p;
3475  pIter(q);
3476  p_SetComp(p, 0,r);
3477  p_SetmComp(p,r);
3478  pIter(p);
3479  l++;
3480  if (p == NULL)
3481  {
3482  pNext(p_prev) = NULL;
3483  goto Finish;
3484  }
3485  }
3486  pNext(p_prev) = p;
3487  p_prev = p;
3488  pIter(p);
3489  }
3490 
3491  Finish:
3492  pNext(q) = NULL;
3493  *r_p = pNext(&pp);
3494  *r_q = pNext(&qq);
3495  *lq = l;
3496 #ifndef SING_NDEBUG
3497  assume(pLength(*r_p) + pLength(*r_q) == lp);
3498 #endif
3499  p_Test(*r_p,r);
3500  p_Test(*r_q,r);
3501 }
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
#define __p_GetComp(p, r)
Definition: monomials.h:63
#define p_SetmComp
Definition: p_polys.h:243
#define p_Test(p, r)
Definition: p_polys.h:162

◆ pLogLength() [1/2]

static unsigned int pLogLength ( poly  p)
inlinestatic

Definition at line 86 of file kbuckets.cc.

87 {
88  return pLogLength((unsigned int) pLength(p));
89 }

◆ pLogLength() [2/2]

static unsigned int pLogLength ( unsigned int  l)
inlinestatic

Definition at line 71 of file kbuckets.cc.

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 }
static int SI_LOG2(int v)
Definition: auxiliary.h:121
static int LOG4(int v)
Some internal stuff.
Definition: kbuckets.cc:56

Variable Documentation

◆ kBucket_bin

STATIC_VAR omBin kBucket_bin = omGetSpecBin(sizeof(kBucket))

Definition at line 45 of file kbuckets.cc.