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)
number	kBucketPolyRed (kBucket_pt bucket, poly p1, int l1, poly spNoether)
void	kBucketPolyRedNF (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,
			I
	)

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.

{
  return TRUE;
}

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 660 of file kbuckets.cc.

{
  if (q == NULL) return;
  assume(*l <= 0 || pLength(q) == *l);
 
  int i, l1;
  ring r = bucket->bucket_ring;
 
  if (*l <= 0)
  {
    l1 = pLength(q);
    *l = l1;
  }
  else
    l1 = *l;
 
  kBucketMergeLm(bucket);
  kbTest(bucket);
  i = pLogLength(l1);
 
  while (bucket->buckets[i] != NULL)
  {
    //MULTIPLY_BUCKET(bucket,i);
  #ifdef USE_COEF_BUCKETS
    if (bucket->coef[i]!=NULL)
    {
      q = p_Plus_mm_Mult_qq(q, bucket->coef[i], bucket->buckets[i],
                 l1, bucket->buckets_length[i], r);
      p_Delete(&bucket->coef[i],r);
      p_Delete(&bucket->buckets[i],r);
    }
    else
    q = p_Add_q(q, bucket->buckets[i],
                 l1, bucket->buckets_length[i], r);
  #else
    q = p_Add_q(q, bucket->buckets[i],
                 l1, bucket->buckets_length[i], r);
  #endif
    bucket->buckets[i] = NULL;
    bucket->buckets_length[i] = 0;
    i = pLogLength(l1);
    assume(i<= MAX_BUCKET);
    assume(bucket->buckets_used<= MAX_BUCKET);
  }
 
  kbTest(bucket);
  bucket->buckets[i] = q;
  bucket->buckets_length[i]=l1;
  if (i >= bucket->buckets_used)
    bucket->buckets_used = i;
  else
    kBucketAdjustBucketsUsed(bucket);
  kbTest(bucket);
}

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 998 of file kbuckets.cc.

{
  if (q == NULL) return append;
  poly lm;
  loop
  {
    lm = kBucketGetLm(bucket);
    if (lm == NULL) return append;
    if (p_LmCmp(lm, q, bucket->bucket_ring) == 1)
    {
      lm = kBucketExtractLm(bucket);
      pNext(append) = lm;
      pIter(append);
    }
    else
    {
      return append;
    }
  }
}

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 722 of file kbuckets.cc.

{
  assume(*l <= 0 || pLength(p) == *l);
  int i, l1;
  poly p1 = p;
  ring r = bucket->bucket_ring;
 
  if (*l <= 0)
  {
    l1 = pLength(p1);
    *l = l1;
  }
  else
    l1 = *l;
 
  if (m == NULL || p == NULL) return;
 
#ifndef HAVE_PSEUDO_BUCKETS
  kBucketMergeLm(bucket);
  kbTest(bucket);
  i = pLogLength(l1);
 
  {
    if ((i <= bucket->buckets_used) && (bucket->buckets[i] != NULL))
    {
      assume(pLength(bucket->buckets[i])==(unsigned)bucket->buckets_length[i]);
//#ifdef USE_COEF_BUCKETS
//     if(bucket->coef[i]!=NULL)
//     {
//       poly mult=p_Mult_mm(bucket->coef[i],m,r);
//       bucket->coef[i]=NULL;
//       p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], mult, p1,
//                               bucket->buckets_length[i], l1,
//                             spNoether, r);
//     }
//     else
//#endif
      MULTIPLY_BUCKET(bucket,i);
      p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], m, p1,
                            bucket->buckets_length[i], l1,
                            spNoether, r);
      l1 = bucket->buckets_length[i];
      bucket->buckets[i] = NULL;
      bucket->buckets_length[i] = 0;
      i = pLogLength(l1);
    }
    else
    {
      pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
      if (spNoether != NULL)
      {
        l1 = -1;
        p1 = r->p_Procs->pp_Mult_mm_Noether(p1, m, spNoether, l1, r);
        i = pLogLength(l1);
      }
      else
      {
        p1 = r->p_Procs->pp_mm_Mult(p1, m, r);
      }
      pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
    }
  }
 
  while (bucket->buckets[i] != NULL)
  {
    //kbTest(bucket);
    MULTIPLY_BUCKET(bucket,i);
    p1 = p_Add_q(p1, bucket->buckets[i],
                 l1, bucket->buckets_length[i], r);
    bucket->buckets[i] = NULL;
    bucket->buckets_length[i] = 0;
    i = pLogLength(l1);
  }
 
  bucket->buckets[i] = p1;
  bucket->buckets_length[i]=l1;
  if (i >= bucket->buckets_used)
    bucket->buckets_used = i;
  else
    kBucketAdjustBucketsUsed(bucket);
