My Project
Loading...
Searching...
No Matches
p_Mult_q.cc File Reference

Go to the source code of this file.

Macros

#define MIN_LENGTH_MAX   81
 
#define MIN_FLINT_QQ   60
 
#define MIN_FLINT_Zp   80
 
#define MIN_FLINT_Z   60
 

Functions

BOOLEAN pqLength (poly p, poly q, int &lp, int &lq, const int min)
 return TRUE and lp == pLength(p), lq == pLength(q), if min(pLength(p), pLength(q)) >= min FALSE if min(pLength(p), pLength(q)) < min and lp >= lq if pLength(p) >= pLength(lq) lp < lq if pLength(p) < pLength(q)
 
static void pqLengthApprox (poly p, poly q, int &lp, int &lq, const int min)
 
poly _p_Mult_q_Bucket (poly p, const int lp, poly q, const int lq, const int copy, const ring r)
 
poly _p_Mult_q_Normal_ZeroDiv (poly p, poly q, const int copy, const ring r)
 
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, !rIsPluralRing(r), nCoeff_is_Domain.
 

Macro Definition Documentation

◆ MIN_FLINT_QQ

#define MIN_FLINT_QQ   60

Definition at line 302 of file p_Mult_q.cc.

◆ MIN_FLINT_Z

#define MIN_FLINT_Z   60

Definition at line 304 of file p_Mult_q.cc.

◆ MIN_FLINT_Zp

#define MIN_FLINT_Zp   80

Definition at line 303 of file p_Mult_q.cc.

◆ MIN_LENGTH_MAX

#define MIN_LENGTH_MAX   81

Definition at line 301 of file p_Mult_q.cc.

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, !rIsPluralRing(r), nCoeff_is_Domain.

Definition at line 309 of file p_Mult_q.cc.

