Functions
p_Mult_q.cc File Reference
#include <misc/auxiliary.h>
#include <factory/factory.h>
#include <misc/options.h>
#include <polys/monomials/p_polys.h>
#include <polys/kbuckets.h>
#include <polys/templates/p_Procs.h>
#include <polys/templates/p_MemCmp.h>
#include <polys/templates/p_MemAdd.h>
#include <polys/templates/p_MemCopy.h>
#include "p_Mult_q.h"

Go to the source code of this file.

Functions

BOOLEAN pqLength (poly p, poly q, int &lp, int &lq, const int min)
 
static poly _p_Mult_q_Bucket (poly p, const int lp, poly q, const int lq, const int copy, const ring r)
 
static poly _p_Mult_q_Normal_ZeroDiv (poly p, poly q, const int copy, const ring r)
 
static poly _p_Mult_q_Normal (poly p, poly q, const int copy, const ring r)
 
poly _p_Mult_q (poly p, poly q, const int copy, const ring r)
 Returns: p * q, Destroys: if !copy then p, q Assumes: pLength(p) >= 2 pLength(q) >=2. More...
 

Function Documentation

§ _p_Mult_q()

poly _p_Mult_q ( poly  p,
poly  q,
const int  copy,
const ring  r 
)

Returns: p * q, Destroys: if !copy then p, q Assumes: pLength(p) >= 2 pLength(q) >=2.

Definition at line 271 of file p_Mult_q.cc.

272 {
273  assume(r != NULL);
274 #ifdef HAVE_RINGS
275  if (!nCoeff_is_Domain(r->cf))
276  return _p_Mult_q_Normal_ZeroDiv(p, q, copy, r);
277 #endif
278  int lp, lq, l;
279  poly pt;
280 
281  pqLength(p, q, lp, lq, MIN_LENGTH_BUCKET);
282 
283  if (lp < lq)
284  {
285  pt = p;
286  p = q;
287  q = pt;
288  l = lp;
289  lp = lq;
290  lq = l;
291  }
293  return _p_Mult_q_Normal(p, q, copy, r);
294  else
295  {
296  assume(lp == pLength(p));
297  assume(lq == pLength(q));
298  return _p_Mult_q_Bucket(p, lp, q, lq, copy, r);
299  }
300 }
CFArray copy(const CFList &list)
write elements of list into an array
return P p
Definition: myNF.cc:203
#define MIN_LENGTH_BUCKET
Definition: p_Mult_q.h:22
static poly _p_Mult_q_Normal_ZeroDiv(poly p, poly q, const int copy, const ring r)
Definition: p_Mult_q.cc:161
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:100
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:394
static poly _p_Mult_q_Normal(poly p, poly q, const int copy, const ring r)
Definition: p_Mult_q.cc:189
static unsigned pLength(poly a)
Definition: p_polys.h:189
BOOLEAN pqLength(poly p, poly q, int &lp, int &lq, const int min)
Definition: p_Mult_q.cc:27
static FORCE_INLINE BOOLEAN nCoeff_is_Domain(const coeffs r)
returns TRUE, if r is a field or r has no zero divisors (i.e is a domain)
Definition: coeffs.h:773
#define NULL
Definition: omList.c:10
static poly _p_Mult_q_Bucket(poly p, const int lp, poly q, const int lq, const int copy, const ring r)
Definition: p_Mult_q.cc:66
polyrec * poly
Definition: hilb.h:10
int l
Definition: cfEzgcd.cc:94

§ _p_Mult_q_Bucket()

static poly _p_Mult_q_Bucket ( poly  p,
const int  lp,
poly  q,
const int  lq,
const int  copy,
const ring  r 
)
static

Definition at line 66 of file p_Mult_q.cc.