#else // HAVE_PSEUDO_BUCKETS
  bucket->p = p_Minus_mm_Mult_qq(bucket->p, m,  p,
                               bucket->l, l1,
                               spNoether, r);
#endif
}

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.

{
#ifndef HAVE_PSEUDO_BUCKETS
  kbTest(bucket);
  ring r=bucket->bucket_ring;
  int i;
 
  for (i=0; i<= bucket->buckets_used; i++)
  {
    if (bucket->buckets[i] != NULL)
    {
#ifdef USE_COEF_BUCKETS
      if (i<coef_start)
        bucket->buckets[i] = __p_Mult_nn(bucket->buckets[i], n, r);
        /* Frank Seelisch on March 11, 2010:
           This looks a bit strange: The following "if" is indented
           like the previous line of code. But coded as it is,
           it should actually be two spaces less indented.
           Question: Should the following "if" also only be
           performed when "(i<coef_start)" is true?
           For the time being, I leave it as it is. */
        if (rField_is_Ring(r) && !(rField_is_Domain(r)))
        {
          bucket->buckets_length[i] = pLength(bucket->buckets[i]);
          kBucketAdjust(bucket, i);
        }
      else
      if (bucket->coef[i]!=NULL)
      {
        bucket->coef[i] = __p_Mult_nn(bucket->coef[i],n,r);
      }
      else
      {
        bucket->coef[i] = p_NSet(n_Copy(n,r),r);
      }
#else
      bucket->buckets[i] = __p_Mult_nn(bucket->buckets[i], n, r);
#endif
    }
  }
  if (rField_is_Ring(r) && !(rField_is_Domain(r)))
  {
    for (i=0; i<= bucket->buckets_used; i++)
    {
      if (bucket->buckets[i] != NULL)
      {
        bucket->buckets_length[i] = pLength(bucket->buckets[i]);
        kBucketAdjust(bucket, i);
      }
    }
  }
  kbTest(bucket);
#else
  bucket->p = __p_Mult_nn(bucket->p, n, bucket->bucket_ring);
#endif
}

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 815 of file kbuckets.cc.