310{
311 assume(r != NULL);
312 int lp=0, lq=0;
313 poly pt;
314
315 BOOLEAN pure_polys=(p_GetComp(p,r)==0) && (p_GetComp(q,r)==0);
316 #ifdef HAVE_FLINT
317 #if __FLINT_RELEASE >= 20503
318 if (pure_polys)
319 {
321 if (lp < lq)
322 {
323 int l;
324 pt = p;
325 p = q;
326 q = pt;
327 l = lp;
328 lp = lq;
329 lq = l;
330 }
331 if ((lq>MIN_FLINT_QQ) && rField_is_Q(r))
332 {
333 fmpq_mpoly_ctx_t ctx;
334 if (!convSingRFlintR(ctx,r))
335 {
336 // lq is a lower bound for the length of p and q
337 poly res=Flint_Mult_MP(p,lq,q,lq,ctx,r);
338 if (!copy)
339 {
340 p_Delete(&p,r);
341 p_Delete(&q,r);
342 }
343 return res;
344 }
345 }
346 else if ((lq>MIN_FLINT_Zp) && rField_is_Zp(r))
347 {
348 nmod_mpoly_ctx_t ctx;
349 if (!convSingRFlintR(ctx,r))
350 {
351 // lq is a lower bound for the length of p and q
352 poly res=Flint_Mult_MP(p,lq,q,lq,ctx,r);
353 if (!copy)
354 {
355 p_Delete(&p,r);
356 p_Delete(&q,r);
357 }
358 return res;
359 }
360 }
361 else if ((lq>MIN_FLINT_Z) && rField_is_Z(r))
362 {
363 fmpz_mpoly_ctx_t ctx;
364 if (!convSingRFlintR(ctx,r))
365 {
366 // lq is a lower bound for the length of p and q
367 poly res=Flint_Mult_MP(p,lq,q,lq,ctx,r);
368 if (!copy)
369 {
370 p_Delete(&p,r);
371 p_Delete(&q,r);
372 }
373 return res;
374 }
375 }
376 }
377 #endif
378 #endif
379 if (lp==0)
381 if (lp < lq)
382 {
383 int l;
384 pt = p;
385 p = q;
386 q = pt;
387 l = lp;
388 lp = lq;
389 lq = l;
390 }
392 return _p_Mult_q_Normal(p, q, copy, r);
393 #if 0
394 else if (pure_polys
395 && ((r->cf->extRing==NULL)||(r->cf->extRing->qideal!=NULL))
396 /* exclude trans. extensions: may contain rat.funct as cf */
397 && (lq >= MIN_LENGTH_FACTORY)
398 && (r->cf->convSingNFactoryN!=ndConvSingNFactoryN))
399 {
400 poly h=singclap_pmult(p,q,r);
401 if (!copy)
402 {
403 p_Delete(&p,r);
404 p_Delete(&q,r);
405 }
406 return h;
407 }
408 #endif
409 else
410 {
411 lp=pLength(p);
412 lq=pLength(q);
413 if (lp < lq)
414 {
415 int l;
416 pt = p;
417 p = q;
418 q = pt;
419 l = lp;
420 lp = lq;
421 lq = l;
422 }
423 return _p_Mult_q_Bucket(p, lp, q, lq, copy, r);
424 }
425}
int BOOLEAN
Definition auxiliary.h:88
int l
Definition cfEzgcd.cc:100
int p
Definition cfModGcd.cc:4086
poly singclap_pmult(poly f, poly g, const ring r)
Definition clapsing.cc:577
CanonicalForm res
Definition facAbsFact.cc:60
CFArray copy(const CFList &list)
write elements of list into an array
STATIC_VAR Poly * h
Definition janet.cc:971
#define assume(x)
Definition mod2.h:389
#define p_GetComp(p, r)
Definition monomials.h:64
Definition lq.h:40
CanonicalForm ndConvSingNFactoryN(number, BOOLEAN, const coeffs)
Definition numbers.cc:307
#define NULL
Definition omList.c:12
#define TEST_OPT_NOT_BUCKETS
Definition options.h:107
static void pqLengthApprox(poly p, poly q, int &lp, int &lq, const int min)
Definition p_Mult_q.cc:69
poly _p_Mult_q_Normal(poly p, poly q, const int copy, const ring r)
Definition p_Mult_q.cc:223
#define MIN_FLINT_Z
Definition p_Mult_q.cc:304
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:100
#define MIN_LENGTH_MAX
Definition p_Mult_q.cc:301
#define MIN_FLINT_QQ
Definition p_Mult_q.cc:302
#define MIN_FLINT_Zp
Definition p_Mult_q.cc:303
#define MIN_LENGTH_BUCKET
Definition p_Mult_q.h:21
static int pLength(poly a)
Definition p_polys.h:190
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:515
static BOOLEAN rField_is_Zp(const ring r)
Definition ring.h:506
static BOOLEAN rField_is_Q(const ring r)
Definition ring.h:512

◆ _p_Mult_q_Bucket()

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

Definition at line 100 of file p_Mult_q.cc.

