1 /*****************************************************************************\
2 * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file FLINTconvert.cc
5 *
6 * This file implements functions for conversion to FLINT (www.flintlib.org)
7 * and back.
8 *
9 * @author Martin Lee
10 *
11 **/
12 /*****************************************************************************/
13
14
15
16 #include <config.h>
17
18
19 #include "canonicalform.h"
20 #include "fac_util.h"
21 #include "cf_iter.h"
22 #include "cf_factory.h"
23 #include "gmpext.h"
24 #include "singext.h"
25 #include "cf_algorithm.h"
26
27 #ifdef HAVE_OMALLOC
28 #define Alloc(L) omAlloc(L)
29 #define Free(A,L) omFreeSize(A,L)
30 #else
31 #define Alloc(L) malloc(L)
32 #define Free(A,L) free(A)
33 #endif
34
35 #ifdef HAVE_FLINT
36 #ifdef HAVE_CSTDIO
37 #include <cstdio>
38 #else
39 #include <stdio.h>
40 #endif
41 #ifdef __cplusplus
42 extern "C"
43 {
44 #endif
45 #ifndef __GMP_BITS_PER_MP_LIMB
46 #define __GMP_BITS_PER_MP_LIMB GMP_LIMB_BITS
47 #endif
48 #include <flint/fmpz.h>
49 #include <flint/fmpq.h>
50 #include <flint/fmpz_poly.h>
51 #include <flint/fmpz_mod_poly.h>
52 #include <flint/nmod_poly.h>
53 #include <flint/fmpq_poly.h>
54 #include <flint/nmod_mat.h>
55 #include <flint/fmpz_mat.h>
56 #if ( __FLINT_RELEASE >= 20400)
57 #include <flint/fq.h>
58 #include <flint/fq_poly.h>
59 #include <flint/fq_nmod.h>
60 #include <flint/fq_nmod_poly.h>
61 #include <flint/fq_nmod_mat.h>
62 #endif
63 #if ( __FLINT_RELEASE >= 20503)
64 #include <flint/fmpq_mpoly.h>
65
66 // planed, but not yet in FLINT:
67 #if (__FLINT_RELEASE < 20700)
68 // helper for fq_nmod_t -> nmod_poly_t
fq_nmod_get_nmod_poly(nmod_poly_t a,const fq_nmod_t b,const fq_nmod_ctx_t ctx)69 static void fq_nmod_get_nmod_poly(nmod_poly_t a, const fq_nmod_t b, const fq_nmod_ctx_t ctx)
70 {
71 FLINT_ASSERT(b->mod.n == ctx->modulus->mod.n);
72 a->mod = ctx->modulus->mod;
73 nmod_poly_set(a, b);
74 }
75 #else
76 #include <flint/fq_nmod_mpoly.h>
77 #endif
78
79 #if (__FLINT_RELEASE < 20700)
80 // helper for nmod_poly_t -> fq_nmod_t
fq_nmod_set_nmod_poly(fq_nmod_t a,const nmod_poly_t b,const fq_nmod_ctx_t ctx)81 void fq_nmod_set_nmod_poly(fq_nmod_t a, const nmod_poly_t b, const fq_nmod_ctx_t ctx)
82 {
83 FLINT_ASSERT(a->mod.n == b->mod.n);
84 FLINT_ASSERT(a->mod.n == ctx->modulus->mod.n);
85 nmod_poly_set(a, b);
86 fq_nmod_reduce(a, ctx);
87 }
88 #else
fq_nmod_set_nmod_poly(fq_nmod_t a,const nmod_poly_t b,const fq_nmod_ctx_t ctx)89 void fq_nmod_set_nmod_poly(fq_nmod_t a, const nmod_poly_t b,
90 const fq_nmod_ctx_t ctx)
91 {
92 FLINT_ASSERT(a->mod.n == b->mod.n);
93 FLINT_ASSERT(a->mod.n == ctx->modulus->mod.n);
94
95 if (b->length <= 2*(ctx->modulus->length - 1))
96 {
97 nmod_poly_set(a, b);
98 fq_nmod_reduce(a, ctx);
99 }
100 else
101 {
102 nmod_poly_rem(a, b, ctx->modulus);
103 }
104 }
105 #endif
106
107
108 #endif
109 #ifdef __cplusplus
110 }
111 #endif
112
113 #include "FLINTconvert.h"
114
115 // assumes result to be uninitialiazed
convertCF2Fmpz(fmpz_t result,const CanonicalForm & f)116 void convertCF2Fmpz (fmpz_t result, const CanonicalForm& f)
117 {
118 if (f.isImm())
119 *result=f.intval();
120 else
121 {
122 mpz_t gmp_val;
123 f.mpzval(gmp_val);
124 fmpz_init(result);
125 fmpz_set_mpz (result, gmp_val);
126 mpz_clear (gmp_val);
127 }
128 }
129
130 // special version assuming result is already initialized
convertCF2initFmpz(fmpz_t result,const CanonicalForm & f)131 void convertCF2initFmpz (fmpz_t result, const CanonicalForm& f)
132 {
133 if (f.isImm())
134 fmpz_set_si (result, f.intval());
135 else
136 {
137 mpz_t gmp_val;
138 f.mpzval(gmp_val);
139
140 mpz_swap(gmp_val, _fmpz_promote(result));
141 _fmpz_demote_val(result);
142
143 mpz_clear (gmp_val);
144 }
145 }
146
convertFacCF2Fmpz_poly_t(fmpz_poly_t result,const CanonicalForm & f)147 void convertFacCF2Fmpz_poly_t (fmpz_poly_t result, const CanonicalForm& f)
148 {
149 fmpz_poly_init2 (result, degree (f)+1);
150 _fmpz_poly_set_length(result, degree(f)+1);
151 for (CFIterator i= f; i.hasTerms(); i++)
152 convertCF2initFmpz (fmpz_poly_get_coeff_ptr(result, i.exp()), i.coeff()); // assumes initialized
153 }
154
convertFmpz2CF(const fmpz_t coefficient)155 CanonicalForm convertFmpz2CF (const fmpz_t coefficient)
156 {
157 if(!COEFF_IS_MPZ(*coefficient)
158 && (fmpz_cmp_si (coefficient, MINIMMEDIATE) >= 0)
159 && (fmpz_cmp_si (coefficient, MAXIMMEDIATE) <= 0))
160 {
161 long coeff= fmpz_get_si (coefficient);
162 return CanonicalForm (coeff);
163 }
164 else
165 {
166 mpz_t gmp_val;
167 mpz_init (gmp_val);
168 fmpz_get_mpz (gmp_val, coefficient);
169 CanonicalForm result= CanonicalForm (CFFactory::basic (gmp_val));
170 return result;
171 }
172 }
173
174 CanonicalForm
convertFmpz_poly_t2FacCF(const fmpz_poly_t poly,const Variable & x)175 convertFmpz_poly_t2FacCF (const fmpz_poly_t poly, const Variable& x)
176 {
177 CanonicalForm result= 0;
178 fmpz* coeff;
179 for (int i= 0; i < fmpz_poly_length (poly); i++)
180 {
181 coeff= fmpz_poly_get_coeff_ptr (poly, i);
182 if (!fmpz_is_zero (coeff))
183 result += convertFmpz2CF (coeff)*power (x,i);
184 }
185 return result;
186 }
187
188 void
convertFacCF2nmod_poly_t(nmod_poly_t result,const CanonicalForm & f)189 convertFacCF2nmod_poly_t (nmod_poly_t result, const CanonicalForm& f)
190 {
191 bool save_sym_ff= isOn (SW_SYMMETRIC_FF);
192 if (save_sym_ff) Off (SW_SYMMETRIC_FF);
193 nmod_poly_init2 (result, getCharacteristic(), degree (f)+1);
194 for (CFIterator i= f; i.hasTerms(); i++)
195 {
196 CanonicalForm c= i.coeff();
197 if (!c.isImm()) c=c.mapinto(); //c%= getCharacteristic();
198 if (!c.isImm())
199 { //This case will never happen if the characteristic is in fact a prime
200 // number, since all coefficients are represented as immediates
201 printf("convertCF2nmod_poly_t: coefficient not immediate!, char=%d\n",
202 getCharacteristic());
203 }
204 else
205 nmod_poly_set_coeff_ui (result, i.exp(), c.intval());
206 }
207 if (save_sym_ff) On (SW_SYMMETRIC_FF);
208 }
209
210 CanonicalForm
convertnmod_poly_t2FacCF(const nmod_poly_t poly,const Variable & x)211 convertnmod_poly_t2FacCF (const nmod_poly_t poly, const Variable& x)
212 {
213 CanonicalForm result= 0;
214 for (int i= 0; i < nmod_poly_length (poly); i++)
215 {
216 ulong coeff= nmod_poly_get_coeff_ui (poly, i);
217 if (coeff != 0)
218 result += CanonicalForm ((long)coeff)*power (x,i);
219 }
220 return result;
221 }
222
convertCF2Fmpq(fmpq_t result,const CanonicalForm & f)223 void convertCF2Fmpq (fmpq_t result, const CanonicalForm& f)
224 {
225 //ASSERT (isOn (SW_RATIONAL), "expected rational");
226 if (f.isImm ())
227 {
228 fmpq_set_si (result, f.intval(), 1);
229 }
230 else if(f.inQ())
231 {
232 mpz_t gmp_val;
233 gmp_numerator (f, gmp_val);
234 fmpz_set_mpz (fmpq_numref (result), gmp_val);
235 mpz_clear (gmp_val);
236 gmp_denominator (f, gmp_val);
237 fmpz_set_mpz (fmpq_denref (result), gmp_val);
238 mpz_clear (gmp_val);
239 }
240 else if(f.inZ())
241 {
242 mpz_t gmp_val;
243 f.mpzval(gmp_val);
244 fmpz_set_mpz (fmpq_numref (result), gmp_val);
245 mpz_clear (gmp_val);
246 fmpz_one(fmpq_denref(result));
247 }
248 else
249 {
250 printf("wrong type\n");
251 }
252 }
253
convertFmpq2CF(const fmpq_t q)254 CanonicalForm convertFmpq2CF (const fmpq_t q)
255 {
256 bool isRat= isOn (SW_RATIONAL);
257 if (!isRat)
258 On (SW_RATIONAL);
259
260 CanonicalForm num, den;
261 mpz_t nnum, nden;
262 mpz_init (nnum);
263 mpz_init (nden);
264 fmpz_get_mpz (nnum, fmpq_numref (q));
265 fmpz_get_mpz (nden, fmpq_denref (q));
266
267 CanonicalForm result;
268 if (mpz_is_imm (nden))
269 {
270 if (mpz_is_imm(nnum))
271 {
272 num= CanonicalForm (mpz_get_si(nnum));
273 den= CanonicalForm (mpz_get_si(nden));
274 mpz_clear (nnum);
275 mpz_clear (nden);
276 result= num/den;
277 }
278 else if (mpz_cmp_si(nden,1)==0)
279 {
280 result= CanonicalForm( CFFactory::basic(nnum));
281 mpz_clear (nden);
282 }
283 else
284 result= CanonicalForm( CFFactory::rational( nnum, nden, false));
285 }
286 else
287 {
288 result= CanonicalForm( CFFactory::rational( nnum, nden, false));
289 }
290 if (!isRat)
291 Off (SW_RATIONAL);
292 return result;
293 }
294
295 CanonicalForm
convertFmpq_poly_t2FacCF(const fmpq_poly_t p,const Variable & x)296 convertFmpq_poly_t2FacCF (const fmpq_poly_t p, const Variable& x)
297 {
298 CanonicalForm result= 0;
299 fmpq_t coeff;
300 long n= p->length;
301 for (long i= 0; i < n; i++)
302 {
303 fmpq_init (coeff);
304 fmpq_poly_get_coeff_fmpq (coeff, p, i);
305 if (fmpq_is_zero (coeff))
306 {
307 fmpq_clear (coeff);
308 continue;
309 }
310 result += convertFmpq2CF (coeff)*power (x, i);
311 fmpq_clear (coeff);
312 }
313 return result;
314 }
315
convertFacCF2Fmpz_array(fmpz * result,const CanonicalForm & f)316 void convertFacCF2Fmpz_array (fmpz* result, const CanonicalForm& f)
317 {
318 for (CFIterator i= f; i.hasTerms(); i++)
319 convertCF2initFmpz (&result[i.exp()], i.coeff()); // assumes initialized
320 }
321
convertFacCF2Fmpq_poly_t(fmpq_poly_t result,const CanonicalForm & f)322 void convertFacCF2Fmpq_poly_t (fmpq_poly_t result, const CanonicalForm& f)
323 {
324 bool isRat= isOn (SW_RATIONAL);
325 if (!isRat)
326 On (SW_RATIONAL);
327
328 fmpq_poly_init2 (result, degree (f)+1);
329 _fmpq_poly_set_length (result, degree (f) + 1);
330 CanonicalForm den= bCommonDen (f);
331 convertFacCF2Fmpz_array (fmpq_poly_numref (result), f*den);
332 convertCF2initFmpz (fmpq_poly_denref (result), den); // assumes initialized
333
334 if (!isRat)
335 Off (SW_RATIONAL);
336 }
337
338 CFFList
convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac,const mp_limb_t leadingCoeff,const Variable & x)339 convertFLINTnmod_poly_factor2FacCFFList (const nmod_poly_factor_t fac,
340 const mp_limb_t leadingCoeff,
341 const Variable& x
342 )
343 {
344 CFFList result;
345 if (leadingCoeff != 1)
346 result.insert (CFFactor (CanonicalForm ((long) leadingCoeff), 1));
347
348 long i;
349
350 for (i = 0; i < fac->num; i++)
351 result.append (CFFactor (convertnmod_poly_t2FacCF (
352 (nmod_poly_t &)fac->p[i],x),
353 fac->exp[i]));
354 return result;
355 }
356
357 #if __FLINT_RELEASE >= 20503
358 CFFList
convertFLINTfmpz_poly_factor2FacCFFList(const fmpz_poly_factor_t fac,const Variable & x)359 convertFLINTfmpz_poly_factor2FacCFFList (
360 const fmpz_poly_factor_t fac, ///< [in] a nmod_poly_factor_t
361 const Variable& x ///< [in] variable the result should
362 ///< have
363 )
364
365 {
366 CFFList result;
367 long i;
368
369 result.append (CFFactor(convertFmpz2CF(&fac->c),1));
370
371 for (i = 0; i < fac->num; i++)
372 result.append (CFFactor (convertFmpz_poly_t2FacCF (
373 (fmpz_poly_t &)fac->p[i],x),
374 fac->exp[i]));
375 return result;
376 }
377 #endif
378
379 #if __FLINT_RELEASE >= 20400
380 CFFList
convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac,const Variable & x,const Variable & alpha,const fq_nmod_ctx_t fq_con)381 convertFLINTFq_nmod_poly_factor2FacCFFList (const fq_nmod_poly_factor_t fac,
382 const Variable& x, const Variable& alpha,
383 const fq_nmod_ctx_t fq_con
384 )
385 {
386 CFFList result;
387
388 long i;
389
390 for (i = 0; i < fac->num; i++)
391 result.append (CFFactor (convertFq_nmod_poly_t2FacCF (
392 (fq_nmod_poly_t &)fac->poly[i], x, alpha, fq_con),
393 fac->exp[i]));
394 return result;
395 }
396 #endif
397
398 void
convertFacCF2Fmpz_mod_poly_t(fmpz_mod_poly_t result,const CanonicalForm & f,const fmpz_t p)399 convertFacCF2Fmpz_mod_poly_t (fmpz_mod_poly_t result, const CanonicalForm& f,
400 const fmpz_t p)
401 {
402 #if (__FLINT_RELEASE >= 20700)
403 fmpz_mod_ctx_t ctx;
404 fmpz_mod_ctx_init(ctx,p);
405 fmpz_mod_poly_init2 (result, degree (f) + 1, ctx);
406 #else
407 fmpz_mod_poly_init2 (result, p, degree (f) + 1);
408 #endif
409 fmpz_poly_t buf;
410 convertFacCF2Fmpz_poly_t (buf, f);
411 #if (__FLINT_RELEASE >= 20700)
412 fmpz_mod_poly_set_fmpz_poly (result, buf, ctx);
413 fmpz_mod_ctx_clear(ctx);
414 #else
415 fmpz_mod_poly_set_fmpz_poly (result, buf);
416 #endif
417 fmpz_poly_clear (buf);
418 }
419
420 CanonicalForm
convertFmpz_mod_poly_t2FacCF(const fmpz_mod_poly_t poly,const Variable & x,const modpk & b)421 convertFmpz_mod_poly_t2FacCF (const fmpz_mod_poly_t poly, const Variable& x,
422 const modpk& b)
423 {
424 fmpz_poly_t buf;
425 fmpz_poly_init (buf);
426 #if (__FLINT_RELEASE >= 20700)
427 fmpz_t FLINTp;
428 fmpz_init (FLINTp);
429 convertCF2initFmpz (FLINTp, b.getpk()); // assumes initialized
430 fmpz_mod_ctx_t ctx;
431 fmpz_mod_ctx_init(ctx,FLINTp);
432 fmpz_clear(FLINTp);
433 fmpz_mod_poly_get_fmpz_poly (buf, poly, ctx);
434 #else
435 fmpz_mod_poly_get_fmpz_poly (buf, poly);
436 #endif
437 CanonicalForm result= convertFmpz_poly_t2FacCF (buf, x);
438 fmpz_poly_clear (buf);
439 return b (result);
440 }
441
442 #if __FLINT_RELEASE >= 20400
443 void
convertFacCF2Fq_nmod_t(fq_nmod_t result,const CanonicalForm & f,const fq_nmod_ctx_t ctx)444 convertFacCF2Fq_nmod_t (fq_nmod_t result, const CanonicalForm& f,
445 const fq_nmod_ctx_t ctx)
446 {
447 bool save_sym_ff= isOn (SW_SYMMETRIC_FF);
448 if (save_sym_ff) Off (SW_SYMMETRIC_FF);
449 #if __FLINT_RELEASE >= 20503
450 nmod_poly_t res;
451 nmod_poly_init(res,getCharacteristic());
452 #endif
453 for (CFIterator i= f; i.hasTerms(); i++)
454 {
455 CanonicalForm c= i.coeff();
456 if (!c.isImm()) c=c.mapinto(); //c%= getCharacteristic();
457 if (!c.isImm())
458 { //This case will never happen if the characteristic is in fact a prime
459 // number, since all coefficients are represented as immediates
460 printf("convertFacCF2Fq_nmod_t: coefficient not immediate!, char=%d\n",
461 getCharacteristic());
462 }
463 else
464 {
465 STICKYASSERT (i.exp() <= fq_nmod_ctx_degree(ctx), "convertFacCF2Fq_nmod_t: element is not reduced");
466 #if __FLINT_RELEASE >= 20503
467 nmod_poly_set_coeff_ui (res, i.exp(), c.intval());
468 #else
469 nmod_poly_set_coeff_ui (result, i.exp(), c.intval());
470 #endif
471 }
472 }
473 #if __FLINT_RELEASE >= 20503
474 fq_nmod_init(result,ctx);
475 fq_nmod_set_nmod_poly(result,res,ctx);
476 #endif
477 if (save_sym_ff) On (SW_SYMMETRIC_FF);
478 }
479
480 CanonicalForm
convertFq_nmod_t2FacCF(const fq_nmod_t poly,const Variable & alpha,const fq_nmod_ctx_t ctx)481 convertFq_nmod_t2FacCF (const fq_nmod_t poly, const Variable& alpha, const fq_nmod_ctx_t ctx)
482 {
483 return convertnmod_poly_t2FacCF (poly, alpha);
484 }
485
486 void
convertFacCF2Fq_t(fq_t result,const CanonicalForm & f,const fq_ctx_t ctx)487 convertFacCF2Fq_t (fq_t result, const CanonicalForm& f, const fq_ctx_t ctx)
488 {
489 fmpz_poly_init2 (result, fq_ctx_degree(ctx));
490 _fmpz_poly_set_length(result, fq_ctx_degree(ctx));
491
492 for (CFIterator i= f; i.hasTerms(); i++)
493 {
494 ASSERT(i.exp() < result->length, "input is not reduced");
495 convertCF2initFmpz (fmpz_poly_get_coeff_ptr(result, i.exp()), i.coeff()); // assumes initialized
496 }
497
498 _fmpz_vec_scalar_mod_fmpz (result->coeffs, result->coeffs, result->length,
499 fq_ctx_prime(ctx));
500
501 _fmpz_poly_normalise (result);
502 }
503
504 CanonicalForm
convertFq_t2FacCF(const fq_t poly,const Variable & alpha)505 convertFq_t2FacCF (const fq_t poly, const Variable& alpha)
506 {
507 return convertFmpz_poly_t2FacCF (poly, alpha);
508 }
509
510 void
convertFacCF2Fq_poly_t(fq_poly_t result,const CanonicalForm & f,const fq_ctx_t ctx)511 convertFacCF2Fq_poly_t (fq_poly_t result, const CanonicalForm& f,
512 const fq_ctx_t ctx)
513 {
514 fq_poly_init2 (result, degree (f)+1, ctx);
515
516 _fq_poly_set_length (result, degree (f) + 1, ctx);
517
518 for (CFIterator i= f; i.hasTerms(); i++)
519 {
520 fq_t buf;
521 convertFacCF2Fq_t (buf, i.coeff(), ctx);
522 fq_poly_set_coeff (result, i.exp(), buf, ctx);
523 fq_clear (buf, ctx);
524 }
525 }
526
527 void
convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result,const CanonicalForm & f,const fq_nmod_ctx_t ctx)528 convertFacCF2Fq_nmod_poly_t (fq_nmod_poly_t result, const CanonicalForm& f,
529 const fq_nmod_ctx_t ctx)
530 {
531 fq_nmod_poly_init2 (result, degree (f)+1, ctx);
532 _fq_nmod_poly_set_length (result, degree (f) + 1, ctx);
533 fq_nmod_t buf;
534 fq_nmod_init2 (buf, ctx);
535 for (CFIterator i= f; i.hasTerms(); i++)
536 {
537 convertFacCF2Fq_nmod_t (buf, i.coeff(), ctx);
538 fq_nmod_poly_set_coeff (result, i.exp(), buf, ctx);
539 fq_nmod_zero (buf, ctx);
540 }
541 fq_nmod_clear (buf, ctx);
542 }
543
544 CanonicalForm
convertFq_poly_t2FacCF(const fq_poly_t p,const Variable & x,const Variable & alpha,const fq_ctx_t ctx)545 convertFq_poly_t2FacCF (const fq_poly_t p, const Variable& x,
546 const Variable& alpha, const fq_ctx_t ctx)
547 {
548 CanonicalForm result= 0;
549 fq_t coeff;
550 long n= fq_poly_length (p, ctx);
551 fq_init2 (coeff, ctx);
552 for (long i= 0; i < n; i++)
553 {
554 fq_poly_get_coeff (coeff, p, i, ctx);
555 if (fq_is_zero (coeff, ctx))
556 continue;
557 result += convertFq_t2FacCF (coeff, alpha)*power (x, i);
558 fq_zero (coeff, ctx);
559 }
560 fq_clear (coeff, ctx);
561
562 return result;
563 }
564
565 CanonicalForm
convertFq_nmod_poly_t2FacCF(const fq_nmod_poly_t p,const Variable & x,const Variable & alpha,const fq_nmod_ctx_t ctx)566 convertFq_nmod_poly_t2FacCF (const fq_nmod_poly_t p, const Variable& x,
567 const Variable& alpha, const fq_nmod_ctx_t ctx)
568 {
569 CanonicalForm result= 0;
570 fq_nmod_t coeff;
571 long n= fq_nmod_poly_length (p, ctx);
572 fq_nmod_init2 (coeff, ctx);
573 for (long i= 0; i < n; i++)
574 {
575 fq_nmod_poly_get_coeff (coeff, p, i, ctx);
576 if (fq_nmod_is_zero (coeff, ctx))
577 continue;
578 result += convertFq_nmod_t2FacCF (coeff, alpha, ctx)*power (x, i);
579 fq_nmod_zero (coeff, ctx);
580 }
581 fq_nmod_clear (coeff, ctx);
582
583 return result;
584 }
585 #endif
586
convertFacCFMatrix2Fmpz_mat_t(fmpz_mat_t M,const CFMatrix & m)587 void convertFacCFMatrix2Fmpz_mat_t (fmpz_mat_t M, const CFMatrix &m)
588 {
589 fmpz_mat_init (M, (long) m.rows(), (long) m.columns());
590
591 int i,j;
592 for(i=m.rows();i>0;i--)
593 {
594 for(j=m.columns();j>0;j--)
595 {
596 convertCF2initFmpz (fmpz_mat_entry (M,i-1,j-1), m(i,j)); // assumes initialized
597 }
598 }
599 }
convertFmpz_mat_t2FacCFMatrix(const fmpz_mat_t m)600 CFMatrix* convertFmpz_mat_t2FacCFMatrix(const fmpz_mat_t m)
601 {
602 CFMatrix *res=new CFMatrix(fmpz_mat_nrows (m),fmpz_mat_ncols (m));
603 int i,j;
604 for(i=res->rows();i>0;i--)
605 {
606 for(j=res->columns();j>0;j--)
607 {
608 (*res)(i,j)=convertFmpz2CF(fmpz_mat_entry (m,i-1,j-1));
609 }
610 }
611 return res;
612 }
613
convertFacCFMatrix2nmod_mat_t(nmod_mat_t M,const CFMatrix & m)614 void convertFacCFMatrix2nmod_mat_t (nmod_mat_t M, const CFMatrix &m)
615 {
616 nmod_mat_init (M, (long) m.rows(), (long) m.columns(), getCharacteristic());
617
618 bool save_sym_ff= isOn (SW_SYMMETRIC_FF);
619 if (save_sym_ff) Off (SW_SYMMETRIC_FF);
620 int i,j;
621 for(i=m.rows();i>0;i--)
622 {
623 for(j=m.columns();j>0;j--)
624 {
625 if(!(m(i,j)).isImm()) printf("convertFacCFMatrix2FLINTmat_zz_p: not imm.\n");
626 nmod_mat_entry (M,i-1,j-1)= (m(i,j)).intval();
627 }
628 }
629 if (save_sym_ff) On (SW_SYMMETRIC_FF);
630 }
631
convertNmod_mat_t2FacCFMatrix(const nmod_mat_t m)632 CFMatrix* convertNmod_mat_t2FacCFMatrix(const nmod_mat_t m)
633 {
634 CFMatrix *res=new CFMatrix(nmod_mat_nrows (m), nmod_mat_ncols (m));
635 int i,j;
636 for(i=res->rows();i>0;i--)
637 {
638 for(j=res->columns();j>0;j--)
639 {
640 (*res)(i,j)=CanonicalForm((long) nmod_mat_entry (m, i-1, j-1));
641 }
642 }
643 return res;
644 }
645
646 #if __FLINT_RELEASE >= 20400
647 void
convertFacCFMatrix2Fq_nmod_mat_t(fq_nmod_mat_t M,const fq_nmod_ctx_t fq_con,const CFMatrix & m)648 convertFacCFMatrix2Fq_nmod_mat_t (fq_nmod_mat_t M,
649 const fq_nmod_ctx_t fq_con, const CFMatrix &m)
650 {
651 fq_nmod_mat_init (M, (long) m.rows(), (long) m.columns(), fq_con);
652 int i,j;
653 for(i=m.rows();i>0;i--)
654 {
655 for(j=m.columns();j>0;j--)
656 {
657 convertFacCF2nmod_poly_t (M->rows[i-1]+j-1, m (i,j));
658 }
659 }
660 }
661
662 CFMatrix*
convertFq_nmod_mat_t2FacCFMatrix(const fq_nmod_mat_t m,const fq_nmod_ctx_t & fq_con,const Variable & alpha)663 convertFq_nmod_mat_t2FacCFMatrix(const fq_nmod_mat_t m,
664 const fq_nmod_ctx_t& fq_con,
665 const Variable& alpha)
666 {
667 CFMatrix *res=new CFMatrix(fq_nmod_mat_nrows (m, fq_con),
668 fq_nmod_mat_ncols (m, fq_con));
669 int i,j;
670 for(i=res->rows();i>0;i--)
671 {
672 for(j=res->columns();j>0;j--)
673 {
674 (*res)(i,j)=convertFq_nmod_t2FacCF (fq_nmod_mat_entry (m, i-1, j-1),
675 alpha, fq_con);
676 }
677 }
678 return res;
679 }
680 #endif
681 #if __FLINT_RELEASE >= 20503
convFlint_RecPP(const CanonicalForm & f,ulong * exp,nmod_mpoly_t result,nmod_mpoly_ctx_t ctx,int N)682 static void convFlint_RecPP ( const CanonicalForm & f, ulong * exp, nmod_mpoly_t result, nmod_mpoly_ctx_t ctx, int N )
683 {
684 // assume f!=0
685 if ( ! f.inCoeffDomain() )
686 {
687 int l = f.level();
688 for ( CFIterator i = f; i.hasTerms(); i++ )
689 {
690 exp[N-l] = i.exp();
691 convFlint_RecPP( i.coeff(), exp, result, ctx, N );
692 }
693 exp[N-l] = 0;
694 }
695 else
696 {
697 int c=f.intval(); // with Off(SW_SYMMETRIC_FF): 0<=c<p
698 nmod_mpoly_push_term_ui_ui(result,c,exp,ctx);
699 }
700 }
701
convFlint_RecPP(const CanonicalForm & f,ulong * exp,fmpq_mpoly_t result,fmpq_mpoly_ctx_t ctx,int N)702 static void convFlint_RecPP ( const CanonicalForm & f, ulong * exp, fmpq_mpoly_t result, fmpq_mpoly_ctx_t ctx, int N )
703 {
704 // assume f!=0
705 if ( ! f.inBaseDomain() )
706 {
707 int l = f.level();
708 for ( CFIterator i = f; i.hasTerms(); i++ )
709 {
710 exp[N-l] = i.exp();
711 convFlint_RecPP( i.coeff(), exp, result, ctx, N );
712 }
713 exp[N-l] = 0;
714 }
715 else
716 {
717 fmpq_t c;
718 fmpq_init(c);
719 convertCF2Fmpq(c,f);
720 fmpq_mpoly_push_term_fmpq_ui(result,c,exp,ctx);
721 fmpq_clear(c);
722 }
723 }
724
convFlint_RecPP(const CanonicalForm & f,ulong * exp,fmpz_mpoly_t result,fmpz_mpoly_ctx_t ctx,int N)725 static void convFlint_RecPP ( const CanonicalForm & f, ulong * exp, fmpz_mpoly_t result, fmpz_mpoly_ctx_t ctx, int N )
726 {
727 // assume f!=0
728 if ( ! f.inBaseDomain() )
729 {
730 int l = f.level();
731 for ( CFIterator i = f; i.hasTerms(); i++ )
732 {
733 exp[N-l] = i.exp();
734 convFlint_RecPP( i.coeff(), exp, result, ctx, N );
735 }
736 exp[N-l] = 0;
737 }
738 else
739 {
740 fmpz_t c;
741 fmpz_init(c);
742 convertCF2initFmpz(c,f); // assumes initialized
743 fmpz_mpoly_push_term_fmpz_ui(result,c,exp,ctx);
744 fmpz_clear(c);
745 }
746 }
747
748 #if __FLINT_RELEASE >= 20700
convFlint_RecPP(const CanonicalForm & f,ulong * exp,fq_nmod_mpoly_t result,const fq_nmod_mpoly_ctx_t ctx,int N,const fq_nmod_ctx_t fq_ctx)749 static void convFlint_RecPP ( const CanonicalForm & f, ulong * exp, fq_nmod_mpoly_t result, const fq_nmod_mpoly_ctx_t ctx, int N, const fq_nmod_ctx_t fq_ctx )
750 {
751 // assume f!=0
752 if ( ! f.inCoeffDomain() )
753 {
754 int l = f.level();
755 for ( CFIterator i = f; i.hasTerms(); i++ )
756 {
757 exp[N-l] = i.exp();
758 convFlint_RecPP( i.coeff(), exp, result, ctx, N, fq_ctx );
759 }
760 exp[N-l] = 0;
761 }
762 else
763 {
764 fq_nmod_t c;
765 convertFacCF2Fq_nmod_t (c, f, fq_ctx);
766 fq_nmod_mpoly_push_term_fq_nmod_ui(result,c,exp,ctx);
767 }
768 }
769 #endif
770
convFactoryPFlintMP(const CanonicalForm & f,nmod_mpoly_t res,nmod_mpoly_ctx_t ctx,int N)771 void convFactoryPFlintMP ( const CanonicalForm & f, nmod_mpoly_t res, nmod_mpoly_ctx_t ctx, int N )
772 {
773 if (f.isZero()) return;
774 ulong * exp = (ulong*)Alloc(N*sizeof(ulong));
775 memset(exp,0,N*sizeof(ulong));
776 bool save_sym_ff= isOn (SW_SYMMETRIC_FF);
777 if (save_sym_ff) Off (SW_SYMMETRIC_FF);
778 convFlint_RecPP( f, exp, res, ctx, N );
779 if (save_sym_ff) On(SW_SYMMETRIC_FF);
780 Free(exp,N*sizeof(ulong));
781 }
782
convFactoryPFlintMP(const CanonicalForm & f,fmpq_mpoly_t res,fmpq_mpoly_ctx_t ctx,int N)783 void convFactoryPFlintMP ( const CanonicalForm & f, fmpq_mpoly_t res, fmpq_mpoly_ctx_t ctx, int N )
784 {
785 if (f.isZero()) return;
786 ulong * exp = (ulong*)Alloc(N*sizeof(ulong));
787 memset(exp,0,N*sizeof(ulong));
788 convFlint_RecPP( f, exp, res, ctx, N );
789 fmpq_mpoly_reduce(res,ctx);
790 Free(exp,N*sizeof(ulong));
791 }
792
convFactoryPFlintMP(const CanonicalForm & f,fmpz_mpoly_t res,fmpz_mpoly_ctx_t ctx,int N)793 void convFactoryPFlintMP ( const CanonicalForm & f, fmpz_mpoly_t res, fmpz_mpoly_ctx_t ctx, int N )
794 {
795 if (f.isZero()) return;
796 ulong * exp = (ulong*)Alloc(N*sizeof(ulong));
797 memset(exp,0,N*sizeof(ulong));
798 convFlint_RecPP( f, exp, res, ctx, N );
799 //fmpz_mpoly_reduce(res,ctx);
800 Free(exp,N*sizeof(ulong));
801 }
802
803 #if __FLINT_RELEASE >= 20700
convFactoryPFlintMP(const CanonicalForm & f,fq_nmod_mpoly_t res,fq_nmod_mpoly_ctx_t ctx,int N,fq_nmod_ctx_t fq_ctx)804 void convFactoryPFlintMP ( const CanonicalForm & f, fq_nmod_mpoly_t res, fq_nmod_mpoly_ctx_t ctx, int N, fq_nmod_ctx_t fq_ctx )
805 {
806 if (f.isZero()) return;
807 ulong * exp = (ulong*)Alloc(N*sizeof(ulong));
808 memset(exp,0,N*sizeof(ulong));
809 bool save_sym_ff= isOn (SW_SYMMETRIC_FF);
810 if (save_sym_ff) Off (SW_SYMMETRIC_FF);
811 convFlint_RecPP( f, exp, res, ctx, N, fq_ctx );
812 if (save_sym_ff) On(SW_SYMMETRIC_FF);
813 Free(exp,N*sizeof(ulong));
814 }
815 #endif
816
convFlintMPFactoryP(nmod_mpoly_t f,nmod_mpoly_ctx_t ctx,int N)817 CanonicalForm convFlintMPFactoryP(nmod_mpoly_t f, nmod_mpoly_ctx_t ctx, int N)
818 {
819 CanonicalForm result;
820 int d=nmod_mpoly_length(f,ctx)-1;
821 ulong* exp=(ulong*)Alloc(N*sizeof(ulong));
822 for(int i=d; i>=0; i--)
823 {
824 ulong c=nmod_mpoly_get_term_coeff_ui(f,i,ctx);
825 nmod_mpoly_get_term_exp_ui(exp,f,i,ctx);
826 CanonicalForm term=(int)c;
827 for ( int i = 0; i <N; i++ )
828 {
829 if (exp[i]!=0) term*=CanonicalForm( Variable( N-i ), exp[i] );
830 }
831 result+=term;
832 }
833 Free(exp,N*sizeof(ulong));
834 return result;
835 }
836
convFlintMPFactoryP(fmpq_mpoly_t f,fmpq_mpoly_ctx_t ctx,int N)837 CanonicalForm convFlintMPFactoryP(fmpq_mpoly_t f, fmpq_mpoly_ctx_t ctx, int N)
838 {
839 CanonicalForm result;
840 int d=fmpq_mpoly_length(f,ctx)-1;
841 ulong* exp=(ulong*)Alloc(N*sizeof(ulong));
842 fmpq_t c;
843 fmpq_init(c);
844 for(int i=d; i>=0; i--)
845 {
846 fmpq_mpoly_get_term_coeff_fmpq(c,f,i,ctx);
847 fmpq_mpoly_get_term_exp_ui(exp,f,i,ctx);
848 CanonicalForm term=convertFmpq2CF(c);
849 for ( int i = 0; i <N; i++ )
850 {
851 if (exp[i]!=0) term*=CanonicalForm( Variable( N-i ), exp[i] );
852 }
853 result+=term;
854 }
855 fmpq_clear(c);
856 Free(exp,N*sizeof(ulong));
857 return result;
858 }
859
convFlintMPFactoryP(fmpz_mpoly_t f,fmpz_mpoly_ctx_t ctx,int N)860 CanonicalForm convFlintMPFactoryP(fmpz_mpoly_t f, fmpz_mpoly_ctx_t ctx, int N)
861 {
862 CanonicalForm result;
863 int d=fmpz_mpoly_length(f,ctx)-1;
864 ulong* exp=(ulong*)Alloc(N*sizeof(ulong));
865 fmpz_t c;
866 fmpz_init(c);
867 for(int i=d; i>=0; i--)
868 {
869 fmpz_mpoly_get_term_coeff_fmpz(c,f,i,ctx);
870 fmpz_mpoly_get_term_exp_ui(exp,f,i,ctx);
871 CanonicalForm term=convertFmpz2CF(c);
872 for ( int i = 0; i <N; i++ )
873 {
874 if (exp[i]!=0) term*=CanonicalForm( Variable( N-i ), exp[i] );
875 }
876 result+=term;
877 }
878 fmpz_clear(c);
879 Free(exp,N*sizeof(ulong));
880 return result;
881 }
882
mulFlintMP_Zp(const CanonicalForm & F,int lF,const CanonicalForm & G,int lG,int m)883 CanonicalForm mulFlintMP_Zp(const CanonicalForm& F,int lF, const CanonicalForm& G, int lG,int m)
884 {
885 int bits=SI_LOG2(m)+1;
886 int N=F.level();
887 nmod_mpoly_ctx_t ctx;
888 nmod_mpoly_ctx_init(ctx,N,ORD_LEX,getCharacteristic());
889 nmod_mpoly_t f,g,res;
890 nmod_mpoly_init3(f,lF,bits,ctx);
891 nmod_mpoly_init3(g,lG,bits,ctx);
892 convFactoryPFlintMP(F,f,ctx,N);
893 convFactoryPFlintMP(G,g,ctx,N);
894 nmod_mpoly_init(res,ctx);
895 nmod_mpoly_mul(res,f,g,ctx);
896 nmod_mpoly_clear(g,ctx);
897 nmod_mpoly_clear(f,ctx);
898 CanonicalForm RES=convFlintMPFactoryP(res,ctx,N);
899 nmod_mpoly_clear(res,ctx);
900 nmod_mpoly_ctx_clear(ctx);
901 return RES;
902 }
903
mulFlintMP_QQ(const CanonicalForm & F,int lF,const CanonicalForm & G,int lG,int m)904 CanonicalForm mulFlintMP_QQ(const CanonicalForm& F,int lF, const CanonicalForm& G, int lG, int m)
905 {
906 int bits=SI_LOG2(m)+1;
907 int N=F.level();
908 fmpq_mpoly_ctx_t ctx;
909 fmpq_mpoly_ctx_init(ctx,N,ORD_LEX);
910 fmpq_mpoly_t f,g,res;
911 fmpq_mpoly_init3(f,lF,bits,ctx);
912 fmpq_mpoly_init3(g,lG,bits,ctx);
913 convFactoryPFlintMP(F,f,ctx,N);
914 convFactoryPFlintMP(G,g,ctx,N);
915 fmpq_mpoly_init(res,ctx);
916 fmpq_mpoly_mul(res,f,g,ctx);
917 fmpq_mpoly_clear(g,ctx);
918 fmpq_mpoly_clear(f,ctx);
919 CanonicalForm RES=convFlintMPFactoryP(res,ctx,N);
920 fmpq_mpoly_clear(res,ctx);
921 fmpq_mpoly_ctx_clear(ctx);
922 return RES;
923 }
924
gcdFlintMP_Zp(const CanonicalForm & F,const CanonicalForm & G)925 CanonicalForm gcdFlintMP_Zp(const CanonicalForm& F, const CanonicalForm& G)
926 {
927 int N=F.level();
928 int lf,lg,m=1<<MPOLY_MIN_BITS;
929 lf=size_maxexp(F,m);
930 lg=size_maxexp(G,m);
931 int bits=SI_LOG2(m)+1;
932 nmod_mpoly_ctx_t ctx;
933 nmod_mpoly_ctx_init(ctx,N,ORD_LEX,getCharacteristic());
934 nmod_mpoly_t f,g,res;
935 nmod_mpoly_init3(f,lf,bits,ctx);
936 nmod_mpoly_init3(g,lg,bits,ctx);
937 convFactoryPFlintMP(F,f,ctx,N);
938 convFactoryPFlintMP(G,g,ctx,N);
939 nmod_mpoly_init(res,ctx);
940 int ok=nmod_mpoly_gcd(res,f,g,ctx);
941 nmod_mpoly_clear(g,ctx);
942 nmod_mpoly_clear(f,ctx);
943 CanonicalForm RES=1;
944 if (ok)
945 {
946 RES=convFlintMPFactoryP(res,ctx,N);
947 }
948 nmod_mpoly_clear(res,ctx);
949 nmod_mpoly_ctx_clear(ctx);
950 return RES;
951 }
952
b_content(const CanonicalForm & f)953 static CanonicalForm b_content ( const CanonicalForm & f )
954 {
955 if ( f.inCoeffDomain() )
956 return f;
957 else
958 {
959 CanonicalForm result = 0;
960 CFIterator i;
961 for ( i = f; i.hasTerms() && (!result.isOne()); i++ )
962 result=bgcd( b_content(i.coeff()) , result );
963 return result;
964 }
965 }
966
967
gcdFlintMP_QQ(const CanonicalForm & F,const CanonicalForm & G)968 CanonicalForm gcdFlintMP_QQ(const CanonicalForm& F, const CanonicalForm& G)
969 {
970 int N=F.level();
971 fmpq_mpoly_ctx_t ctx;
972 fmpq_mpoly_ctx_init(ctx,N,ORD_LEX);
973 fmpq_mpoly_t f,g,res;
974 fmpq_mpoly_init(f,ctx);
975 fmpq_mpoly_init(g,ctx);
976 convFactoryPFlintMP(F,f,ctx,N);
977 convFactoryPFlintMP(G,g,ctx,N);
978 fmpq_mpoly_init(res,ctx);
979 int ok=fmpq_mpoly_gcd(res,f,g,ctx);
980 fmpq_mpoly_clear(g,ctx);
981 fmpq_mpoly_clear(f,ctx);
982 CanonicalForm RES=1;
983 if (ok)
984 {
985 // Flint normalizes the gcd to be monic.
986 // Singular wants a gcd defined over ZZ that is primitive and has a positive leading coeff.
987 if (!fmpq_mpoly_is_zero(res, ctx))
988 {
989 fmpq_t content;
990 fmpq_init(content);
991 fmpq_mpoly_content(content, res, ctx);
992 fmpq_mpoly_scalar_div_fmpq(res, res, content, ctx);
993 fmpq_clear(content);
994 }
995 RES=convFlintMPFactoryP(res,ctx,N);
996 // gcd(2x,4x) should be 2x, so RES should also have the gcd(lc(F),lc(G))
997 RES*=bgcd(b_content(F),b_content(G));
998 }
999 fmpq_mpoly_clear(res,ctx);
1000 fmpq_mpoly_ctx_clear(ctx);
1001 return RES;
1002 }
1003
1004 #endif // FLINT 2.5.3
1005
1006 #if __FLINT_RELEASE >= 20700
1007 CFFList
convertFLINTFq_nmod_mpoly_factor2FacCFFList(fq_nmod_mpoly_factor_t fac,const fq_nmod_mpoly_ctx_t & ctx,const int N,const fq_nmod_ctx_t & fq_ctx,const Variable alpha)1008 convertFLINTFq_nmod_mpoly_factor2FacCFFList (
1009 fq_nmod_mpoly_factor_t fac,
1010 const fq_nmod_mpoly_ctx_t& ctx,
1011 const int N,
1012 const fq_nmod_ctx_t& fq_ctx,
1013 const Variable alpha)
1014 {
1015 CFFList result;
1016
1017 long i;
1018
1019 fq_nmod_t c;
1020 fq_nmod_init(c,fq_ctx);
1021 fq_nmod_mpoly_factor_get_constant_fq_nmod(c,fac,ctx);
1022 result.append(CFFactor(convertFq_nmod_t2FacCF(c,alpha,fq_ctx),1));
1023 fq_nmod_clear(c,fq_ctx);
1024
1025 fq_nmod_mpoly_t p;
1026 fq_nmod_mpoly_init(p,ctx);
1027 long exp;
1028 for (i = 0; i < fac->num; i++)
1029 {
1030 fq_nmod_mpoly_factor_get_base(p,fac,i,ctx);
1031 exp=fq_nmod_mpoly_factor_get_exp_si(fac,i,ctx);
1032 result.append (CFFactor (convertFq_nmod_mpoly_t2FacCF (
1033 p,ctx,N,fq_ctx,alpha), exp));
1034 }
1035 fq_nmod_mpoly_clear(p,ctx);
1036 return result;
1037 }
1038
1039 void
convertFacCF2Fq_nmod_mpoly_t(fq_nmod_mpoly_t result,const CanonicalForm & f,const fq_nmod_mpoly_ctx_t ctx,const int N,const fq_nmod_ctx_t fq_ctx)1040 convertFacCF2Fq_nmod_mpoly_t (fq_nmod_mpoly_t result,
1041 const CanonicalForm& f,
1042 const fq_nmod_mpoly_ctx_t ctx,
1043 const int N,
1044 const fq_nmod_ctx_t fq_ctx
1045 )
1046 {
1047 if (f.isZero()) return;
1048 ulong * exp = (ulong*)Alloc(N*sizeof(ulong));
1049 memset(exp,0,N*sizeof(ulong));
1050 convFlint_RecPP( f, exp, result, ctx, N, fq_ctx );
1051 Free(exp,N*sizeof(ulong));
1052 }
1053
1054 CanonicalForm
convertFq_nmod_mpoly_t2FacCF(const fq_nmod_mpoly_t f,const fq_nmod_mpoly_ctx_t & ctx,const int N,const fq_nmod_ctx_t & fq_ctx,const Variable alpha)1055 convertFq_nmod_mpoly_t2FacCF (const fq_nmod_mpoly_t f,
1056 const fq_nmod_mpoly_ctx_t& ctx,
1057 const int N,
1058 const fq_nmod_ctx_t& fq_ctx,
1059 const Variable alpha)
1060 {
1061 CanonicalForm result;
1062 int d=fq_nmod_mpoly_length(f,ctx)-1;
1063 ulong* exp=(ulong*)Alloc(N*sizeof(ulong));
1064 fq_nmod_t c;
1065 fq_nmod_init(c,fq_ctx);
1066 for(int i=d; i>=0; i--)
1067 {
1068 fq_nmod_mpoly_get_term_coeff_fq_nmod(c,f,i,ctx);
1069 fq_nmod_mpoly_get_term_exp_ui(exp,f,i,ctx);
1070 CanonicalForm term=convertFq_nmod_t2FacCF(c,alpha,fq_ctx);
1071 for ( int i = 0; i <N; i++ )
1072 {
1073 if (exp[i]!=0) term*=CanonicalForm( Variable( N-i ), exp[i] );
1074 }
1075 result+=term;
1076 }
1077 Free(exp,N*sizeof(ulong));
1078 return result;
1079 }
1080
1081 #endif
1082 #endif // FLINT
1083