{
    assume((!rIsPluralRing(bucket->bucket_ring))||p_IsConstant(m, bucket->bucket_ring));
  assume(l <= 0 || pLength(p) == (unsigned)l);
  int i, l1;
  poly p1 = p;
  ring r = bucket->bucket_ring;
 
  if (m == NULL || p == NULL) return;
 
  if (l <= 0)
  {
    l1 = pLength(p1);
    l = l1;
  }
  else
    l1 = l;
 
  kBucketMergeLm(bucket);
  kbTest(bucket);
  i = pLogLength(l1);
  #ifdef USE_COEF_BUCKETS
  number n=n_Init(1,r->cf);
  #endif
  if (i <= bucket->buckets_used && bucket->buckets[i] != NULL)
  {
    //if (FALSE){
    #ifdef USE_COEF_BUCKETS
    if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
    {
      number orig_coef=p_GetCoeff(bucket->coef[i],r);
      //we take ownership:
      p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
      number add_coef=n_Copy(p_GetCoeff(m,r),r);
      number gcd=n_Gcd(add_coef, orig_coef,r);
 
      if (!(n_IsOne(gcd,r)))
      {
        number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
        number add_coef2=n_ExactDiv(add_coef, gcd,r);
        n_Delete(&orig_coef,r);
        n_Delete(&add_coef,r);
        orig_coef=orig_coef2;
        add_coef=add_coef2;
 
        //p_Mult_nn(bucket->buckets[i], orig_coef,r);
        n_Delete(&n,r);
        n=gcd;
      }
 
      //assume(n_IsOne(n,r));
      number backup=p_GetCoeff(m,r);
 
      p_SetCoeff0(m,add_coef,r);
      bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
 
      n_Delete(&orig_coef,r);
      p_Delete(&bucket->coef[i],r);
 
      p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
                           bucket->buckets_length[i], l1, r);
      l1=bucket->buckets_length[i];
      bucket->buckets[i]=NULL;
      bucket->buckets_length[i] = 0;
      i = pLogLength(l1);
      assume(l1==pLength(p1));
 
      p_SetCoeff(m,backup,r); //deletes add_coef
    }
    else
    #endif
    {
      MULTIPLY_BUCKET(bucket,i);
      p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
                           bucket->buckets_length[i], l1, r);
      l1 = bucket->buckets_length[i];
      bucket->buckets[i] = NULL;
      bucket->buckets_length[i] = 0;
      i = pLogLength(l1);
    }
  }
  else
  {
    #ifdef USE_COEF_BUCKETS
    number swap_n=p_GetCoeff(m,r);
 
    assume(n_IsOne(n,r));
    p_SetCoeff0(m,n,r);
    n=swap_n;
    //p_SetCoeff0(n, swap_n, r);
    //p_GetCoeff0(n, swap_n,r);
    #endif
    p1 = r->p_Procs->pp_Mult_mm(p1, m, r);
    #ifdef USE_COEF_BUCKETS
    //m may not be changed
    p_SetCoeff(m,n_Copy(n,r),r);
    #endif
  }
 
  while ((bucket->buckets[i] != NULL) && (p1!=NULL))
  {
    assume(i!=0);
    #ifdef USE_COEF_BUCKETS
    if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
    {
      number orig_coef=p_GetCoeff(bucket->coef[i],r);
      //we take ownership:
      p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
      number add_coef=n_Copy(n,r);
      number gcd=n_Gcd(add_coef, orig_coef,r);
 
      if (!(n_IsOne(gcd,r)))
      {
        number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
        number add_coef2=n_ExactDiv(add_coef, gcd,r);
        n_Delete(&orig_coef,r);
        n_Delete(&n,r);
        n_Delete(&add_coef,r);
        orig_coef=orig_coef2;
        add_coef=add_coef2;
        //p_Mult_nn(bucket->buckets[i], orig_coef,r);
        n=gcd;
      }
      //assume(n_IsOne(n,r));
      bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
      p1=__p_Mult_nn(p1,add_coef,r);
 
      p1 = p_Add_q(p1, bucket->buckets[i],r);
      l1=pLength(p1);
 
      bucket->buckets[i]=NULL;
      n_Delete(&orig_coef,r);
      p_Delete(&bucket->coef[i],r);
      //l1=bucket->buckets_length[i];
      assume(l1==pLength(p1));
    }
    else
    #endif
    {
      //don't do that, pull out gcd
      #ifdef USE_COEF_BUCKETS
      if(!(n_IsOne(n,r)))
      {
        p1=__p_Mult_nn(p1, n, r);
        n_Delete(&n,r);
        n=n_Init(1,r);
      }
      #endif
      MULTIPLY_BUCKET(bucket,i);
      p1 = p_Add_q(p1, bucket->buckets[i],
                 l1, bucket->buckets_length[i], r);
      bucket->buckets[i] = NULL;
      bucket->buckets_length[i] = 0;
    }
    i = pLogLength(l1);
  }
 
  bucket->buckets[i] = p1;
#ifdef USE_COEF_BUCKETS
  assume(bucket->coef[i]==NULL);
 
  if (!(n_IsOne(n,r)))
  {
    bucket->coef[i]=p_NSet(n,r);
  }
  else
  {
    bucket->coef[i]=NULL;
    n_Delete(&n,r);
  }
 
  if (p1==NULL)
    p_Delete(&bucket->coef[i],r);