103{
104 assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
107 assume(lp >= 1 && lq >= 1);
108 p_Test(p, r);
109 p_Test(q, r);
110
111 poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
112 poly qq = pNext(q); // we iter of this
113 poly qn = pp_Mult_mm(qq, p,r); // holds p1*qi
114 poly pp = pNext(p); // used for Lm(qq)*pp
115 poly rr = res; // last monom which is surely not NULL
116 poly rn = pNext(res); // pNext(rr)
117 number n, n1;
118
119 kBucket_pt bucket = kBucketCreate(r);
120
121 // initialize bucket
122 kBucketInit(bucket, pNext(rn), lp - 2);
123 pNext(rn) = NULL;
124
125 // now the main loop
126 Top:
127 if (rn == NULL) goto Smaller;
128 p_LmCmpAction(rn, qn, r, goto Equal, goto Greater, goto Smaller);
129
130 Greater:
131 // rn > qn, so iter
132 rr = rn;
133 pNext(rn) = kBucketExtractLm(bucket);
134 pIter(rn);
135 goto Top;
136
137 // rn < qn, append qn to rr, and compute next Lm(qq)*pp
138 Smaller:
139 pNext(rr) = qn;
140 rr = qn;
141 pIter(qn);
142 Work: // compute res + Lm(qq)*pp
143 if (rn == NULL)
144 {
145 pNext(rr) = pp_Mult_mm(pp, qq, r);
146 kBucketInit(bucket, pNext(pNext(rr)), lp - 2);
147 pNext(pNext(rr)) = NULL;
148 }
149 else
150 {
151 kBucketSetLm(bucket, rn);
152 kBucket_Plus_mm_Mult_pp(bucket, qq, pp, lp - 1);
153 pNext(rr) = kBucketExtractLm(bucket);
154 }
155
156 pIter(qq);
157 if (qq == NULL) goto Finish;
158 rn = pNext(rr);
159 goto Top;
160
161 Equal:
162 n1 = pGetCoeff(rn);
163 n = n_Add(n1, pGetCoeff(qn), r->cf);
164 n_Delete(&n1, r->cf);
165 if (n_IsZero(n, r->cf))
166 {
167 n_Delete(&n, r->cf);
168 p_LmFree(rn, r);
169 }
170 else
171 {
172 pSetCoeff0(rn, n);
173 rr = rn;
174 }
175 rn = kBucketExtractLm(bucket);
176 n_Delete(&pGetCoeff(qn),r->cf);
177 qn = p_LmFreeAndNext(qn, r);
178 goto Work;
179
180 Finish:
181 assume(rr != NULL && pNext(rr) != NULL);
182 pNext(pNext(rr)) = kBucketClear(bucket);
183 kBucketDestroy(&bucket);
184
185 if (!copy)
186 {
187 p_Delete(&p, r);
188 p_Delete(&q, r);
189 }
190 p_Test(res, r);
191 return res;
192}
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition cf_gcd.cc:676
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:651
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:468
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:459
static BOOLEAN Equal(number a, number b, const coeffs)
Definition flintcf_Q.cc:381
static bool Greater(mono_type m1, mono_type m2)
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition kbuckets.cc:521
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition kbuckets.cc:216
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition kbuckets.cc:493
poly kBucketExtractLm(kBucket_pt bucket)
Definition kbuckets.cc:511
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition kbuckets.cc:209
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
void kBucketSetLm(kBucket_pt bucket, poly lm)
#define pIter(p)
Definition monomials.h:37
#define pNext(p)
Definition monomials.h:36
#define pAssume1(cond)
Definition monomials.h:171
#define pSetCoeff0(p, n)
Definition monomials.h:59
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
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition p_polys.h:1033
#define p_LmCmpAction(p, q, r, actionE, actionG, actionS)
Definition p_polys.h:1735
static poly p_LmFreeAndNext(poly p, ring)
Definition p_polys.h:713
static void p_LmFree(poly p, ring)
Definition p_polys.h:685
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition pDebug.cc:174
#define p_Test(p, r)
Definition p_polys.h:161
static BOOLEAN rField_is_Domain(const ring r)
Definition ring.h:493
kBucket * kBucket_pt
Definition ring.h:26
#define rField_is_Ring(R)
Definition ring.h:491

◆ _p_Mult_q_Normal()

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

Definition at line 223 of file p_Mult_q.cc.