69 {
70  assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
73  assume(lp >= 1 && lq >= 1);
74  p_Test(p, r);
75  p_Test(q, r);
76 
77  poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
78  poly qq = pNext(q); // we iter of this
79  poly qn = pp_Mult_mm(qq, p,r); // holds p1*qi
80  poly pp = pNext(p); // used for Lm(qq)*pp
81  poly rr = res; // last monom which is surely not NULL
82  poly rn = pNext(res); // pNext(rr)
83  number n, n1;
84 
86 
87  // initialize bucket
88  kBucketInit(bucket, pNext(rn), lp - 2);
89  pNext(rn) = NULL;
90 
91  // now the main loop
92  Top:
93  if (rn == NULL) goto Smaller;
94  p_LmCmpAction(rn, qn, r, goto Equal, goto Greater, goto Smaller);
95 
96  Greater:
97  // rn > qn, so iter
98  rr = rn;
99  pNext(rn) = kBucketExtractLm(bucket);
100  pIter(rn);
101  goto Top;
102 
103  // rn < qn, append qn to rr, and compute next Lm(qq)*pp
104  Smaller:
105  pNext(rr) = qn;
106  rr = qn;
107  pIter(qn);
108  Work: // compute res + Lm(qq)*pp
109  if (rn == NULL)
110  {
111  pNext(rr) = pp_Mult_mm(pp, qq, r);
112  kBucketInit(bucket, pNext(pNext(rr)), lp - 2);
113  pNext(pNext(rr)) = NULL;
114  }
115  else
116  {
117  kBucketSetLm(bucket, rn);
118  kBucket_Plus_mm_Mult_pp(bucket, qq, pp, lp - 1);
119  pNext(rr) = kBucketExtractLm(bucket);
120  }
121 
122  pIter(qq);
123  if (qq == NULL) goto Finish;
124  rn = pNext(rr);
125  goto Top;
126 
127  Equal:
128  n1 = pGetCoeff(rn);
129  n = n_Add(n1, pGetCoeff(qn), r->cf);
130  n_Delete(&n1, r->cf);
131  if (n_IsZero(n, r->cf))
132  {
133  n_Delete(&n, r->cf);
134  p_LmFree(rn, r);
135  }
136  else
137  {
138  pSetCoeff0(rn, n);
139  rr = rn;
140  }
141  rn = kBucketExtractLm(bucket);
142  n_Delete(&pGetCoeff(qn),r->cf);
143  qn = p_LmFreeAndNext(qn, r);
144  goto Work;
145 
146  Finish:
147  assume(rr != NULL && pNext(rr) != NULL);
148  pNext(pNext(rr)) = kBucketClear(bucket);
149  kBucketDestroy(&bucket);
150 
151  if (!copy)
152  {
153  p_Delete(&p, r);
154  p_Delete(&q, r);
155  }
156  p_Test(res, r);
157  return res;
158 }
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:495
CFArray copy(const CFList &list)
write elements of list into an array
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:467
return P p
Definition: myNF.cc:203
static BOOLEAN Equal(number a, number b, const coeffs r)
Definition: flintcf_Q.cc:351
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:957
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:480
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition: pDebug.cc:174
static void p_LmFree(poly p, ring)
Definition: p_polys.h:678
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:485
poly pp
Definition: myNF.cc:296
#define pIter(p)
Definition: monomials.h:44
poly res
Definition: myNF.cc:322
const ring r
Definition: syzextra.cc:208
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:200
#define assume(x)
Definition: mod2.h:394
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:660
void kBucketSetLm(kBucket_pt bucket, poly lm)
P bucket
Definition: myNF.cc:79
static poly p_LmFreeAndNext(poly p, ring)
Definition: p_polys.h:698
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
#define p_Test(p, r)
Definition: p_polys.h:160
static bool Greater(mono_type m1, mono_type m2)
#define p_LmCmpAction(p, q, r, actionE, actionG, actionS)
Definition: p_polys.h:1607
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:477
#define NULL
Definition: omList.c:10
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:795
#define pNext(p)
Definition: monomials.h:43
#define pSetCoeff0(p, n)
Definition: monomials.h:67
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
polyrec * poly
Definition: hilb.h:10
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:193
#define pAssume1(cond)
Definition: monomials.h:179

§ _p_Mult_q_Normal()

static poly _p_Mult_q_Normal ( poly  p,
poly  q,
const int  copy,
const ring  r 
)
static

Definition at line 189 of file p_Mult_q.cc.

