Loading...
Searching...
No Matches
kbuckets.cc
Go to the documentation of this file.
/****************************************
* Computer Algebra System SINGULAR *
****************************************/
#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"
#ifdef HAVE_SHIFTBBA
#include "polys/shiftop.h"
#endif
#ifdef HAVE_COEF_BUCKETS
#define USE_COEF_BUCKETS
#endif
#ifdef USE_COEF_BUCKETS
#ifdef HAVE_RINGS_OLD
#define MULTIPLY_BUCKET(B,I) do \
{ if (B->coef[I]!=NULL) \
{ \
assume(p_IsConstant(B->Coef[i],B->bucket->ring)); \
B->buckets[I]=p_Mult_q(B->buckets[I],B->coef[I],B->bucket_ring); \
B->coef[I]=NULL; \
} \
} while(0) \
if (rField_is_Ring(B->bucket_ring)) B->buckets_length[i] = pLength(B->buckets[i]);
#else
#define MULTIPLY_BUCKET(B,I) do \
{ if (B->coef[I]!=NULL) \
{ \
B->buckets[I]=p_Mult_q(B->buckets[I],B->coef[I],B->bucket_ring); \
B->coef[I]=NULL; \
} \
} while(0)
#endif
#else
#define MULTIPLY_BUCKET(B,I)
#endif
STATIC_VAR omBin kBucket_bin = omGetSpecBin(sizeof(kBucket));
#ifdef USE_COEF_BUCKETS
STATIC_VAR int coef_start=1;
#endif
//////////////////////////////////////////////////////////////////////////
///
/// Some internal stuff
///
// https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
#ifndef BUCKET_TWO_BASE
static inline int LOG4(int v)
{
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;
}
#endif
// returns ceil(log_4(l))
static inline unsigned int pLogLength(unsigned int l)
{
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;
}
// returns ceil(log_4(pLength(p)))
static inline unsigned int pLogLength(poly p)
{
return pLogLength((unsigned int) pLength(p));
}
#ifdef KDEBUG
#ifndef HAVE_PSEUDO_BUCKETS
BOOLEAN kbTest_i(kBucket_pt bucket, int i)
{//sBucketSortMerge
#ifdef USE_COEF_BUCKETS
assume(bucket->coef[0]==NULL);
if ((bucket->coef[i]!=NULL) && (bucket->buckets[i]==NULL))
{
dReportError("Bucket %d coef not NULL", i);
}
if (bucket->coef[i]!=NULL)
{
assume(bucket->buckets[i]!=NULL);
p_Test(bucket->coef[i],bucket->bucket_ring);
}
#endif
pFalseReturn(p_Test(bucket->buckets[i], bucket->bucket_ring));
if (bucket->buckets_length[i] != pLength(bucket->buckets[i]))
{
dReportError("Bucket %d lengths difference should:%d has:%d",
i, bucket->buckets_length[i], pLength(bucket->buckets[i]));
}
else if (i > 0 && (int) pLogLength(bucket->buckets_length[i]) > i)
{
dReportError("Bucket %d too long %d",
i, bucket->buckets_length[i]);
}
if (i==0 && bucket->buckets_length[0] > 1)
{
dReportError("Bucket 0 too long");
}
return TRUE;
}
BOOLEAN kbTest(kBucket_pt bucket)
{
#ifdef HAVE_COEF_BUCKETS
assume(bucket->coef[0]==NULL);
#endif
int i;
poly lm = bucket->buckets[0];
omCheckAddrBin(bucket, kBucket_bin);
assume(bucket->buckets_used <= MAX_BUCKET);
if (! kbTest_i(bucket, 0)) return FALSE;
for (i=1; i<= (int) bucket->buckets_used; i++)
{
if (!kbTest_i(bucket, i)) return FALSE;
if (lm != NULL && bucket->buckets[i] != NULL
&& p_LmCmp(lm, bucket->buckets[i], bucket->bucket_ring) != 1)
{
dReportError("Bucket %d larger or equal than lm", i);
if (p_LmCmp(lm, bucket->buckets[i], bucket->bucket_ring) ==0)
dReportError("Bucket %d equal to lm", i);
return FALSE;
}
if (!p_Test(bucket->buckets[i],bucket->bucket_ring))
{
dReportError("Bucket %d is not =0(4)", i);
return FALSE;
}
}
for (; i<=MAX_BUCKET; i++)
{
if (bucket->buckets[i] != NULL || bucket->buckets_length[i] != 0)
{
dReportError("Bucket %d not zero", i);
return FALSE;
}
}
for(i=0;i<=MAX_BUCKET;i++)
{
if (bucket->buckets[i]!=NULL)
{
int j;
for(j=i+1;j<=MAX_BUCKET;j++)
{
if (bucket->buckets[j]==bucket->buckets[i])
{
dReportError("Bucket %d %d equal", i,j);
return FALSE;
}
}
}
#ifdef HAVE_COEF_BUCKETS
if (bucket->coef[i]!=NULL)
{
int j;
for(j=i+1;j<=MAX_BUCKET;j++)
{
if (bucket->coef[j]==bucket->coef[i])
{
dReportError("internal coef %d %d equal", i,j);
return FALSE;
}
}
}
#endif
}
return TRUE;
}
#else // HAVE_PSEUDO_BUCKETS
BOOLEAN kbTest(kBucket_pt bucket)
{
return TRUE;
}
#endif // ! HAVE_PSEUDO_BUCKETS
#endif // KDEBUG
//////////////////////////////////////////////////////////////////////////
///
/// Creation/Destruction of buckets
///
kBucket_pt kBucketCreate(const ring bucket_ring)
{
assume(bucket_ring != NULL);
kBucket_pt bucket = (kBucket_pt) omAlloc0Bin(kBucket_bin);
bucket->bucket_ring = bucket_ring;
return bucket;
}
void kBucketDestroy(kBucket_pt *bucket_pt)
{
omFreeBin(*bucket_pt, kBucket_bin);
*bucket_pt = NULL;
}
void kBucketDeleteAndDestroy(kBucket_pt *bucket_pt)
{
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;
}
/////////////////////////////////////////////////////////////////////////////
// Conversion from/to Bpolys
//
#ifndef HAVE_PSEUDO_BUCKETS
inline void kBucketMergeLm(kBucket_pt bucket)
{
kbTest(bucket);
if (bucket->buckets[0] != NULL)
{
poly lm = bucket->buckets[0];
int i = 1;
#ifdef BUCKET_TWO_BASE
int l = 2;
while ( bucket->buckets_length[i] >= l)
{
i++;
l = l << 1;
}
#else
int l = 4;
while ( bucket->buckets_length[i] >= l)
{
i++;
l = l << 2;
}
#endif
#ifndef USE_COEF_BUCKETS
MULTIPLY_BUCKET(bucket,i);
pNext(lm) = bucket->buckets[i];
bucket->buckets[i] = lm;
bucket->buckets_length[i]++;
assume(i <= bucket->buckets_used+1);
if (i > bucket->buckets_used) bucket->buckets_used = i;
bucket->buckets[0] = NULL;
bucket->buckets_length[0] = 0;
kbTest(bucket);
#else
if (i > bucket->buckets_used) bucket->buckets_used = i;
assume(i!=0);
if (bucket->buckets[i]!=NULL)
{
MULTIPLY_BUCKET(bucket,i);
pNext(lm) = bucket->buckets[i];
bucket->buckets[i] = lm;
bucket->buckets_length[i]++;
assume(i <= bucket->buckets_used+1);
}
else
{
#if 1
assume(bucket->buckets[i]==NULL);
assume(bucket->coef[0]==NULL);
assume(pLength(lm)==1);
assume(pNext(lm)==NULL);
number coef=p_GetCoeff(lm,bucket->bucket_ring);
//WARNING: not thread_safe
p_SetCoeff0(lm, n_Init(1,bucket->bucket_ring), bucket->bucket_ring);
bucket->buckets[i]=lm;
bucket->buckets_length[i]=1;
bucket->coef[i]=p_NSet(n_Copy(coef,bucket->bucket_ring),bucket->bucket_ring);
bucket->buckets[i]=lm;
bucket->buckets_length[i]=1;
#else
MULTIPLY_BUCKET(bucket,i);
pNext(lm) = bucket->buckets[i];
bucket->buckets[i] = lm;
bucket->buckets_length[i]++;
assume(i <= bucket->buckets_used+1);
#endif
}
bucket->buckets[0]=NULL;
bucket->buckets_length[0] = 0;
bucket->coef[0]=NULL;
kbTest(bucket);
#endif
}
}
BOOLEAN kBucketIsCleared(kBucket_pt bucket)
{
int i;
for (i = 0;i<=MAX_BUCKET;i++)
{
if (bucket->buckets[i] != NULL) return FALSE;
#ifdef HAVE_COEF_BUCKETS
if (bucket->coef[i] != NULL) return FALSE;
#endif
if (bucket->buckets_length[i] != 0) return FALSE;
}
return TRUE;
}
void kBucketInit(kBucket_pt bucket, poly lm, int length)
{
//assume(false);
assume(bucket != NULL);
assume(length <= 0 || length == pLength(lm));
assume(kBucketIsCleared(bucket));
if (lm == NULL) return;
if (length <= 0)
length = pLength(lm);
bucket->buckets[0] = lm;
#ifdef HAVE_COEF_BUCKETS
assume(bucket->coef[0]==NULL);
#endif
#ifdef USE_COEF_BUCKETS
bucket->coef[0]=NULL;
#endif
if (lm!=NULL)
bucket->buckets_length[0] = 1;
else
bucket->buckets_length[0]= 0;
if (length > 1)
{
unsigned int i = pLogLength(length-1);
bucket->buckets[i] = pNext(lm);
pNext(lm) = NULL;
bucket->buckets_length[i] = length-1;
bucket->buckets_used = i;
}
else
{
bucket->buckets_used = 0;
}
}
int kBucketCanonicalize(kBucket_pt bucket)
{
#ifndef HAVE_PSEUDO_BUCKETS
assume(bucket->buckets_used<=MAX_BUCKET);
MULTIPLY_BUCKET(bucket,1);
kbTest(bucket);
poly p = bucket->buckets[1];
poly lm;
int pl = bucket->buckets_length[1];//, i;
int i;
bucket->buckets[1] = NULL;
bucket->buckets_length[1] = 0;
#ifdef USE_COEF_BUCKETS
assume(bucket->coef[1]==NULL);
#endif
ring r=bucket->bucket_ring;
for (i=1; i<=bucket->buckets_used; i++)
{
#ifdef USE_COEF_BUCKETS
if (bucket->coef[i]!=NULL)
{
assume(bucket->buckets[i]!=NULL);
p = p_Plus_mm_Mult_qq(p, bucket->coef[i], bucket->buckets[i],
pl, bucket->buckets_length[i], r);
p_Delete(&bucket->coef[i],r);
p_Delete(&bucket->buckets[i],r);
}
else
p = p_Add_q(p, bucket->buckets[i],
pl, bucket->buckets_length[i], r);
#else
p = p_Add_q(p, bucket->buckets[i],
pl, bucket->buckets_length[i], r);
#endif
if (i==1) continue;
bucket->buckets[i] = NULL;
bucket->buckets_length[i] = 0;
}
#ifdef HAVE_COEF_BUCKETS
assume(bucket->coef[0]==NULL);
#endif
lm = bucket->buckets[0];
if (lm != NULL)
{
pNext(lm) = p;
p = lm;
pl++;
bucket->buckets[0] = NULL;
bucket->buckets_length[0] = 0;
}
if (pl > 0)
{
i = pLogLength(pl);
bucket->buckets[i] = p;
bucket->buckets_length[i] = pl;
}
else
{
i = 0;
}
bucket->buckets_used = i;
assume(bucket->buckets_used <= MAX_BUCKET);
#ifdef USE_COEF_BUCKETS
assume(bucket->coef[0]==NULL);
assume(bucket->coef[i]==NULL);
#endif
assume(pLength(p) == pl);
//if (TEST_OPT_PROT) { Print("C(%d)",pl); }
kbTest(bucket);
return i;
#endif
}
void kBucketNormalize(kBucket_pt bucket)
{
#ifdef HAVE_PSEUDO_BUCKETS
p_Normalize(bucket->p,bucket->bucket_ring);
#else
MULTIPLY_BUCKET(bucket,1);
for (int i=0; i<=bucket->buckets_used; i++)
{
p_Normalize(bucket->buckets[i],bucket->bucket_ring);
}
#endif
}
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
{
int i = kBucketCanonicalize(bucket);
if (i > 0)
{
#ifdef USE_COEF_BUCKETS
MULTIPLY_BUCKET(bucket,i);
//bucket->coef[i]=NULL;
#endif
*p = bucket->buckets[i];
*length = bucket->buckets_length[i];
bucket->buckets[i] = NULL;
bucket->buckets_length[i] = 0;
bucket->buckets_used = 0;
}
else
{
*p = NULL;
*length = 0;
}
}
void kBucketSetLm(kBucket_pt bucket, poly lm)
{
kBucketMergeLm(bucket);
pNext(lm) = NULL;
bucket->buckets[0] = lm;
bucket->buckets_length[0] = 1;
}
#else // HAVE_PSEUDO_BUCKETS
void kBucketInit(kBucket_pt bucket, poly lm, int length)
{
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;
}
const poly kBucketGetLm(kBucket_pt bucket)
{
return bucket->p;
}
poly kBucketExtractLm(kBucket_pt bucket)
{
poly lm = bucket->p;
assume(pLength(bucket->p) == bucket->l);
pIter(bucket->p);
(bucket->l)--;
pNext(lm) = NULL;
return lm;
}
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
{
assume(pLength(bucket->p) == bucket->l);
*p = bucket->p;
*length = bucket->l;
bucket->p = NULL;
bucket->l = 0;
}
#endif // ! HAVE_PSEUDO_BUCKETS
//////////////////////////////////////////////////////////////////////////
///
/// For changing the ring of the Bpoly to new_tailBin
///
void kBucketShallowCopyDelete(kBucket_pt bucket,
ring new_tailRing, omBin new_tailBin,
pShallowCopyDeleteProc p_shallow_copy_delete)
{
#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;
}
//////////////////////////////////////////////////////////////////////////
///
/// Bucket number i from bucket is out of length sync, resync
///
void kBucketAdjust(kBucket_pt bucket, int i) {
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);
}
//////////////////////////////////////////////////////////////////////////
///
/// Multiply Bucket by number ,i.e. Bpoly == n*Bpoly
///
void kBucket_Mult_n(kBucket_pt bucket, number n)
{
#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
}
//////////////////////////////////////////////////////////////////////////
///
/// Add to Bucket a poly ,i.e. Bpoly == q+Bpoly
///
void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
{
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);
}
//////////////////////////////////////////////////////////////////////////
///
/// Bpoly == Bpoly - m*p; where m is a monom
/// Does not destroy p and m
/// assume (*l <= 0 || pLength(p) == *l)
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l,
poly spNoether)
{
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])==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
}
//////////////////////////////////////////////////////////////////////////
///
/// Bpoly == Bpoly + m*p; where m is a monom
/// Does not destroy p and m
/// assume (l <= 0 || pLength(p) == l)
void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l)
{
assume((!rIsPluralRing(bucket->bucket_ring))||p_IsConstant(m, bucket->bucket_ring));
assume(l <= 0 || pLength(p) == 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);
}
poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append)
{
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;
}
}
}
/////////////////////////////////////////////////////////////////////////////
//
// Extract all monomials from bucket with component comp
// Return as a polynomial *p with length *l
// In other words, afterwards
// Bpoly = Bpoly - (poly consisting of all monomials with component comp)
// and components of monomials of *p are all 0
//
// Hmm... for now I'm too lazy to implement those independent of currRing
// But better declare it extern than including polys.h
extern 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)
{
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) == lq);
bucket->buckets_length[i] -= lq;
assume(pLength(bucket->buckets[i]) == 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);
}
/////////////////////////////////////////////////////////////////////////////
// Reduction of Bpoly with a given poly
//
number kBucketPolyRed(kBucket_pt bucket,
poly p1, int l1,
poly spNoether)
{
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) == 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 cancellation 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(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;
}
void kBucketPolyRedNF(kBucket_pt bucket,
poly p1, int l1,
poly spNoether)
{
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) == 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(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;
}
#ifndef USE_COEF_BUCKETS
void kBucketSimpleContent(kBucket_pt bucket)
{
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);
}
#else
static BOOLEAN nIsPseudoUnit(number n, ring r)
{
if (rField_is_Zp(r))
return TRUE;
if (rParameter(r)==NULL)
{
return (n_Size(n,r->cf)==1);
}
//if (r->parameter!=NULL)
return (n_IsOne(n,r->cf) || n_IsMOne(n,r->cf));
}
void kBucketSimpleContent(kBucket_pt bucket)
{
ring r=bucket->bucket_ring;
int i;
//PrintS("HHHHHHHHHHHHH");
for (i=0;i<=MAX_BUCKET;i++)
{
//if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]!=NULL))
// PrintS("H2H2H2");
if (i==0)
{
assume(bucket->buckets[i]==NULL);
}
if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]==NULL))
return;
}
for (i=0;i<=MAX_BUCKET;i++)
{
//if ((bucket->buckets[i]!=NULL) && (bucket->coef[i]!=NULL))
// PrintS("H2H2H2");
if (i==0)
{
assume(bucket->buckets[i]==NULL);
}
if ((bucket->buckets[i]!=NULL)
&& (nIsPseudoUnit(p_GetCoeff(bucket->coef[i],r),r)))
return;
}
//return;
number coef=n_Init(0,r);
//ATTENTION: will not work correct for GB over ring
//if (TEST_OPT_PROT)
// PrintS("CCCCCCCCCCCCC");
for (i=MAX_BUCKET;i>=0;i--)
{
if (i==0)
{
assume(bucket->buckets[i]==NULL);
}
if (bucket->buckets[i]!=NULL)
{
assume(bucket->coef[i]!=NULL);
assume(!(n_IsZero(pGetCoeff(bucket->coef[i]),r)));
//in this way it should crash on programming errors, yeah
number temp=n_Gcd(coef, pGetCoeff(bucket->coef[i]),r);
n_Delete(&coef,r );
coef=temp;
if (nIsPseudoUnit(coef,r))
{
n_Delete(&coef,r);
return;
}
assume(!(n_IsZero(coef,r)));
}
}
if (n_IsZero(coef,r))
{
n_Delete(&coef,r);
return;
}
if (TEST_OPT_PROT)
PrintS("S");
for(i=0;i<=MAX_BUCKET;i++)
{
if (bucket->buckets[i]!=NULL)
{
assume(!(n_IsZero(coef,r)));
assume(bucket->coef[i]!=NULL);
number lc=p_GetCoeff(bucket->coef[i],r);
p_SetCoeff(bucket->coef[i], n_ExactDiv(lc,coef,r),r);
assume(!(n_IsZero(p_GetCoeff(bucket->coef[i],r),r)));
}
}
n_Delete(&coef,r);
}
#endif
poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i)
{
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;
}
}
/*
* input - output: a, b
* returns:
* a := a/gcd(a,b), b := b/gcd(a,b)
* and return value
* 0 -> a != 1, b != 1
* 1 -> a == 1, b != 1
* 2 -> a != 1, b == 1
* 3 -> a == 1, b == 1
* this value is used to control the spolys
*/
int ksCheckCoeff(number *a, number *b, const coeffs r)
{
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;
}
auxiliary.h
All the auxiliary stuff.
si_max
static int si_max(const int a, const int b)
Definition auxiliary.h:125
UNLIKELY
#define UNLIKELY(X)
Definition auxiliary.h:405
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
l
int l
Definition cfEzgcd.cc:100
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
p
int p
Definition cfModGcd.cc:4086
cf
CanonicalForm cf
Definition cfModGcd.cc:4091
b
CanonicalForm b
Definition cfModGcd.cc:4111
coeffs.h
Coefficient rings, fields and other domains suitable for Singular polynomials.
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition coeffs.h:457
n_Test
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r).
Definition coeffs.h:715
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:667
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:625
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:478
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:560
n_Div
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition coeffs.h:618
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:470
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:573
nCoeff_is_Ring
static FORCE_INLINE BOOLEAN nCoeff_is_Ring(const coeffs r)
Definition coeffs.h:732
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:461
n_Write
static FORCE_INLINE void n_Write(number n, const coeffs r, const BOOLEAN bShortOut=TRUE)
Definition coeffs.h:594
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:541
n_DivBy
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition coeffs.h:750
n_SubringGcd
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition coeffs.h:669
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition coeffs.h:474
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
j
int j
Definition facHensel.cc:110
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition facSparseHensel.h:25
STATIC_VAR
#define STATIC_VAR
Definition globaldefs.h:7
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
next
ListNode * next
Definition janet.h:31
kBucketDeleteAndDestroy
void kBucketDeleteAndDestroy(kBucket_pt *bucket_pt)
Definition kbuckets.cc:223
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition kbuckets.cc:521
kbTest
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition kbuckets.cc:197
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:722
kBucketTakeOutComp
void kBucketTakeOutComp(kBucket_pt bucket, long comp, poly *r_p, int *l)
Definition kbuckets.cc:1032
kBucket_Mult_n
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition kbuckets.cc:598
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition kbuckets.cc:216
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition kbuckets.cc:493
ksCheckCoeff
int ksCheckCoeff(number *a, number *b, const coeffs r)
Definition kbuckets.cc:1504
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition kbuckets.cc:511
kBucketAdjust
void kBucketAdjust(kBucket_pt bucket, int i)
Bucket number i from bucket is out of length sync, resync.
Definition kbuckets.cc:565
MULTIPLY_BUCKET
#define MULTIPLY_BUCKET(B, I)
Definition kbuckets.cc:43
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:998
kBucketExtractLmOfBucket
poly kBucketExtractLmOfBucket(kBucket_pt bucket, int i)
Definition kbuckets.cc:1455
kBucket_bin
STATIC_VAR omBin kBucket_bin
Definition kbuckets.cc:45
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition kbuckets.cc:209
LOG4
static int LOG4(int v)
Some internal stuff.
Definition kbuckets.cc:56
kBucketPolyRed
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition kbuckets.cc:1071
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:815
p_TakeOutComp
void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r)
Definition p_polys.cc:3620
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:660
kBucketPolyRedNF
void kBucketPolyRedNF(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition kbuckets.cc:1188
pLogLength
static unsigned int pLogLength(unsigned int l)
Definition kbuckets.cc:71
kBucketGetLm
const poly kBucketGetLm(kBucket_pt bucket)
Definition kbuckets.cc:506
kBucketSimpleContent
void kBucketSimpleContent(kBucket_pt bucket)
Definition kbuckets.cc:1283
kbuckets.h
kBucket::l
int l
Definition kbuckets.h:187
kBucketSetLm
void kBucketSetLm(kBucket_pt bucket, poly lm)
kBucketNormalize
void kBucketNormalize(kBucket_pt bucket)
apply n_Normalize to all coefficients
kBucketCanonicalize
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
kBucket::p
poly p
Definition kbuckets.h:186
kBucket::bucket_ring
ring bucket_ring
Definition kbuckets.h:196
kBucketIsCleared
BOOLEAN kBucketIsCleared(kBucket_pt bucket)
MAX_BUCKET
#define MAX_BUCKET
Bucket definition (should be no one elses business, though).
Definition kbuckets.h:179
kBucket
Definition kbuckets.h:183
assume
#define assume(x)
Definition mod2.h:389
dReportError
int dReportError(const char *fmt,...)
Definition dError.cc:44
p_SetCoeff0
#define p_SetCoeff0(p, n, r)
Definition monomials.h:60
p_GetComp
#define p_GetComp(p, r)
Definition monomials.h:64
pFalseReturn
#define pFalseReturn(cond)
Definition monomials.h:139
pIter
#define pIter(p)
Definition monomials.h:37
pNext
#define pNext(p)
Definition monomials.h:36
pSetCoeff0
#define pSetCoeff0(p, n)
Definition monomials.h:59
p_GetCoeff
#define p_GetCoeff(p, r)
Definition monomials.h:50
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:44
coeffs
The main handler for Singular numbers which are suitable for Singular polynomials.
lq
Definition lq.h:40
ndGcd
number ndGcd(number, number, const coeffs r)
Definition numbers.cc:193
numbers.h
omCheckAddrBin
#define omCheckAddrBin(addr, bin)
Definition omAllocDecl.h:325
omAlloc0Bin
#define omAlloc0Bin(bin)
Definition omAllocDecl.h:206
omFreeBin
#define omFreeBin(addr, bin)
Definition omAllocDecl.h:259
omGetSpecBin
#define omGetSpecBin(size)
Definition omBin.h:11
NULL
#define NULL
Definition omList.c:12
omBin
omBin_t * omBin
Definition omStructs.h:12
options.h
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition options.h:105
p_Normalize
void p_Normalize(poly p, const ring r)
Definition p_polys.cc:3939
p_NSet
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition p_polys.cc:1474
p_InitContent
number p_InitContent(poly ph, const ring r)
Definition p_polys.cc:2683
p_polys.h
pLength
static int pLength(poly a)
Definition p_polys.h:190
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:938
p_LmDelete
static void p_LmDelete(poly p, const ring r)
Definition p_polys.h:725
p_LmEqual
#define p_LmEqual(p1, p2, r)
Definition p_polys.h:1744
p_SetCompP
static void p_SetCompP(poly p, int i, ring r)
Definition p_polys.h:256
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition p_polys.h:249
p_ExpVectorSub
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition p_polys.h:1461
p_Setm
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition p_polys.h:414
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition p_polys.h:1601
p_IsConstant
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition p_polys.h:1985
p_DivisibleBy
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1921
p_Mult_nn
static poly p_Mult_nn(poly p, number n, const ring r)
Definition p_polys.h:960
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
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:1077
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:1204
p_Test
#define p_Test(p, r)
Definition p_polys.h:161
__p_Mult_nn
#define __p_Mult_nn(p, n, r)
Definition p_polys.h:973
StringSetS
void StringSetS(const char *st)
Definition reporter.cc:128
StringAppendS
void StringAppendS(const char *st)
Definition reporter.cc:107
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
StringEndS
char * StringEndS()
Definition reporter.cc:151
ring.h
rField_is_Zp
static BOOLEAN rField_is_Zp(const ring r)
Definition ring.h:506
rIsPluralRing
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:406
rField_is_Domain
static BOOLEAN rField_is_Domain(const ring r)
Definition ring.h:493
kBucket_pt
kBucket * kBucket_pt
Definition ring.h:26
rParameter
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition ring.h:631
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:45
rField_is_Ring
#define rField_is_Ring(R)
Definition ring.h:491
p_mFirstVblock
int p_mFirstVblock(poly p, const ring ri)
Definition shiftop.cc:478
k_SplitFrame
void k_SplitFrame(poly &m1, poly &m2, int at, const ring r)
Definition shiftop.cc:600
shiftop.h
SI_LOG2
static int SI_LOG2(int v)
Definition si_log2.h:6
loop
#define loop
Definition structs.h:71
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836