224{
225 assume(r != NULL);
226 assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
227#ifdef HAVE_RINGS
228 assume(nCoeff_is_Domain(r->cf));
229#endif
230 pAssume1(! p_HaveCommonMonoms(p, q, r));
231 p_Test(p, r);
232 p_Test(q, r);
233
234 poly res = pp_Mult_mm(p,q,r); // holds initially q1*p
235 poly qq = pNext(q); // we iter of this
236 poly qn = pp_Mult_mm(qq, p,r); // holds p1*qi
237 poly pp = pNext(p); // used for Lm(qq)*pp
238 poly rr = res; // last monom which is surely not NULL
239 poly rn = pNext(res); // pNext(rr)
240 number n, n1;
241
242 // now the main loop
243 Top:
244 if (rn == NULL) goto Smaller;
245 p_LmCmpAction(rn, qn, r, goto Equal, goto Greater, goto Smaller);
246
247 Greater:
248 // rn > qn, so iter
249 rr = rn;
250 pIter(rn);
251 goto Top;
252
253 // rn < qn, append qn to rr, and compute next Lm(qq)*pp
254 Smaller:
255 pNext(rr) = qn;
256 rr = qn;
257 pIter(qn);
258
259 Work: // compute res + Lm(qq)*pp
260 if (rn == NULL)
261 pNext(rr) = pp_Mult_mm(pp, qq, r);
262 else
263 {
264 pNext(rr) = p_Plus_mm_Mult_qq(rn, qq, pp, r);
265 }
266
267 pIter(qq);
268 if (qq == NULL) goto Finish;
269 rn = pNext(rr);
270 goto Top;
271
272 Equal:
273 n1 = pGetCoeff(rn);
274 n = n_Add(n1, pGetCoeff(qn), r->cf);
275 n_Delete(&n1, r->cf);
276 if (n_IsZero(n, r->cf))
277 {
278 n_Delete(&n, r->cf);
279 rn = p_LmFreeAndNext(rn, r);
280 }
281 else
282 {
283 pSetCoeff0(rn, n);
284 rr = rn;
285 pIter(rn);
286 }
287 n_Delete(&pGetCoeff(qn),r->cf);
288 qn = p_LmFreeAndNext(qn, r);
289 goto Work;
290
291 Finish:
292 if (!copy)
293 {
294 p_Delete(&p, r);
295 p_Delete(&q, r);
296 }
297 p_Test(res, r);
298 return res;
299}
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:734
static poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq, const ring r)
Definition p_polys.h:1199

◆ _p_Mult_q_Normal_ZeroDiv()

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

Definition at line 195 of file p_Mult_q.cc.

196{
197 assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
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
205 while (qq != NULL)
206 {
207 res = p_Plus_mm_Mult_qq(res, qq, p, r);
208 pIter(qq);
209 }
210
211 if (!copy)
212 {
213 p_Delete(&p, r);
214 p_Delete(&q, r);
215 }
216
217 p_Test(res, r);
218
219 return res;
220}

◆ pqLength()

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

return TRUE and lp == pLength(p), lq == pLength(q), if min(pLength(p), pLength(q)) >= min FALSE if min(pLength(p), pLength(q)) < min and lp >= lq if pLength(p) >= pLength(lq) lp < lq if pLength(p) < pLength(q)

Definition at line 31 of file p_Mult_q.cc.

32{
33 int l = 0;
34
35 do
36 {
37 if (p == NULL)
38 {
39 lp = l;
40 if (l < min)
41 {
42 if (q != NULL)
43 lq = l+1;
44 else
45 lq = l;
46 return FALSE;
47 }
48 lq = l + pLength(q);
49 return TRUE;
50 }
51 pIter(p);
52 if (q == NULL)
53 {
54 lq = l;
55 if (l < min)
56 {
57 lp = l+1;
58 return FALSE;
59 }
60 lp = l + 1 + pLength(p);
61 return TRUE;
62 }
63 pIter(q);
64 l++;
65 }
66 while (1);
67}
#define TRUE
Definition auxiliary.h:101
#define FALSE
Definition auxiliary.h:97
static int min(int a, int b)
Definition fast_mult.cc:268

◆ pqLengthApprox()

static void pqLengthApprox ( poly p,
poly q,
int & lp,
int & lq,
const int min )
static

Definition at line 69 of file p_Mult_q.cc.

70{
71 int l = 0;
72
73 do
74 {
75 if (p == NULL)
76 {
77 lp=l;
78 lq=l+(q!=NULL);
79 return;
80 }
81 if (q == NULL) /* && p!=NULL */
82 {
83 lp=l+1;
84 lq=l;
85 return;
86 }
87 if (l>min) /* && p,q!=NULL */
88 {
89 lp=l; lq=l;
90 return;
91 }
92 pIter(p);
93 pIter(q);
94 l++;
95 }
96 while (1);
97}