#endif
  bucket->buckets_length[i]=l1;
  if (i > bucket->buckets_used)
    bucket->buckets_used = i;
  else
    kBucketAdjustBucketsUsed(bucket);
 
  kbTest(bucket);
}

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.

                                             {
 
  MULTIPLY_BUCKET(bucket,i);
 
  int l1 = bucket->buckets_length[i];
  poly p1 = bucket->buckets[i];
  bucket->buckets[i] = NULL;
  bucket->buckets_length[i] = 0;
  i = pLogLength(l1);
 
  while (bucket->buckets[i] != NULL)
  {
    //kbTest(bucket);
    MULTIPLY_BUCKET(bucket,i);
    p1 = p_Add_q(p1, bucket->buckets[i],
                 l1, bucket->buckets_length[i], bucket->bucket_ring);
    bucket->buckets[i] = NULL;
    bucket->buckets_length[i] = 0;
    i = pLogLength(l1);
  }
 
  bucket->buckets[i] = p1;
  bucket->buckets_length[i]=l1;
  if (i >= bucket->buckets_used)
    bucket->buckets_used = i;
  else
    kBucketAdjustBucketsUsed(bucket);
}

kBucketClear()

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

Definition at line 521 of file kbuckets.cc.

{
  assume(pLength(bucket->p) == bucket->l);
  *p = bucket->p;
  *length = bucket->l;
  bucket->p = NULL;
  bucket->l = 0;
}

kBucketCreate()

kBucket_pt kBucketCreate

(

const ring

bucket_ring

)

Creation/Destruction of buckets.

Definition at line 209 of file kbuckets.cc.

{
  assume(bucket_ring != NULL);
  kBucket_pt bucket = (kBucket_pt) omAlloc0Bin(kBucket_bin);
  bucket->bucket_ring = bucket_ring;
  return bucket;
}

kBucketDeleteAndDestroy()

void kBucketDeleteAndDestroy

(

kBucket_pt *

bucket_pt

)

Definition at line 223 of file kbuckets.cc.

{
  kBucket_pt bucket = *bucket_pt;
  kbTest(bucket);
  int i;
  for (i=0; i<= bucket->buckets_used; i++)
  {
    p_Delete(&(bucket->buckets[i]), bucket->bucket_ring);
#ifdef USE_COEF_BUCKETS
    p_Delete(&(bucket->coef[i]), bucket->bucket_ring);
#endif
  }
  omFreeBin(bucket, kBucket_bin);
  *bucket_pt = NULL;
}

kBucketDestroy()

void kBucketDestroy

(

kBucket_pt *

bucket_pt

)

Definition at line 216 of file kbuckets.cc.

{
  omFreeBin(*bucket_pt, kBucket_bin);
  *bucket_pt = NULL;
}

kBucketExtractLm()

poly kBucketExtractLm ( kBucket_pt  bucket )

inline

Definition at line 511 of file kbuckets.cc.

{
  poly lm = bucket->p;
  assume(pLength(bucket->p) == bucket->l);
  pIter(bucket->p);
  (bucket->l)--;
  pNext(lm) = NULL;
  return lm;
}

kBucketExtractLmOfBucket()

poly kBucketExtractLmOfBucket	(	kBucket_pt	bucket,
		int	i
	)

Definition at line 1455 of file kbuckets.cc.

{
  assume(bucket->buckets[i]!=NULL);
 
  poly p=bucket->buckets[i];
  bucket->buckets_length[i]--;
#ifdef USE_COEF_BUCKETS
  ring r=bucket->bucket_ring;
  if (bucket->coef[i]!=NULL)
  {
    poly next=pNext(p);
    if (next==NULL)
    {
      MULTIPLY_BUCKET(bucket,i);
      p=bucket->buckets[i];
      bucket->buckets[i]=NULL;
      return p;
    }
    else
    {
      bucket->buckets[i]=next;
      number c=p_GetCoeff(bucket->coef[i],r);
      pNext(p)=NULL;
      p=__p_Mult_nn(p,c,r);
      assume(p!=NULL);
      return p;
    }
  }
  else
#endif
  {
    bucket->buckets[i]=pNext(bucket->buckets[i]);
    pNext(p)=NULL;
    assume(p!=NULL);
    return p;
  }
}

