My Project  UNKNOWN_GIT_VERSION
p_Mult_q.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /***************************************************************
5  * File: p_Mult_q.cc
6  * Purpose: multiplication of polynomials
7  * Author: obachman (Olaf Bachmann)
8  * Created: 8/00
9  *******************************************************************/
10 
11 #include "misc/auxiliary.h"
12 #include "factory/factory.h"
13 
14 #include "misc/options.h"
15 
16 #include "coeffs/numbers.h"
18 #include "polys/kbuckets.h"
19 #include "polys/clapsing.h"
20 
25 
26 #include "p_Mult_q.h"
27 
28 
29 BOOLEAN pqLength(poly p, poly q, int &lp, int &lq, const int min)
30 {
31  int l = 0;
32 
33  do
34  {
35  if (p == NULL)
36  {
37  lp = l;
38  if (l < min)
39  {
40  if (q != NULL)
41  lq = l+1;
42  else
43  lq = l;
44  return FALSE;
45  }
46  lq = l + pLength(q);
47  return TRUE;
48  }
49  pIter(p);
50  if (q == NULL)
51  {
52  lq = l;
53  if (l < min)
54  {
55  lp = l+1;
56  return FALSE;
57  }
58  lp = l + 1 + pLength(p);
59  return TRUE;
60  }
61  pIter(q);
62  l++;
63  }
64  while (1);
65 }
66 
67 
68 static poly _p_Mult_q_Bucket(poly p, const int lp,
69  poly q, const int lq,
70  const int copy, const ring r)
71 {
72  assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
75  assume(lp >= 1 && lq >= 1);
76  p_Test(p, r);
77  p_Test(q, r);
78 
79  poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
80  poly qq = pNext(q); // we iter of this
81  poly qn = pp_Mult_mm(qq, p,r); // holds p1*qi
82  poly pp = pNext(p); // used for Lm(qq)*pp
83  poly rr = res; // last monom which is surely not NULL
84  poly rn = pNext(res); // pNext(rr)
85  number n, n1;
86 
87  kBucket_pt bucket = kBucketCreate(r);
88 
89  // initialize bucket
90  kBucketInit(bucket, pNext(rn), lp - 2);
91  pNext(rn) = NULL;
92 
93  // now the main loop
94  Top:
95  if (rn == NULL) goto Smaller;
96  p_LmCmpAction(rn, qn, r, goto Equal, goto Greater, goto Smaller);
97 
98  Greater:
99  // rn > qn, so iter
100  rr = rn;
101  pNext(rn) = kBucketExtractLm(bucket);
102  pIter(rn);
103  goto Top;
104 
105  // rn < qn, append qn to rr, and compute next Lm(qq)*pp
106  Smaller:
107  pNext(rr) = qn;
108  rr = qn;
109  pIter(qn);
110  Work: // compute res + Lm(qq)*pp
111  if (rn == NULL)
112  {
113  pNext(rr) = pp_Mult_mm(pp, qq, r);
114  kBucketInit(bucket, pNext(pNext(rr)), lp - 2);
115  pNext(pNext(rr)) = NULL;
116  }
117  else
118  {
119  kBucketSetLm(bucket, rn);
120  kBucket_Plus_mm_Mult_pp(bucket, qq, pp, lp - 1);
121  pNext(rr) = kBucketExtractLm(bucket);
122  }
123 
124  pIter(qq);
125  if (qq == NULL) goto Finish;
126  rn = pNext(rr);
127  goto Top;
128 
129  Equal:
130  n1 = pGetCoeff(rn);
131  n = n_Add(n1, pGetCoeff(qn), r->cf);
132  n_Delete(&n1, r->cf);
133  if (n_IsZero(n, r->cf))
134  {
135  n_Delete(&n, r->cf);
136  p_LmFree(rn, r);
137  }
138  else
139  {
140  pSetCoeff0(rn, n);
141  rr = rn;
142  }
143  rn = kBucketExtractLm(bucket);
144  n_Delete(&pGetCoeff(qn),r->cf);
145  qn = p_LmFreeAndNext(qn, r);
146  goto Work;
147 
148  Finish:
149  assume(rr != NULL && pNext(rr) != NULL);
150  pNext(pNext(rr)) = kBucketClear(bucket);
151  kBucketDestroy(&bucket);
152 
153  if (!copy)
154  {
155  p_Delete(&p, r);
156  p_Delete(&q, r);
157  }
158  p_Test(res, r);
159  return res;
160 }
161 
162 #ifdef HAVE_RINGS
163 static poly _p_Mult_q_Normal_ZeroDiv(poly p, poly q, const int copy, const ring r)
164 {
165  assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
167  p_Test(p, r);
168  p_Test(q, r);
169 
170  poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
171  poly qq = pNext(q); // we iter of this
172 
173  while (qq != NULL)
174  {
175  res = p_Plus_mm_Mult_qq(res, qq, p, r);
176  pIter(qq);
177  }
178 
179  if (!copy)
180  {
181  p_Delete(&p, r);
182  p_Delete(&q, r);
183  }
184 
185  p_Test(res, r);
186 
187  return res;
188 }
189 #endif
190 
191 static poly _p_Mult_q_Normal(poly p, poly q, const int copy, const ring r)
192 {
193  assume(r != NULL);
194  assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
195 #ifdef HAVE_RINGS
196  assume(nCoeff_is_Domain(r->cf));
197 #endif
198  pAssume1(! p_HaveCommonMonoms(p, q, r));
199  p_Test(p, r);
200  p_Test(q, r);
201 
202  poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
203  poly qq = pNext(q); // we iter of this
204  poly qn = pp_Mult_mm(qq, p,r); // holds p1*qi
205  poly pp = pNext(p); // used for Lm(qq)*pp
206  poly rr = res; // last monom which is surely not NULL
207  poly rn = pNext(res); // pNext(rr)
208  number n, n1;
209 
210  // now the main loop
211  Top:
212  if (rn == NULL) goto Smaller;
213  p_LmCmpAction(rn, qn, r, goto Equal, goto Greater, goto Smaller);
214 
215  Greater:
216  // rn > qn, so iter
217  rr = rn;
218  pIter(rn);
219  goto Top;
220 
221  // rn < qn, append qn to rr, and compute next Lm(qq)*pp
222  Smaller:
223  pNext(rr) = qn;
224  rr = qn;
225  pIter(qn);
226 
227  Work: // compute res + Lm(qq)*pp
228  if (rn == NULL)
229  pNext(rr) = pp_Mult_mm(pp, qq, r);
230  else
231  {
232  pNext(rr) = p_Plus_mm_Mult_qq(rn, qq, pp, r);
233  }
234 
235  pIter(qq);
236  if (qq == NULL) goto Finish;
237  rn = pNext(rr);
238  goto Top;
239 
240  Equal:
241  n1 = pGetCoeff(rn);
242  n = n_Add(n1, pGetCoeff(qn), r->cf);
243  n_Delete(&n1, r->cf);
244  if (n_IsZero(n, r->cf))
245  {
246  n_Delete(&n, r->cf);
247  rn = p_LmFreeAndNext(rn, r);
248  }
249  else
250  {
251  pSetCoeff0(rn, n);
252  rr = rn;
253  pIter(rn);
254  }
255  n_Delete(&pGetCoeff(qn),r->cf);
256  qn = p_LmFreeAndNext(qn, r);
257  goto Work;
258 
259  Finish:
260  if (!copy)
261  {
262  p_Delete(&p, r);
263  p_Delete(&q, r);
264  }
265  p_Test(res, r);
266  return res;
267 }
268 
269 
270 /// Returns: p * q,
271 /// Destroys: if !copy then p, q
272 /// Assumes: pLength(p) >= 2 pLength(q) >=2
273 poly _p_Mult_q(poly p, poly q, const int copy, const ring r)
274 {
275  assume(r != NULL);
276 #ifdef HAVE_RINGS
277  if (!nCoeff_is_Domain(r->cf))
278  return _p_Mult_q_Normal_ZeroDiv(p, q, copy, r);
279 #endif
280  int lp, lq, l;
281  poly pt;
282 
283  pqLength(p, q, lp, lq, MIN_LENGTH_BUCKET);
284 
285  if (lp < lq)
286  {
287  pt = p;
288  p = q;
289  q = pt;
290  l = lp;
291  lp = lq;
292  lq = l;
293  }
295  return _p_Mult_q_Normal(p, q, copy, r);
296  else if ((lq >= MIN_LENGTH_FACTORY)
297  && (r->cf->convSingNFactoryN!=ndConvSingNFactoryN))
298  {
299  poly h=singclap_pmult(p,q,r);
300  if (!copy)
301  {
302  p_Delete(&p,r);
303  p_Delete(&q,r);
304  }
305  return h;
306  }
307  else
308  {
309  assume(lp == pLength(p));
310  assume(lq == pLength(q));
311  return _p_Mult_q_Bucket(p, lp, q, lq, copy, r);
312  }
313 }
_p_Mult_q_Normal
static poly _p_Mult_q_Normal(poly p, poly q, const int copy, const ring r)
Definition: p_Mult_q.cc:191
FALSE
#define FALSE
Definition: auxiliary.h:94
kBucketSetLm
void kBucketSetLm(kBucket_pt bucket, poly lm)
p_LmFreeAndNext
static poly p_LmFreeAndNext(poly p, ring)
Definition: p_polys.h:704
Equal
static BOOLEAN Equal(number a, number b, const coeffs r)
Definition: flintcf_Q.cc:323
p_Procs.h
_p_Mult_q_Normal_ZeroDiv
static poly _p_Mult_q_Normal_ZeroDiv(poly p, poly q, const int copy, const ring r)
Definition: p_Mult_q.cc:163
rField_is_Domain
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:478
lq
Definition: lq.h:40
MIN_LENGTH_BUCKET
#define MIN_LENGTH_BUCKET
Definition: p_Mult_q.h:21
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:1120
pqLength
BOOLEAN pqLength(poly p, poly q, int &lp, int &lq, const int min)
Definition: p_Mult_q.cc:29
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
p_Test
#define p_Test(p, r)
Definition: p_polys.h:164
p_MemAdd.h
options.h
pp_Mult_mm
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:988
auxiliary.h
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:464
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:193
Greater
static bool Greater(mono_type m1, mono_type m2)
Definition: interpolation.cc:285
n_Add
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
Definition: coeffs.h:656
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:508
TRUE
#define TRUE
Definition: auxiliary.h:98
res
CanonicalForm res
Definition: facAbsFact.cc:64
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:213
TEST_OPT_NOT_BUCKETS
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:104
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:490
clapsing.h
_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)
Definition: p_Mult_q.cc:68
rField_is_Ring
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:475
h
static Poly * h
Definition: janet.cc:972
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:818
p_Mult_q.h
p_MemCopy.h
pIter
#define pIter(p)
Definition: monomials.h:38
p_polys.h
pp
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:518
singclap_pmult
poly singclap_pmult(poly f, poly g, const ring r)
Definition: clapsing.cc:510
kbuckets.h
p_LmFree
static void p_LmFree(poly p, ring)
Definition: p_polys.h:684
p_LmCmpAction
#define p_LmCmpAction(p, q, r, actionE, actionG, actionS)
Definition: p_polys.h:1645
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:858
min
static int min(int a, int b)
Definition: fast_mult.cc:268
pAssume1
#define pAssume1(cond)
Definition: monomials.h:172
pSetCoeff0
#define pSetCoeff0(p, n)
Definition: monomials.h:60
_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: p_Mult_q.cc:273
MIN_LENGTH_FACTORY
#define MIN_LENGTH_FACTORY
Definition: p_Mult_q.h:27
assume
#define assume(x)
Definition: mod2.h:390
NULL
#define NULL
Definition: omList.c:10
l
int l
Definition: cfEzgcd.cc:93
kBucket
Definition: kbuckets.h:179
p
int p
Definition: cfModGcd.cc:4019
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:206
ndConvSingNFactoryN
CanonicalForm ndConvSingNFactoryN(number, BOOLEAN, const coeffs)
Definition: numbers.cc:273
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:45
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition: facFqBivarUtil.cc:364
pHaveCommonMonoms
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition: pDebug.cc:175
numbers.h
pNext
#define pNext(p)
Definition: monomials.h:37
p_MemCmp.h
nCoeff_is_Domain
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:761