190 {
191  assume(r != NULL);
192  assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
193 #ifdef HAVE_RINGS
194  assume(nCoeff_is_Domain(r->cf));
195 #endif
196  pAssume1(! p_HaveCommonMonoms(p, q, r));
197  p_Test(p, r);
198  p_Test(q, r);
199 
200  poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
201  poly qq = pNext(q); // we iter of this
202  poly qn = pp_Mult_mm(qq, p,r); // holds p1*qi
203  poly pp = pNext(p); // used for Lm(qq)*pp
204  poly rr = res; // last monom which is surely not NULL
205  poly rn = pNext(res); // pNext(rr)
206  number n, n1;
207 
208  // now the main loop
209  Top:
210  if (rn == NULL) goto Smaller;
211  p_LmCmpAction(rn, qn, r, goto Equal, goto Greater, goto Smaller);
212 
213  Greater:
214  // rn > qn, so iter
215  rr = rn;
216  pIter(rn);
217  goto Top;
218 
219  // rn < qn, append qn to rr, and compute next Lm(qq)*pp
220  Smaller:
221  pNext(rr) = qn;
222  rr = qn;
223  pIter(qn);
224 
225  Work: // compute res + Lm(qq)*pp
226  if (rn == NULL)
227  pNext(rr) = pp_Mult_mm(pp, qq, r);
228  else
229  {
230  pNext(rr) = p_Plus_mm_Mult_qq(rn, qq, pp, r);
231  }
232 
233  pIter(qq);
234  if (qq == NULL) goto Finish;
235  rn = pNext(rr);
236  goto Top;
237 
238  Equal:
239  n1 = pGetCoeff(rn);
240  n = n_Add(n1, pGetCoeff(qn), r->cf);
241  n_Delete(&n1, r->cf);
242  if (n_IsZero(n, r->cf))
243  {
244  n_Delete(&n, r->cf);
245  rn = p_LmFreeAndNext(rn, r);
246  }
247  else
248  {
249  pSetCoeff0(rn, n);
250  rr = rn;
251  pIter(rn);
252  }
253  n_Delete(&pGetCoeff(qn),r->cf);
254  qn = p_LmFreeAndNext(qn, r);
255  goto Work;
256 
257  Finish:
258  if (!copy)
259  {
260  p_Delete(&p, r);
261  p_Delete(&q, r);
262  }
263  p_Test(res, r);
264  return res;
265 }
CFArray copy(const CFList &list)
write elements of list into an array
return P p
Definition: myNF.cc:203
static BOOLEAN Equal(number a, number b, const coeffs r)
Definition: flintcf_Q.cc:351
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:957
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
poly pp
Definition: myNF.cc:296
#define pIter(p)
Definition: monomials.h:44
poly res
Definition: myNF.cc:322
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:394
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:660
static poly p_LmFreeAndNext(poly p, ring)
Definition: p_polys.h:698
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
#define p_Test(p, r)
Definition: p_polys.h:160
static bool Greater(mono_type m1, mono_type m2)
#define p_LmCmpAction(p, q, r, actionE, actionG, actionS)
Definition: p_polys.h:1607
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
static FORCE_INLINE BOOLEAN nCoeff_is_Domain(const coeffs r)
returns TRUE, if r is a field or r has no zero divisors (i.e is a domain)
Definition: coeffs.h:773
#define NULL
Definition: omList.c:10
#define pNext(p)
Definition: monomials.h:43
#define pSetCoeff0(p, n)
Definition: monomials.h:67
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
polyrec * poly
Definition: hilb.h:10
#define pAssume1(cond)
Definition: monomials.h:179
static poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq, const ring r)
Definition: p_polys.h:1106

§ _p_Mult_q_Normal_ZeroDiv()

static poly _p_Mult_q_Normal_ZeroDiv ( poly  p,
poly  q,
const int  copy,
const ring  r 
)
static

Definition at line 161 of file p_Mult_q.cc.

162 {
163  assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
165  p_Test(p, r);
166  p_Test(q, r);
167 
168  poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
169  poly qq = pNext(q); // we iter of this
170 
171  while (qq != NULL)
172  {
173  res = p_Plus_mm_Mult_qq(res, qq, p, r);
174  pIter(qq);
175  }
176 
177  if (!copy)
178  {
179  p_Delete(&p, r);
180  p_Delete(&q, r);
181  }
182 
183  p_Test(res, r);
184 
185  return res;
186 }
CFArray copy(const CFList &list)
write elements of list into an array
return P p
Definition: myNF.cc:203
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:957
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition: pDebug.cc:174
#define pIter(p)
Definition: monomials.h:44
poly res
Definition: myNF.cc:322
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:394
#define p_Test(p, r)
Definition: p_polys.h:160
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
#define NULL
Definition: omList.c:10
#define pNext(p)
Definition: monomials.h:43
polyrec * poly
Definition: hilb.h:10
#define pAssume1(cond)
Definition: monomials.h:179
static poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq, const ring r)
Definition: p_polys.h:1106

§ pqLength()

BOOLEAN pqLength ( poly  p,
poly  q,
int &  lp,
int &  lq,
const int  min 
)

Definition at line 27 of file p_Mult_q.cc.

28 {
29  int l = 0;
30 
31  do
32  {
33  if (p == NULL)
34  {
35  lp = l;
36  if (l < min)
37  {
38  if (q != NULL)
39  lq = l+1;
40  else
41  lq = l;
42  return FALSE;
43  }
44  lq = l + pLength(q);
45  return TRUE;
46  }
47  pIter(p);
48  if (q == NULL)
49  {
50  lq = l;
51  if (l < min)
52  {
53  lp = l+1;
54  return FALSE;
55  }
56  lp = l + 1 + pLength(p);
57  return TRUE;
58  }
59  pIter(q);
60  l++;
61  }
62  while (1);
63 }
static int min(int a, int b)
Definition: fast_mult.cc:268
#define FALSE
Definition: auxiliary.h:94
return P p
Definition: myNF.cc:203
#define TRUE
Definition: auxiliary.h:98
#define pIter(p)
Definition: monomials.h:44
static unsigned pLength(poly a)
Definition: p_polys.h:189
#define NULL
Definition: omList.c:10
int l
Definition: cfEzgcd.cc:94