kBucketGetLm()

const poly kBucketGetLm

(

kBucket_pt

bucket

)

Definition at line 506 of file kbuckets.cc.

{
  return bucket->p;
}

kBucketInit()

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

Definition at line 493 of file kbuckets.cc.

{
  int i;
 
  assume(bucket != NULL);
  assume(length <= 0 || length == pLength(lm));
 
  bucket->p = lm;
  if (length <= 0) bucket->l = pLength(lm);
  else bucket->l = length;
 
}

kBucketPolyRed()

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

Definition at line 1071 of file kbuckets.cc.

{
  ring r=bucket->bucket_ring;
  assume((!rIsPluralRing(r))||p_LmEqual(p1,kBucketGetLm(bucket), r));
  assume(p1 != NULL &&
         p_DivisibleBy(p1,  kBucketGetLm(bucket), r));
  assume(pLength(p1) == (unsigned) l1);
 
  poly a1 = pNext(p1), lm = kBucketExtractLm(bucket);
  BOOLEAN reset_vec=FALSE;
  number rn;
 
  /* we shall reduce bucket=bn*lm+... by p1=an*t+a1 where t=lm(p1)
     and an,bn shall be defined further down only if lc(p1)!=1
     we already know: an|bn and t|lm */
  if(a1==NULL)
  {
    p_LmDelete(&lm, r);
    return n_Init(1,r->cf);
  }
 
  if (! n_IsOne(pGetCoeff(p1),r->cf))
  {
    number an = pGetCoeff(p1), bn = pGetCoeff(lm);
    /* ksCheckCoeff: divide out gcd from an and bn: */
    int ct = ksCheckCoeff(&an, &bn,r->cf);
    /* the previous command returns ct=0 or ct=2 iff an!=1
       note: an is now 1 or -1 */
 
    /* setup factor for p1 which cancels leading terms */
    p_SetCoeff(lm, bn, r);
    if ((ct == 0) || (ct == 2))
    {
      /* correct factor for cancelation by changing sign if an=-1 */
      if (rField_is_Ring(r))
        lm = __p_Mult_nn(lm, an, r);
      else
        kBucket_Mult_n(bucket, an);
    }
    rn = an;
  }
  else
  {
    rn = n_Init(1,r->cf);
  }
 
  if (p_GetComp(p1, r) != p_GetComp(lm, r))
  {
    p_SetCompP(a1, p_GetComp(lm, r), r);
    reset_vec = TRUE;
    p_SetComp(lm, p_GetComp(p1, r), r);
    p_Setm(lm, r);
  }
 
  p_ExpVectorSub(lm, p1, r);
  l1--;
 
  assume((unsigned)l1==pLength(a1));
 
#ifdef HAVE_SHIFTBBA
  poly lmRight;
  poly lm_org;
  if (r->isLPring)
  {
    int firstBlock = p_mFirstVblock(p1, r);
    lm_org=lm;
    k_SplitFrame(lm, lmRight, si_max(firstBlock, 1), r);
  }
#endif
#if 0
  BOOLEAN backuped=FALSE;
  number coef;
  //@Viktor, don't ignore coefficients on monomials
  if(l1==1) {
 
    //if (rField_is_Q(r)) {
      //avoid this for function fields, as gcds are expensive at the moment
 
 
      coef=p_GetCoeff(a1,r);
      lm=p_Mult_nn(lm, coef, r);
      p_SetCoeff0(a1, n_Init(1,r), r);
      backuped=TRUE;
      //WARNING: not thread_safe
    //deletes coef as side effect
    //}
  }
#endif
 
#ifdef HAVE_SHIFTBBA
  if (r->isLPring)
  {
    poly tmp=r->p_Procs->pp_Mult_mm(a1, lmRight, r);
    kBucket_Minus_m_Mult_p(bucket, lm,tmp, &l1, spNoether);
    p_Delete(&tmp,r);
    p_LmDelete(&lmRight,r);
    p_LmDelete(lm_org,r);
  }
  else
#endif
  {
    kBucket_Minus_m_Mult_p(bucket, lm, a1, &l1, spNoether);
  }
 
#if 0
  if (backuped)
    p_SetCoeff0(a1,coef,r);
#endif
 
  p_LmDelete(&lm, r);
  if (reset_vec) p_SetCompP(a1, 0, r);
  kbTest(bucket);
  return rn;
}

kBucketPolyRedNF()

void kBucketPolyRedNF	(	kBucket_pt	bucket,
		poly	p1,
		int	l1,
		poly	spNoether
	)

Definition at line 1188 of file kbuckets.cc.

{
  ring r=bucket->bucket_ring;
  assume((!rIsPluralRing(r))||p_LmEqual(p1,kBucketGetLm(bucket), r));
  assume(p1 != NULL &&
         p_DivisibleBy(p1,  kBucketGetLm(bucket), r));
  assume(pLength(p1) == (unsigned) l1);
 
  poly a1 = pNext(p1), lm = kBucketExtractLm(bucket);
  BOOLEAN reset_vec=FALSE;
 
  /* we shall reduce bucket=bn*lm+... by p1=an*t+a1 where t=lm(p1)
     and an,bn shall be defined further down only if lc(p1)!=1
     we already know: an|bn and t|lm */
  if(a1==NULL)
  {
    p_LmDelete(&lm, r);
    return;
  }
 
  #ifdef KDEBUG
  if (n_DivBy(pGetCoeff(lm),pGetCoeff(p1),r->cf))
  #endif
  {
    number c=n_Div(pGetCoeff(lm),pGetCoeff(p1),r->cf);
    //StringSetS("mult cf:");n_Write(c,r->cf);StringAppendS("\n");
    //PrintS(StringEndS());
    #ifdef KDEBUG
    if (n_IsZero(c,r->cf))
    {
      StringSetS("a/b: ");n_Write(pGetCoeff(lm),r->cf);StringAppendS(" / ");
      n_Write(pGetCoeff(p1),r->cf);StringAppendS("\n");PrintS(StringEndS());
    }
    #endif
    p_SetCoeff(lm,c,r);
  }
  #ifdef KDEBUG
  else
  {
    PrintS("bug\n");
  }
  #endif
  if (p_GetComp(p1, r) != p_GetComp(lm, r))
  {
    p_SetCompP(a1, p_GetComp(lm, r), r);
    reset_vec = TRUE;
    p_SetComp(lm, p_GetComp(p1, r), r);
    p_Setm(lm, r);
  }
 
  p_ExpVectorSub(lm, p1, r);
  l1--;
 
  assume((unsigned)l1==pLength(a1));
 
#ifdef HAVE_SHIFTBBA
  poly lmRight;
  poly lm_org;
  if (r->isLPring)
  {
    int firstBlock = p_mFirstVblock(p1, r);
    lm_org=lm;
    k_SplitFrame(lm, lmRight, si_max(firstBlock, 1), r);
  }
#endif
 
#ifdef HAVE_SHIFTBBA
  if (r->isLPring)
  {
    poly tmp=r->p_Procs->pp_Mult_mm(a1, lmRight, r);
    kBucket_Minus_m_Mult_p(bucket, lm,tmp, &l1, spNoether);
    p_Delete(&tmp,r);
    p_LmDelete(&lmRight,r);
    p_LmDelete(lm_org,r);
  }
  else
#endif
  {
    kBucket_Minus_m_Mult_p(bucket, lm, a1, &l1, spNoether);
  }
 
#if 0
  if (backuped)
    p_SetCoeff0(a1,coef,r);
#endif
 
  p_LmDelete(&lm, r);
  if (reset_vec) p_SetCompP(a1, 0, r);
  kbTest(bucket);
  return;
}

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.

{
#ifndef HAVE_PSEUDO_BUCKETS
  int i;
 
  kBucketCanonicalize(bucket);
  for (i=0; i<= bucket->buckets_used; i++)
    if (bucket->buckets[i] != NULL)
    {
      MULTIPLY_BUCKET(bucket,i);
      bucket->buckets[i] = p_shallow_copy_delete(bucket->buckets[i],
                                                 bucket->bucket_ring,
                                                 new_tailRing,
                                                 new_tailBin);
    }
#else
  bucket->p = p_shallow_copy_delete(p,
                                    bucket_ring,
                                    new_tailRing,
                                    new_tailBin);
#endif
  bucket->bucket_ring = new_tailRing;
}

kBucketSimpleContent()

void kBucketSimpleContent

(

kBucket_pt

bucket

)

Definition at line 1283 of file kbuckets.cc.

{
  if (bucket->buckets[0]==NULL) return;
 
  ring r=bucket->bucket_ring;
  if (rField_is_Ring(r)) return;
 
  coeffs cf=r->cf;
  if (cf->cfSubringGcd==ndGcd) /* trivial gcd*/ return;
 
  number nn=pGetCoeff(bucket->buckets[0]);
  //if ((bucket->buckets_used==0)
  //&&(!n_IsOne(nn,cf)))
  //{
  //  if (TEST_OPT_PROT) PrintS("@");
  //  p_SetCoeff(bucket->buckets[0],n_Init(1,cf),r);
  //  return;
  //}
 
  if (n_Size(nn,cf)<2) return;
 
  //kBucketAdjustBucketsUsed(bucket);
  number coef=n_Copy(nn,cf);
  // find an initial guess of a gcd
  for (int i=1; i<=bucket->buckets_used;i++)
  {
    if (bucket->buckets[i]!=NULL)
    {
      number t=p_InitContent(bucket->buckets[i],r);
      if (n_Size(t,cf)<2)
      {
        n_Delete(&t,cf);
        n_Delete(&coef,cf);
        return;
      }
      number t2=n_SubringGcd(coef,t,cf);
      n_Delete(&t,cf);
      n_Delete(&coef,cf);
      coef=t2;
      if (n_Size(coef,cf)<2) { n_Delete(&coef,cf);return;}
    }
  }
  // find the gcd
  for (int i=0; i<=bucket->buckets_used;i++)
  {
    if (bucket->buckets[i]!=NULL)
    {
      poly p=bucket->buckets[i];
      while(p!=NULL)
      {
        number t=n_SubringGcd(coef,pGetCoeff(p),cf);
        if (n_Size(t,cf)<2)
        {
          n_Delete(&t,cf);
          n_Delete(&coef,cf);
          return;
        }
        pIter(p);
      }
    }
  }
  // divided by the gcd
  if (TEST_OPT_PROT) PrintS("@");
  for (int i=bucket->buckets_used;i>=0;i--)
  {
    if (bucket->buckets[i]!=NULL)
    {
      poly p=bucket->buckets[i];
      while(p!=NULL)
      {
        number d = n_ExactDiv(pGetCoeff(p),coef,cf);
        p_SetCoeff(p,d,r);
        pIter(p);
      }
    }
  }
  n_Delete(&coef,cf);
}

kBucketTakeOutComp()

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

Definition at line 1032 of file kbuckets.cc.

{
  poly p = NULL, q;
  int i, lp = 0, lq;
 
#ifndef HAVE_PSEUDO_BUCKETS
  kBucketMergeLm(bucket);
  for (i=1; i<=bucket->buckets_used; i++)
  {
    if (bucket->buckets[i] != NULL)
    {
      MULTIPLY_BUCKET(bucket,i);
      p_TakeOutComp(&(bucket->buckets[i]), comp, &q, &lq, bucket->bucket_ring);
      if (q != NULL)
      {
        assume(pLength(q) == (unsigned)lq);
        bucket->buckets_length[i] -= lq;
        assume(pLength(bucket->buckets[i]) == (unsigned)bucket->buckets_length[i]);
        p = p_Add_q(p, q, lp, lq, bucket->bucket_ring);
      }
    }
  }
  kBucketAdjustBucketsUsed(bucket);
#else
  p_TakeOutComp(&(bucket->p), comp, &p, &lp,bucket->bucket_ring);
  (bucket->l) -= lp;
#endif
  *r_p = p;
  *l = lp;
 
  kbTest(bucket);
}

ksCheckCoeff()

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

Definition at line 1504 of file kbuckets.cc.

{
  int c = 0;
  number an = *a, bn = *b;
  n_Test(an,r);
  n_Test(bn,r);
 
  if (UNLIKELY(nCoeff_is_Ring(r) && n_DivBy(bn,an,r))) // in NF
  {
      bn = n_ExactDiv(bn, an, r);
      an = n_Init(1, r);
  }
  else
  {
    number cn = n_SubringGcd(an, bn, r);
    if(n_IsOne(cn, r))
    {
      an = n_Copy(an, r); // a/1
      bn = n_Copy(bn, r); // b/1
    }
    else
    {
      an = n_ExactDiv(an, cn, r);
      bn = n_ExactDiv(bn, cn, r);
    }
    n_Delete(&cn, r);
  }
  if (n_IsOne(an, r))
  {
    c = 1;
  }
  if (n_IsOne(bn, r))
  {
    c += 2;
  }
  *a = an;
  *b = bn;
  return c;
}

LOG4()

static int LOG4 ( int  v )

inlinestatic

Some internal stuff.

Definition at line 56 of file kbuckets.cc.

{
  const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
  const unsigned int S[] = {1, 2, 4, 8, 16};
 
  unsigned int r = 0; // result of log4(v) will go here
  if (v & b[4]) { v >>= S[4]; r |= S[3]; }
  if (v & b[3]) { v >>= S[3]; r |= S[2]; }
  if (v & b[2]) { v >>= S[2]; r |= S[1]; }
  if (v & b[1]) { v >>= S[1]; r |= S[0]; }
  return (int)r;
}

p_TakeOutComp()

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

Definition at line 3496 of file p_polys.cc.

{
  spolyrec pp, qq;
  poly p, q, p_prev;
  int l = 0;
 
#ifndef SING_NDEBUG
  int lp = pLength(*r_p);
#endif
 
  pNext(&pp) = *r_p;
  p = *r_p;
  p_prev = &pp;
  q = &qq;
 
  while(p != NULL)
  {
    while (__p_GetComp(p,r) == comp)
    {
      pNext(q) = p;
      pIter(q);
      p_SetComp(p, 0,r);
      p_SetmComp(p,r);
      pIter(p);
      l++;
      if (p == NULL)
      {
        pNext(p_prev) = NULL;
        goto Finish;
      }
    }
    pNext(p_prev) = p;
    p_prev = p;
    pIter(p);
  }
 
  Finish:
  pNext(q) = NULL;
  *r_p = pNext(&pp);
  *r_q = pNext(&qq);
  *lq = l;
#ifndef SING_NDEBUG
  assume(pLength(*r_p) + pLength(*r_q) == (unsigned)lp);
#endif
  p_Test(*r_p,r);
  p_Test(*r_q,r);
}

pLogLength() [1/2]

static unsigned int pLogLength ( poly  p )

inlinestatic

Definition at line 86 of file kbuckets.cc.

{
  return pLogLength((unsigned int) pLength(p));
}

pLogLength() [2/2]

static unsigned int pLogLength ( unsigned int  l )

inlinestatic

Definition at line 71 of file kbuckets.cc.

{
  unsigned int i = 0;
 
  if (l == 0) return 0;
  l--;
#ifdef BUCKET_TWO_BASE
  i=SI_LOG2(l);
#else
  i=LOG4(l);
#endif
  return i+1;
}

Variable Documentation

kBucket_bin

STATIC_VAR omBin kBucket_bin = omGetSpecBin(sizeof(kBucket))

Definition at line 45 of file kbuckets.cc.