1 /*
2 Copyright (C) 2016-2017 William Hart
3 Copyright (C) 2017-2020 Daniel Schultz
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <https://www.gnu.org/licenses/>.
11 */
12
13 #ifndef FMPZ_MPOLY_H
14 #define FMPZ_MPOLY_H
15
16 #ifdef FMPZ_MPOLY_INLINES_C
17 #define FMPZ_MPOLY_INLINE FLINT_DLL
18 #else
19 #define FMPZ_MPOLY_INLINE static __inline__
20 #endif
21
22 #undef ulong
23 #define ulong ulongxx /* interferes with system includes */
24 #include <stdio.h>
25 #undef ulong
26
27 #include <gmp.h>
28 #define ulong mp_limb_t
29
30 #include "flint.h"
31 #include "fmpz.h"
32 #include "fmpz_vec.h"
33 #include "fmpz_poly.h"
34 #include "mpoly.h"
35 #include "nmod_mpoly.h"
36 #include "fmpz_mod.h"
37 #include "n_poly.h"
38
39 #ifdef __cplusplus
40 extern "C" {
41 #endif
42
43 /* Type definitions **********************************************************/
44
45 /*
46 context object for fmpz_mpoly
47 */
48 typedef struct
49 {
50 mpoly_ctx_t minfo;
51 } fmpz_mpoly_ctx_struct;
52
53 typedef fmpz_mpoly_ctx_struct fmpz_mpoly_ctx_t[1];
54
55 /*
56 fmpz_mpoly_t
57 sparse multivariates with fmpz coeffs
58 */
59 typedef struct
60 {
61 fmpz * coeffs; /* alloc fmpzs */
62 ulong * exps;
63 slong alloc;
64 slong length;
65 flint_bitcnt_t bits; /* number of bits per exponent */
66 } fmpz_mpoly_struct;
67
68 typedef fmpz_mpoly_struct fmpz_mpoly_t[1];
69
70 FMPZ_MPOLY_INLINE
fmpz_mpoly_term_coeff_ref(fmpz_mpoly_t A,slong i,const fmpz_mpoly_ctx_t ctx)71 fmpz * fmpz_mpoly_term_coeff_ref(fmpz_mpoly_t A, slong i,
72 const fmpz_mpoly_ctx_t ctx)
73 {
74 FLINT_ASSERT(i < A->length);
75 return A->coeffs + i;
76 }
77
fmpz_mpoly_leadcoeff(const fmpz_mpoly_t A)78 FMPZ_MPOLY_INLINE fmpz * fmpz_mpoly_leadcoeff(const fmpz_mpoly_t A)
79 {
80 FLINT_ASSERT(A->length > 0);
81 return A->coeffs + 0;
82 }
83
84 /* Internal type definitions *************************************************/
85
86 /*
87 fmpz_mpoly_univar_t
88 sparse univariates with multivariate coefficients
89 */
90 typedef struct
91 {
92 fmpz_mpoly_struct * coeffs; /* multivariate coefficients */
93 fmpz * exps;
94 slong alloc;
95 slong length;
96 } fmpz_mpoly_univar_struct;
97
98 typedef fmpz_mpoly_univar_struct fmpz_mpoly_univar_t[1];
99
100 /*
101 fmpz_mpolyd_t
102 A dense mpoly is stored as a flat array of coeffcients.
103 Suppose deg_bounds = {r0, r1, r2}. The coefficient of the monomial with
104 exponents {e0, e1, e2} is stored at the coefficient of index
105 e2 + r2*(e1 + r1*(e0 + r0*0))
106 */
107 typedef struct
108 {
109 slong nvars;
110 slong degb_alloc;
111 slong * deg_bounds;
112 slong length; /* usage is inconsistent currently */
113 slong coeff_alloc;
114 fmpz * coeffs;
115 } fmpz_mpolyd_struct;
116
117 typedef fmpz_mpolyd_struct fmpz_mpolyd_t[1];
118
119 /* Context object ************************************************************/
120
121 FLINT_DLL void fmpz_mpoly_ctx_init(fmpz_mpoly_ctx_t ctx,
122 slong nvars, const ordering_t ord);
123
124 FLINT_DLL void fmpz_mpoly_ctx_init_rand(fmpz_mpoly_ctx_t mctx, flint_rand_t state, slong max_nvars);
125
126
127 FLINT_DLL void fmpz_mpoly_ctx_clear(fmpz_mpoly_ctx_t ctx);
128
129 FMPZ_MPOLY_INLINE
fmpz_mpoly_ctx_nvars(const fmpz_mpoly_ctx_t ctx)130 slong fmpz_mpoly_ctx_nvars(const fmpz_mpoly_ctx_t ctx)
131 {
132 return ctx->minfo->nvars;
133 }
134
135 FMPZ_MPOLY_INLINE
fmpz_mpoly_ctx_ord(const fmpz_mpoly_ctx_t ctx)136 ordering_t fmpz_mpoly_ctx_ord(const fmpz_mpoly_ctx_t ctx)
137 {
138 return ctx->minfo->ord;
139 }
140
141
142 /* Memory management ********************************************************/
143
144 FLINT_DLL void fmpz_mpoly_init(fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx);
145
146 FLINT_DLL void fmpz_mpoly_init2(fmpz_mpoly_t A, slong alloc,
147 const fmpz_mpoly_ctx_t ctx);
148
149 FLINT_DLL void fmpz_mpoly_init3(fmpz_mpoly_t A, slong alloc, flint_bitcnt_t bits,
150 const fmpz_mpoly_ctx_t ctx);
151
152 FLINT_DLL void _fmpz_mpoly_realloc(fmpz ** Acoeff, ulong ** Aexp,
153 slong * Aalloc, slong len, slong N);
154
155 FLINT_DLL void fmpz_mpoly_realloc(fmpz_mpoly_t A, slong alloc,
156 const fmpz_mpoly_ctx_t ctx);
157
158 FLINT_DLL void _fmpz_mpoly_fit_length(fmpz ** Acoeff,
159 ulong ** Aexp, slong * Aalloc, slong len, slong N);
160
161 FLINT_DLL void fmpz_mpoly_fit_length(fmpz_mpoly_t A, slong len,
162 const fmpz_mpoly_ctx_t ctx);
163
164 FLINT_DLL void fmpz_mpoly_fit_length_reset_bits(fmpz_mpoly_t A, slong len,
165 flint_bitcnt_t bits, const fmpz_mpoly_ctx_t ctx);
166
167 FLINT_DLL void fmpz_mpoly_clear(fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx);
168
169 FMPZ_MPOLY_INLINE
_fmpz_mpoly_set_length(fmpz_mpoly_t A,slong newlen,const fmpz_mpoly_ctx_t ctx)170 void _fmpz_mpoly_set_length(fmpz_mpoly_t A, slong newlen,
171 const fmpz_mpoly_ctx_t ctx)
172 {
173 slong i;
174 for (i = newlen; i < A->length; i++)
175 _fmpz_demote(A->coeffs + i);
176
177 A->length = newlen;
178 }
179
180 FMPZ_MPOLY_INLINE
fmpz_mpoly_truncate(fmpz_mpoly_t A,slong newlen,const fmpz_mpoly_ctx_t ctx)181 void fmpz_mpoly_truncate(fmpz_mpoly_t A, slong newlen,
182 const fmpz_mpoly_ctx_t ctx)
183 {
184 if (A->length > newlen)
185 {
186 slong i;
187
188 for (i = newlen; i < A->length; i++)
189 _fmpz_demote(A->coeffs + i);
190
191 A->length = newlen;
192 }
193 }
194
195 FMPZ_MPOLY_INLINE
fmpz_mpoly_fit_bits(fmpz_mpoly_t A,flint_bitcnt_t bits,const fmpz_mpoly_ctx_t ctx)196 void fmpz_mpoly_fit_bits(fmpz_mpoly_t A,
197 flint_bitcnt_t bits, const fmpz_mpoly_ctx_t ctx)
198 {
199 if (A->bits < bits)
200 {
201 if (A->alloc != 0)
202 {
203 slong N = mpoly_words_per_exp(bits, ctx->minfo);
204 ulong * t = (ulong *) flint_malloc(N*A->alloc*sizeof(ulong));
205 mpoly_repack_monomials(t, bits, A->exps, A->bits, A->length, ctx->minfo);
206 flint_free(A->exps);
207 A->exps = t;
208 }
209
210 A->bits = bits;
211 }
212 }
213
214
215 /* Input/output **************************************************************/
216
217 FLINT_DLL int fmpz_mpoly_set_str_pretty(fmpz_mpoly_t A, const char * str,
218 const char ** x, const fmpz_mpoly_ctx_t ctx);
219
220 FLINT_DLL char * _fmpz_mpoly_get_str_pretty(const fmpz * poly,
221 const ulong * exps, slong len, const char ** x,
222 slong bits, const mpoly_ctx_t mctx);
223
224 FLINT_DLL char * fmpz_mpoly_get_str_pretty(const fmpz_mpoly_t A,
225 const char ** x, const fmpz_mpoly_ctx_t ctx);
226
227 FLINT_DLL int _fmpz_mpoly_fprint_pretty(FILE * file, const fmpz * poly,
228 const ulong * exps, slong len, const char ** x_in,
229 flint_bitcnt_t bits, const mpoly_ctx_t mctx);
230
231 FLINT_DLL int fmpz_mpoly_fprint_pretty(FILE * file,
232 const fmpz_mpoly_t A, const char ** x, const fmpz_mpoly_ctx_t ctx);
233
234 FMPZ_MPOLY_INLINE
_fmpz_mpoly_print_pretty(const fmpz * poly,const ulong * exps,slong len,const char ** x,slong bits,const mpoly_ctx_t mctx)235 int _fmpz_mpoly_print_pretty(const fmpz * poly,
236 const ulong * exps, slong len, const char ** x,
237 slong bits, const mpoly_ctx_t mctx)
238 {
239 return _fmpz_mpoly_fprint_pretty(stdout, poly, exps, len, x, bits, mctx);
240 }
241
242 FMPZ_MPOLY_INLINE
fmpz_mpoly_print_pretty(const fmpz_mpoly_t A,const char ** x,const fmpz_mpoly_ctx_t ctx)243 int fmpz_mpoly_print_pretty(const fmpz_mpoly_t A,
244 const char ** x, const fmpz_mpoly_ctx_t ctx)
245 {
246 return fmpz_mpoly_fprint_pretty(stdout, A, x, ctx);
247 }
248
249
250 /* Basic manipulation *******************************************************/
251
252 FLINT_DLL void fmpz_mpoly_gen(fmpz_mpoly_t poly, slong i,
253 const fmpz_mpoly_ctx_t ctx);
254
255 FLINT_DLL int fmpz_mpoly_is_gen(const fmpz_mpoly_t poly,
256 slong k, const fmpz_mpoly_ctx_t ctx);
257
258 FLINT_DLL void _fmpz_mpoly_set(fmpz * poly1, ulong * exps1,
259 const fmpz * poly2, const ulong * exps2, slong n, slong N);
260
261 FLINT_DLL void fmpz_mpoly_set(fmpz_mpoly_t A, const fmpz_mpoly_t B,
262 const fmpz_mpoly_ctx_t ctx);
263
264 FLINT_DLL int _fmpz_mpoly_equal(fmpz * poly1, ulong * exps1,
265 const fmpz * poly2, const ulong * exps2, slong n, slong N);
266
267 FLINT_DLL int fmpz_mpoly_equal(const fmpz_mpoly_t A, const fmpz_mpoly_t B,
268 const fmpz_mpoly_ctx_t ctx);
269
270 FMPZ_MPOLY_INLINE
fmpz_mpoly_swap(fmpz_mpoly_t A,fmpz_mpoly_t B,const fmpz_mpoly_ctx_t ctx)271 void fmpz_mpoly_swap(fmpz_mpoly_t A,
272 fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx)
273 {
274 fmpz_mpoly_struct t = *A;
275 *A = *B;
276 *B = t;
277 }
278
279 FMPZ_MPOLY_INLINE
_fmpz_mpoly_fits_small(const fmpz * poly,slong len)280 int _fmpz_mpoly_fits_small(const fmpz * poly, slong len)
281 {
282 slong i;
283 for (i = 0; i < len; i++)
284 {
285 if (COEFF_IS_MPZ(poly[i]))
286 return 0;
287 }
288 return 1;
289 }
290
291 FMPZ_MPOLY_INLINE
fmpz_mpoly_max_bits(const fmpz_mpoly_t A)292 slong fmpz_mpoly_max_bits(const fmpz_mpoly_t A)
293 {
294 return _fmpz_vec_max_bits(A->coeffs, A->length);
295 }
296
297 /* Constants *****************************************************************/
298
299 FLINT_DLL int fmpz_mpoly_is_fmpz(const fmpz_mpoly_t A,
300 const fmpz_mpoly_ctx_t ctx);
301
302 FLINT_DLL void fmpz_mpoly_get_fmpz(fmpz_t c, const fmpz_mpoly_t A,
303 const fmpz_mpoly_ctx_t ctx);
304
305 FLINT_DLL void fmpz_mpoly_set_fmpz(fmpz_mpoly_t A,
306 const fmpz_t c, const fmpz_mpoly_ctx_t ctx);
307
308 FLINT_DLL void fmpz_mpoly_set_ui(fmpz_mpoly_t A,
309 ulong c, const fmpz_mpoly_ctx_t ctx);
310
311 FLINT_DLL void fmpz_mpoly_set_si(fmpz_mpoly_t A,
312 slong c, const fmpz_mpoly_ctx_t ctx);
313
314 FMPZ_MPOLY_INLINE
fmpz_mpoly_zero(fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)315 void fmpz_mpoly_zero(fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx)
316 {
317 _fmpz_mpoly_set_length(A, 0, ctx);
318 }
319
320 FMPZ_MPOLY_INLINE
fmpz_mpoly_one(fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)321 void fmpz_mpoly_one(fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx)
322 {
323 fmpz_mpoly_set_ui(A, UWORD(1), ctx);
324 }
325
326 FLINT_DLL int fmpz_mpoly_equal_fmpz(const fmpz_mpoly_t A,
327 const fmpz_t c, const fmpz_mpoly_ctx_t ctx);
328
329 FLINT_DLL int fmpz_mpoly_equal_ui(const fmpz_mpoly_t A,
330 ulong c, const fmpz_mpoly_ctx_t ctx);
331
332 FLINT_DLL int fmpz_mpoly_equal_si(const fmpz_mpoly_t A,
333 slong c, const fmpz_mpoly_ctx_t ctx);
334
335 FMPZ_MPOLY_INLINE
fmpz_mpoly_is_zero(const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)336 int fmpz_mpoly_is_zero(const fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx)
337 {
338 return A->length == 0;
339 }
340
341 FMPZ_MPOLY_INLINE
fmpz_mpoly_is_one(const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)342 int fmpz_mpoly_is_one(const fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx)
343 {
344 return fmpz_mpoly_equal_ui(A, UWORD(1), ctx);
345 }
346
347
348 /* Degrees *******************************************************************/
349
350 FMPZ_MPOLY_INLINE
fmpz_mpoly_degrees_fit_si(const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)351 int fmpz_mpoly_degrees_fit_si(const fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx)
352 {
353 return A->bits <= FLINT_BITS ? 1
354 : mpoly_degrees_fit_si(A->exps, A->length, A->bits, ctx->minfo);
355 }
356
357 FMPZ_MPOLY_INLINE
fmpz_mpoly_degrees_fmpz(fmpz ** degs,const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)358 void fmpz_mpoly_degrees_fmpz(fmpz ** degs, const fmpz_mpoly_t A,
359 const fmpz_mpoly_ctx_t ctx)
360 {
361 mpoly_degrees_pfmpz(degs, A->exps, A->length, A->bits, ctx->minfo);
362 }
363
364 FMPZ_MPOLY_INLINE
fmpz_mpoly_degrees_si(slong * degs,const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)365 void fmpz_mpoly_degrees_si(slong * degs, const fmpz_mpoly_t A,
366 const fmpz_mpoly_ctx_t ctx)
367 {
368 mpoly_degrees_si(degs, A->exps, A->length, A->bits, ctx->minfo);
369 }
370
371 FMPZ_MPOLY_INLINE
fmpz_mpoly_degree_fmpz(fmpz_t deg,const fmpz_mpoly_t A,slong var,const fmpz_mpoly_ctx_t ctx)372 void fmpz_mpoly_degree_fmpz(fmpz_t deg, const fmpz_mpoly_t A, slong var,
373 const fmpz_mpoly_ctx_t ctx)
374 {
375 mpoly_degree_fmpz(deg, A->exps, A->length, A->bits, var, ctx->minfo);
376 }
377
378 FMPZ_MPOLY_INLINE
fmpz_mpoly_degree_si(const fmpz_mpoly_t A,slong var,const fmpz_mpoly_ctx_t ctx)379 slong fmpz_mpoly_degree_si(const fmpz_mpoly_t A, slong var,
380 const fmpz_mpoly_ctx_t ctx)
381 {
382 return mpoly_degree_si(A->exps, A->length, A->bits, var, ctx->minfo);
383 }
384
385 FMPZ_MPOLY_INLINE
fmpz_mpoly_total_degree_fits_si(const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)386 int fmpz_mpoly_total_degree_fits_si(const fmpz_mpoly_t A,
387 const fmpz_mpoly_ctx_t ctx)
388 {
389 return mpoly_total_degree_fits_si(A->exps, A->length, A->bits, ctx->minfo);
390 }
391
392 FMPZ_MPOLY_INLINE
fmpz_mpoly_total_degree_fmpz(fmpz_t td,const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)393 void fmpz_mpoly_total_degree_fmpz(fmpz_t td, const fmpz_mpoly_t A,
394 const fmpz_mpoly_ctx_t ctx)
395 {
396 mpoly_total_degree_fmpz(td, A->exps, A->length, A->bits, ctx->minfo);
397 }
398
399 FMPZ_MPOLY_INLINE
fmpz_mpoly_total_degree_si(const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)400 slong fmpz_mpoly_total_degree_si(const fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx)
401 {
402 return mpoly_total_degree_si(A->exps, A->length, A->bits, ctx->minfo);
403 }
404
405 FMPZ_MPOLY_INLINE
fmpz_mpoly_used_vars(int * used,const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)406 void fmpz_mpoly_used_vars(int * used, const fmpz_mpoly_t A,
407 const fmpz_mpoly_ctx_t ctx)
408 {
409 slong i;
410
411 for (i = 0; i < ctx->minfo->nvars; i++)
412 used[i] = 0;
413
414 mpoly_used_vars_or(used, A->exps, A->length, A->bits, ctx->minfo);
415 }
416
417 /* Coefficients **************************************************************/
418
419 FLINT_DLL void fmpz_mpoly_get_coeff_fmpz_monomial(fmpz_t c,
420 const fmpz_mpoly_t A, const fmpz_mpoly_t M,
421 const fmpz_mpoly_ctx_t ctx);
422
423 FLINT_DLL void fmpz_mpoly_set_coeff_fmpz_monomial(fmpz_mpoly_t A,
424 const fmpz_t c, const fmpz_mpoly_t M,
425 const fmpz_mpoly_ctx_t ctx);
426
427 FLINT_DLL void fmpz_mpoly_get_coeff_fmpz_fmpz(fmpz_t c, const fmpz_mpoly_t A,
428 fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
429
430 FLINT_DLL ulong fmpz_mpoly_get_coeff_ui_fmpz( const fmpz_mpoly_t A,
431 fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
432
433 FLINT_DLL slong fmpz_mpoly_get_coeff_si_fmpz( const fmpz_mpoly_t A,
434 fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
435
436 FLINT_DLL void fmpz_mpoly_get_coeff_fmpz_ui(fmpz_t c, const fmpz_mpoly_t A,
437 const ulong * exp, const fmpz_mpoly_ctx_t ctx);
438
439 FLINT_DLL ulong fmpz_mpoly_get_coeff_ui_ui( const fmpz_mpoly_t A,
440 const ulong * exp, const fmpz_mpoly_ctx_t ctx);
441
442 FLINT_DLL slong fmpz_mpoly_get_coeff_si_ui( const fmpz_mpoly_t A,
443 const ulong * exp, const fmpz_mpoly_ctx_t ctx);
444
445 FLINT_DLL void _fmpz_mpoly_set_coeff_fmpz_fmpz(fmpz_mpoly_t A,
446 const fmpz_t c, const fmpz * exp, const fmpz_mpoly_ctx_t ctx);
447
448 FLINT_DLL void fmpz_mpoly_set_coeff_fmpz_fmpz(fmpz_mpoly_t A,
449 const fmpz_t c, fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
450
451 FLINT_DLL void fmpz_mpoly_set_coeff_ui_fmpz(fmpz_mpoly_t A,
452 const ulong c, fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
453
454 FLINT_DLL void fmpz_mpoly_set_coeff_si_fmpz(fmpz_mpoly_t A,
455 const slong c, fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
456
457 FLINT_DLL void fmpz_mpoly_set_coeff_fmpz_ui(fmpz_mpoly_t A,
458 const fmpz_t c, const ulong * exp, const fmpz_mpoly_ctx_t ctx);
459
460 FLINT_DLL void fmpz_mpoly_set_coeff_ui_ui(fmpz_mpoly_t A,
461 const ulong c, const ulong * exp, const fmpz_mpoly_ctx_t ctx);
462
463 FLINT_DLL void fmpz_mpoly_set_coeff_si_ui(fmpz_mpoly_t A,
464 const slong c, const ulong * exp, const fmpz_mpoly_ctx_t ctx);
465
466 FLINT_DLL void fmpz_mpoly_get_coeff_vars_ui(fmpz_mpoly_t C,
467 const fmpz_mpoly_t A, const slong * vars, const ulong * exps,
468 slong length, const fmpz_mpoly_ctx_t ctx);
469
470 /* conversion ****************************************************************/
471
472 FLINT_DLL int fmpz_mpoly_is_fmpz_poly(const fmpz_mpoly_t A, slong var,
473 const fmpz_mpoly_ctx_t ctx);
474
475 FLINT_DLL int fmpz_mpoly_get_fmpz_poly(fmpz_poly_t A, const fmpz_mpoly_t B,
476 slong var, const fmpz_mpoly_ctx_t ctx);
477
478 FLINT_DLL void _fmpz_mpoly_set_fmpz_poly(fmpz_mpoly_t A, flint_bitcnt_t Abits,
479 const fmpz * Bcoeffs, slong Blen, slong var, const fmpz_mpoly_ctx_t ctx);
480
481 FLINT_DLL void fmpz_mpoly_set_fmpz_poly(fmpz_mpoly_t A, const fmpz_poly_t B,
482 slong v, const fmpz_mpoly_ctx_t ctx);
483
484 /* comparison ****************************************************************/
485
486 FLINT_DLL int fmpz_mpoly_cmp(const fmpz_mpoly_t A, const fmpz_mpoly_t B,
487 const fmpz_mpoly_ctx_t ctx);
488
489 /* container operations ******************************************************/
490
491 FLINT_DLL int fmpz_mpoly_is_canonical(const fmpz_mpoly_t A,
492 const fmpz_mpoly_ctx_t ctx);
493
494 FMPZ_MPOLY_INLINE
fmpz_mpoly_length(const fmpz_mpoly_t A,const fmpz_mpoly_ctx_t ctx)495 slong fmpz_mpoly_length(const fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx)
496 {
497 return A->length;
498 }
499
500 FLINT_DLL void fmpz_mpoly_resize(fmpz_mpoly_t A, slong new_length,
501 const fmpz_mpoly_ctx_t ctx);
502
503 FLINT_DLL void fmpz_mpoly_get_term_coeff_fmpz(fmpz_t c, const fmpz_mpoly_t A,
504 slong i, const fmpz_mpoly_ctx_t ctx);
505
506 FLINT_DLL ulong fmpz_mpoly_get_term_coeff_ui( const fmpz_mpoly_t A,
507 slong i, const fmpz_mpoly_ctx_t ctx);
508
509 FLINT_DLL slong fmpz_mpoly_get_term_coeff_si( const fmpz_mpoly_t A,
510 slong i, const fmpz_mpoly_ctx_t ctx);
511
512 FLINT_DLL void fmpz_mpoly_set_term_coeff_fmpz(fmpz_mpoly_t A,
513 slong i, const fmpz_t c, const fmpz_mpoly_ctx_t ctx);
514
515 FLINT_DLL void fmpz_mpoly_set_term_coeff_ui(fmpz_mpoly_t A,
516 slong i, ulong c, const fmpz_mpoly_ctx_t ctx);
517
518 FLINT_DLL void fmpz_mpoly_set_term_coeff_si(fmpz_mpoly_t A,
519 slong i, slong c, const fmpz_mpoly_ctx_t ctx);
520
521 FMPZ_MPOLY_INLINE
fmpz_mpoly_term_exp_fits_ui(const fmpz_mpoly_t A,slong i,const fmpz_mpoly_ctx_t ctx)522 int fmpz_mpoly_term_exp_fits_ui(const fmpz_mpoly_t A, slong i,
523 const fmpz_mpoly_ctx_t ctx)
524 {
525 return A->bits <= FLINT_BITS ? 1
526 : mpoly_term_exp_fits_ui(A->exps, A->bits, i, ctx->minfo);
527 }
528
529 FMPZ_MPOLY_INLINE
fmpz_mpoly_term_exp_fits_si(const fmpz_mpoly_t A,slong i,const fmpz_mpoly_ctx_t ctx)530 int fmpz_mpoly_term_exp_fits_si(const fmpz_mpoly_t A, slong i,
531 const fmpz_mpoly_ctx_t ctx)
532 {
533 return A->bits <= FLINT_BITS ? 1
534 : mpoly_term_exp_fits_si(A->exps, A->bits, i, ctx->minfo);
535 }
536
537 FLINT_DLL void fmpz_mpoly_get_term_exp_fmpz(fmpz ** exp, const fmpz_mpoly_t A,
538 slong i, const fmpz_mpoly_ctx_t ctx);
539
540 FLINT_DLL void fmpz_mpoly_get_term_exp_ui(ulong * exp, const fmpz_mpoly_t A,
541 slong i, const fmpz_mpoly_ctx_t ctx);
542
543 FLINT_DLL void fmpz_mpoly_get_term_exp_si(slong * exp, const fmpz_mpoly_t A,
544 slong i, const fmpz_mpoly_ctx_t ctx);
545
546 FLINT_DLL ulong fmpz_mpoly_get_term_var_exp_ui(const fmpz_mpoly_t A, slong i,
547 slong var, const fmpz_mpoly_ctx_t ctx);
548
549 FLINT_DLL slong fmpz_mpoly_get_term_var_exp_si(const fmpz_mpoly_t A, slong i,
550 slong var, const fmpz_mpoly_ctx_t ctx);
551
552 FLINT_DLL void fmpz_mpoly_set_term_exp_fmpz(fmpz_mpoly_t A,
553 slong i, fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
554
555 FLINT_DLL void fmpz_mpoly_set_term_exp_ui(fmpz_mpoly_t A,
556 slong i, const ulong * exp, const fmpz_mpoly_ctx_t ctx);
557
558 FLINT_DLL void fmpz_mpoly_get_term(fmpz_mpoly_t M, const fmpz_mpoly_t A,
559 slong i, const fmpz_mpoly_ctx_t ctx);
560
561 FLINT_DLL void fmpz_mpoly_get_term_monomial(fmpz_mpoly_t M, const fmpz_mpoly_t A,
562 slong i, const fmpz_mpoly_ctx_t ctx);
563
564 FLINT_DLL void fmpz_mpoly_push_term_fmpz_fmpz(fmpz_mpoly_t A,
565 const fmpz_t c, fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
566
567 FLINT_DLL void fmpz_mpoly_push_term_ui_fmpz(fmpz_mpoly_t A,
568 ulong c, fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
569
570 FLINT_DLL void fmpz_mpoly_push_term_si_fmpz(fmpz_mpoly_t A,
571 slong c, fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
572
573 FLINT_DLL void fmpz_mpoly_push_term_fmpz_ui(fmpz_mpoly_t A,
574 const fmpz_t c, const ulong * exp, const fmpz_mpoly_ctx_t ctx);
575
576 FLINT_DLL void fmpz_mpoly_push_term_ui_ui(fmpz_mpoly_t A,
577 ulong c, const ulong * exp, const fmpz_mpoly_ctx_t ctx);
578
579 FLINT_DLL void fmpz_mpoly_push_term_si_ui(fmpz_mpoly_t A,
580 slong c, const ulong * exp, const fmpz_mpoly_ctx_t ctx);
581
582 FLINT_DLL void fmpz_mpoly_sort_terms(fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx);
583
584 FLINT_DLL void fmpz_mpoly_combine_like_terms(fmpz_mpoly_t A,
585 const fmpz_mpoly_ctx_t ctx);
586
587 FLINT_DLL void fmpz_mpoly_reverse(fmpz_mpoly_t A, const fmpz_mpoly_t B,
588 const fmpz_mpoly_ctx_t ctx);
589
590 FLINT_DLL void fmpz_mpoly_assert_canonical(const fmpz_mpoly_t A,
591 const fmpz_mpoly_ctx_t ctx);
592
593 FLINT_DLL void _fmpz_mpoly_radix_sort1(fmpz_mpoly_t A, slong left, slong right,
594 flint_bitcnt_t pos, ulong cmpmask, ulong totalmask);
595
596 FLINT_DLL void _fmpz_mpoly_radix_sort(fmpz_mpoly_t A, slong left, slong right,
597 flint_bitcnt_t pos, slong N, ulong * cmpmask);
598
599 FLINT_DLL void _fmpz_mpoly_push_exp_ffmpz(fmpz_mpoly_t A,
600 const fmpz * exp, const fmpz_mpoly_ctx_t ctx);
601
602 FLINT_DLL void _fmpz_mpoly_push_exp_pfmpz(fmpz_mpoly_t A,
603 fmpz * const * exp, const fmpz_mpoly_ctx_t ctx);
604
605 FLINT_DLL void _fmpz_mpoly_push_exp_ui(fmpz_mpoly_t A,
606 const ulong * exp, const fmpz_mpoly_ctx_t ctx);
607
608
609 /* Random generation *********************************************************/
610
611 FLINT_DLL void fmpz_mpoly_randtest_bound(fmpz_mpoly_t A, flint_rand_t state,
612 slong length, flint_bitcnt_t coeff_bits, ulong exp_bound,
613 const fmpz_mpoly_ctx_t ctx);
614
615 FLINT_DLL void fmpz_mpoly_randtest_bounds(fmpz_mpoly_t A, flint_rand_t state,
616 slong length, flint_bitcnt_t coeff_bits, ulong * exp_bounds,
617 const fmpz_mpoly_ctx_t ctx);
618
619 FLINT_DLL void fmpz_mpoly_randtest_bits(fmpz_mpoly_t A, flint_rand_t state,
620 slong length, flint_bitcnt_t coeff_bits, flint_bitcnt_t exp_bits,
621 const fmpz_mpoly_ctx_t ctx);
622
623
624 /* Addition/Subtraction ******************************************************/
625
626 FLINT_DLL void fmpz_mpoly_add_fmpz(fmpz_mpoly_t A, const fmpz_mpoly_t B,
627 const fmpz_t c, const fmpz_mpoly_ctx_t ctx);
628
629 FLINT_DLL void fmpz_mpoly_add_ui(fmpz_mpoly_t A, const fmpz_mpoly_t B,
630 ulong c, const fmpz_mpoly_ctx_t ctx);
631
632 FLINT_DLL void fmpz_mpoly_add_si(fmpz_mpoly_t A, const fmpz_mpoly_t B,
633 slong c, const fmpz_mpoly_ctx_t ctx);
634
635 FLINT_DLL void fmpz_mpoly_sub_fmpz(fmpz_mpoly_t A, const fmpz_mpoly_t B,
636 const fmpz_t c, const fmpz_mpoly_ctx_t ctx);
637
638 FLINT_DLL void fmpz_mpoly_sub_ui(fmpz_mpoly_t A, const fmpz_mpoly_t B,
639 ulong c, const fmpz_mpoly_ctx_t ctx);
640
641 FLINT_DLL void fmpz_mpoly_sub_si(fmpz_mpoly_t A, const fmpz_mpoly_t B,
642 slong c, const fmpz_mpoly_ctx_t ctx);
643
644 FLINT_DLL void fmpz_mpoly_add(fmpz_mpoly_t A, const fmpz_mpoly_t B,
645 const fmpz_mpoly_t C, const fmpz_mpoly_ctx_t ctx);
646
647 FLINT_DLL slong _fmpz_mpoly_add(fmpz * poly1, ulong * exps1,
648 const fmpz * poly2, const ulong * exps2, slong len2,
649 const fmpz * poly3, const ulong * exps3, slong len3, slong N,
650 const ulong * cmpmask);
651
652 FLINT_DLL void fmpz_mpoly_sub(fmpz_mpoly_t A, const fmpz_mpoly_t B,
653 const fmpz_mpoly_t C, const fmpz_mpoly_ctx_t ctx);
654
655 FLINT_DLL slong _fmpz_mpoly_sub(fmpz * poly1, ulong * exps1,
656 const fmpz * poly2, const ulong * exps2, slong len2,
657 const fmpz * poly3, const ulong * exps3, slong len3, slong N,
658 const ulong * cmpmask);
659
660
661 /* Scalar operations *********************************************************/
662
663 FLINT_DLL void fmpz_mpoly_neg(fmpz_mpoly_t A, const fmpz_mpoly_t B,
664 const fmpz_mpoly_ctx_t ctx);
665
666 FLINT_DLL void fmpz_mpoly_scalar_mul_fmpz(fmpz_mpoly_t A,
667 const fmpz_mpoly_t B, const fmpz_t c, const fmpz_mpoly_ctx_t ctx);
668
669 FLINT_DLL void fmpz_mpoly_scalar_mul_si(fmpz_mpoly_t A,
670 const fmpz_mpoly_t B, slong c, const fmpz_mpoly_ctx_t ctx);
671
672 FLINT_DLL void fmpz_mpoly_scalar_mul_ui(fmpz_mpoly_t A,
673 const fmpz_mpoly_t B, ulong c, const fmpz_mpoly_ctx_t ctx);
674
675 FLINT_DLL void fmpz_mpoly_scalar_fmma(fmpz_mpoly_t A, const fmpz_mpoly_t B,
676 const fmpz_t c, const fmpz_mpoly_t D, const fmpz_t e,
677 const fmpz_mpoly_ctx_t ctx);
678
679 FLINT_DLL void fmpz_mpoly_scalar_divexact_fmpz(fmpz_mpoly_t A,
680 const fmpz_mpoly_t B, const fmpz_t c, const fmpz_mpoly_ctx_t ctx);
681
682 FLINT_DLL void fmpz_mpoly_scalar_divexact_si(fmpz_mpoly_t A,
683 const fmpz_mpoly_t B, slong c, const fmpz_mpoly_ctx_t ctx);
684
685 FLINT_DLL void fmpz_mpoly_scalar_divexact_ui(fmpz_mpoly_t A,
686 const fmpz_mpoly_t B, ulong c, const fmpz_mpoly_ctx_t ctx);
687
688 FLINT_DLL int fmpz_mpoly_scalar_divides_fmpz(fmpz_mpoly_t A,
689 const fmpz_mpoly_t B, const fmpz_t c, const fmpz_mpoly_ctx_t ctx);
690
691 FLINT_DLL int fmpz_mpoly_scalar_divides_si(fmpz_mpoly_t A,
692 const fmpz_mpoly_t B, slong c, const fmpz_mpoly_ctx_t ctx);
693
694 FLINT_DLL int fmpz_mpoly_scalar_divides_ui(fmpz_mpoly_t A,
695 const fmpz_mpoly_t B, ulong c, const fmpz_mpoly_ctx_t ctx);
696
697
698 /* Differentiation/Integration ***********************************************/
699
700 FLINT_DLL void fmpz_mpoly_derivative(fmpz_mpoly_t A,
701 const fmpz_mpoly_t B, slong var, const fmpz_mpoly_ctx_t ctx);
702
703 FLINT_DLL void fmpz_mpoly_integral(fmpz_mpoly_t A, fmpz_t scale,
704 const fmpz_mpoly_t B, slong var, const fmpz_mpoly_ctx_t ctx);
705
706
707 /* Evaluation ****************************************************************/
708
709 FLINT_DLL int _fmpz_pow_ui_is_not_feasible(flint_bitcnt_t bbits, ulong e);
710
711 FLINT_DLL int _fmpz_pow_fmpz_is_not_feasible(flint_bitcnt_t bbits, const fmpz_t e);
712
713 FLINT_DLL int fmpz_mpoly_evaluate_all_fmpz(fmpz_t ev, const fmpz_mpoly_t A,
714 fmpz * const * vals, const fmpz_mpoly_ctx_t ctx);
715
716 FLINT_DLL mp_limb_t fmpz_mpoly_evaluate_all_nmod(const fmpz_mpoly_t A,
717 const mp_limb_t * alphas, const fmpz_mpoly_ctx_t ctx, nmod_t fpctx);
718
719 FLINT_DLL void fmpz_mpoly_evaluate_all_fmpz_mod(fmpz_t ev,
720 const fmpz_mpoly_t A, const fmpz * alphas,
721 const fmpz_mpoly_ctx_t ctx, const fmpz_mod_ctx_t fpctx);
722
723 FLINT_DLL int fmpz_mpoly_evaluate_one_fmpz(fmpz_mpoly_t A,
724 const fmpz_mpoly_t B, slong var, const fmpz_t val,
725 const fmpz_mpoly_ctx_t ctx);
726
727 FLINT_DLL int fmpz_mpoly_compose_fmpz_poly(fmpz_poly_t A,
728 const fmpz_mpoly_t B, fmpz_poly_struct * const * C,
729 const fmpz_mpoly_ctx_t ctxB);
730
731 FLINT_DLL void _fmpz_mpoly_compose_mat(fmpz_mpoly_t A,
732 const fmpz_mpoly_t B, const fmpz_mat_t M,
733 const fmpz_mpoly_ctx_t ctxB, const fmpz_mpoly_ctx_t ctxAC);
734
735 FLINT_DLL int fmpz_mpoly_compose_fmpz_mpoly_geobucket(fmpz_mpoly_t A,
736 const fmpz_mpoly_t B, fmpz_mpoly_struct * const * C,
737 const fmpz_mpoly_ctx_t ctxB, const fmpz_mpoly_ctx_t ctxAC);
738
739 FLINT_DLL int fmpz_mpoly_compose_fmpz_mpoly_horner(fmpz_mpoly_t A,
740 const fmpz_mpoly_t B, fmpz_mpoly_struct * const * C,
741 const fmpz_mpoly_ctx_t ctxB, const fmpz_mpoly_ctx_t ctxAC);
742
743 FLINT_DLL int fmpz_mpoly_compose_fmpz_mpoly(fmpz_mpoly_t A,
744 const fmpz_mpoly_t B, fmpz_mpoly_struct * const * C,
745 const fmpz_mpoly_ctx_t ctxB, const fmpz_mpoly_ctx_t ctxAC);
746
747 FLINT_DLL void fmpz_mpoly_compose_fmpz_mpoly_gen(fmpz_mpoly_t A,
748 const fmpz_mpoly_t B, const slong * c,
749 const fmpz_mpoly_ctx_t ctxB, const fmpz_mpoly_ctx_t ctxAC);
750
751
752 /* Multiplication ************************************************************/
753
754 FLINT_DLL void fmpz_mpoly_mul(fmpz_mpoly_t A,
755 const fmpz_mpoly_t B, const fmpz_mpoly_t C, const fmpz_mpoly_ctx_t ctx);
756
757 FLINT_DLL void fmpz_mpoly_mul_johnson(fmpz_mpoly_t A,
758 const fmpz_mpoly_t B, const fmpz_mpoly_t C, const fmpz_mpoly_ctx_t ctx);
759
760 FLINT_DLL void fmpz_mpoly_mul_heap_threaded(fmpz_mpoly_t A,
761 const fmpz_mpoly_t B, const fmpz_mpoly_t C, const fmpz_mpoly_ctx_t ctx);
762
763 FLINT_DLL int fmpz_mpoly_mul_array(fmpz_mpoly_t A,
764 const fmpz_mpoly_t B, const fmpz_mpoly_t C, const fmpz_mpoly_ctx_t ctx);
765
766 FLINT_DLL int fmpz_mpoly_mul_array_threaded(fmpz_mpoly_t A,
767 const fmpz_mpoly_t B, const fmpz_mpoly_t C, const fmpz_mpoly_ctx_t ctx);
768
769 FLINT_DLL int fmpz_mpoly_mul_dense(fmpz_mpoly_t A,
770 const fmpz_mpoly_t B, const fmpz_mpoly_t C, const fmpz_mpoly_ctx_t ctx);
771
772 FLINT_DLL slong _fmpz_mpoly_mul_johnson(fmpz ** poly1, ulong ** exp1, slong * alloc,
773 const fmpz * poly2, const ulong * exp2, slong len2,
774 const fmpz * poly3, const ulong * exp3, slong len3,
775 flint_bitcnt_t bits, slong N, const ulong * cmpmask);
776
777 FLINT_DLL void _fmpz_mpoly_mul_johnson_maxfields(fmpz_mpoly_t A,
778 const fmpz_mpoly_t B, fmpz * maxBfields,
779 const fmpz_mpoly_t C, fmpz * maxCfields,
780 const fmpz_mpoly_ctx_t ctx);
781
782 FLINT_DLL void _fmpz_mpoly_mul_heap_threaded_pool_maxfields(fmpz_mpoly_t A,
783 const fmpz_mpoly_t B, fmpz * maxBfields,
784 const fmpz_mpoly_t C, fmpz * maxCfields, const fmpz_mpoly_ctx_t ctx,
785 const thread_pool_handle * handles, slong num_handles);
786
787 FLINT_DLL int _fmpz_mpoly_mul_array_DEG(fmpz_mpoly_t A,
788 const fmpz_mpoly_t B, fmpz * maxBfields,
789 const fmpz_mpoly_t C, fmpz * maxCfields,
790 const fmpz_mpoly_ctx_t ctx);
791
792 FLINT_DLL int _fmpz_mpoly_mul_array_LEX(fmpz_mpoly_t A,
793 const fmpz_mpoly_t B, fmpz * maxBfields,
794 const fmpz_mpoly_t C, fmpz * maxCfields,
795 const fmpz_mpoly_ctx_t ctx);
796
797 FLINT_DLL int _fmpz_mpoly_mul_array_threaded_pool_DEG(fmpz_mpoly_t A,
798 const fmpz_mpoly_t B, fmpz * maxBfields,
799 const fmpz_mpoly_t C, fmpz * maxCfields, const fmpz_mpoly_ctx_t ctx,
800 const thread_pool_handle * handles, slong num_handles);
801
802 FLINT_DLL int _fmpz_mpoly_mul_array_threaded_pool_LEX(fmpz_mpoly_t A,
803 const fmpz_mpoly_t B, fmpz * maxBfields,
804 const fmpz_mpoly_t C, fmpz * maxCfields, const fmpz_mpoly_ctx_t ctx,
805 const thread_pool_handle * handles, slong num_handles);
806
807 FLINT_DLL int _fmpz_mpoly_mul_dense(fmpz_mpoly_t P,
808 const fmpz_mpoly_t A, fmpz * maxAfields,
809 const fmpz_mpoly_t B, fmpz * maxBfields,
810 const fmpz_mpoly_ctx_t ctx);
811
812 /* Powering ******************************************************************/
813
814 FLINT_DLL int fmpz_mpoly_pow_fmpz(fmpz_mpoly_t A, const fmpz_mpoly_t B,
815 const fmpz_t k, const fmpz_mpoly_ctx_t ctx);
816
817 FLINT_DLL int fmpz_mpoly_pow_ui(fmpz_mpoly_t A, const fmpz_mpoly_t B,
818 ulong k, const fmpz_mpoly_ctx_t ctx);
819
820 /* Division ******************************************************************/
821
822 FLINT_DLL int fmpz_mpoly_divides(fmpz_mpoly_t Q,
823 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
824
825 FLINT_DLL int fmpz_mpoly_divides_monagan_pearce(fmpz_mpoly_t Q,
826 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
827
828 FLINT_DLL int fmpz_mpoly_divides_heap_threaded(fmpz_mpoly_t Q,
829 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
830
831 FLINT_DLL int _fmpz_mpoly_divides_heap_threaded_pool(fmpz_mpoly_t Q,
832 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx,
833 const thread_pool_handle * handles, slong num_handles);
834
835 FLINT_DLL slong _fmpz_mpoly_divides_array(fmpz ** poly1, ulong ** exp1,
836 slong * alloc, const fmpz * poly2, const ulong * exp2, slong len2,
837 const fmpz * poly3, const ulong * exp3, slong len3,
838 slong * mults, slong num, slong bits);
839
840 FLINT_DLL int fmpz_mpoly_divides_array(fmpz_mpoly_t poly1,
841 const fmpz_mpoly_t poly2, const fmpz_mpoly_t poly3,
842 const fmpz_mpoly_ctx_t ctx);
843
844
845 FLINT_DLL int mpoly_divides_select_exps(fmpz_mpoly_t S, fmpz_mpoly_ctx_t zctx,
846 slong nworkers, ulong * Aexp, slong Alen,
847 ulong * Bexp, slong Blen, flint_bitcnt_t bits);
848
849 FLINT_DLL slong _fmpz_mpoly_divides_monagan_pearce(fmpz ** poly1,
850 ulong ** exp1, slong * alloc, const fmpz * poly2,
851 const ulong * exp2, slong len2, const fmpz * poly3,
852 const ulong * exp3, slong len3, flint_bitcnt_t bits, slong N,
853 const ulong * cmpmask);
854
855 FLINT_DLL void fmpz_mpoly_divrem(fmpz_mpoly_t Q, fmpz_mpoly_t R,
856 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
857
858 FLINT_DLL void fmpz_mpoly_quasidivrem(fmpz_t scale, fmpz_mpoly_t Q,
859 fmpz_mpoly_t R, const fmpz_mpoly_t A, const fmpz_mpoly_t B,
860 const fmpz_mpoly_ctx_t ctx);
861
862 FLINT_DLL void fmpz_mpoly_div(fmpz_mpoly_t Q, const fmpz_mpoly_t A,
863 const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
864
865 FLINT_DLL void fmpz_mpoly_quasidiv(fmpz_t scale, fmpz_mpoly_t Q,
866 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
867
868 FLINT_DLL void fmpz_mpoly_divrem_ideal(fmpz_mpoly_struct ** Q,
869 fmpz_mpoly_t R, const fmpz_mpoly_t A, fmpz_mpoly_struct * const * B,
870 slong len, const fmpz_mpoly_ctx_t ctx);
871
872 FLINT_DLL void fmpz_mpoly_quasidivrem_ideal(fmpz_t scale,
873 fmpz_mpoly_struct ** Q, fmpz_mpoly_t R, const fmpz_mpoly_t A,
874 fmpz_mpoly_struct * const * B, slong len, const fmpz_mpoly_ctx_t ctx);
875
876 FMPZ_MPOLY_INLINE
fmpz_mpoly_divexact(fmpz_mpoly_t Q,const fmpz_mpoly_t A,const fmpz_mpoly_t B,const fmpz_mpoly_ctx_t ctx)877 void fmpz_mpoly_divexact(fmpz_mpoly_t Q, const fmpz_mpoly_t A,
878 const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx)
879 {
880 if (fmpz_mpoly_divides(Q, A, B, ctx))
881 return;
882
883 flint_throw(FLINT_ERROR, "fmpz_mpoly_divexact: nonexact division");
884 }
885
886 FLINT_DLL slong _fmpz_mpoly_div_monagan_pearce(fmpz ** polyq,
887 ulong ** expq, slong * allocq, const fmpz * poly2,
888 const ulong * exp2, slong len2, const fmpz * poly3, const ulong * exp3,
889 slong len3, slong bits, slong N, const ulong * cmpmask);
890
891 FLINT_DLL void fmpz_mpoly_div_monagan_pearce(fmpz_mpoly_t q,
892 const fmpz_mpoly_t poly2, const fmpz_mpoly_t poly3,
893 const fmpz_mpoly_ctx_t ctx);
894
895 FLINT_DLL slong _fmpz_mpoly_divrem_monagan_pearce(slong * lenr,
896 fmpz ** polyq, ulong ** expq, slong * allocq, fmpz ** polyr,
897 ulong ** expr, slong * allocr, const fmpz * poly2,
898 const ulong * exp2, slong len2, const fmpz * poly3, const ulong * exp3,
899 slong len3, slong bits, slong N, const ulong * cmpmask);
900
901 FLINT_DLL void fmpz_mpoly_divrem_monagan_pearce(fmpz_mpoly_t q, fmpz_mpoly_t r,
902 const fmpz_mpoly_t poly2, const fmpz_mpoly_t poly3,
903 const fmpz_mpoly_ctx_t ctx);
904
905 FLINT_DLL slong _fmpz_mpoly_divrem_array(slong * lenr,
906 fmpz ** polyq, ulong ** expq, slong * allocq,
907 fmpz ** polyr, ulong ** expr, slong * allocr,
908 const fmpz * poly2, const ulong * exp2, slong len2,
909 const fmpz * poly3, const ulong * exp3, slong len3, slong * mults,
910 slong num, slong bits);
911
912 FLINT_DLL int fmpz_mpoly_divrem_array(fmpz_mpoly_t q, fmpz_mpoly_t r,
913 const fmpz_mpoly_t poly2, const fmpz_mpoly_t poly3,
914 const fmpz_mpoly_ctx_t ctx);
915
916 FLINT_DLL void fmpz_mpoly_quasidivrem_heap(fmpz_t scale,
917 fmpz_mpoly_t q, fmpz_mpoly_t r,
918 const fmpz_mpoly_t poly2, const fmpz_mpoly_t poly3,
919 const fmpz_mpoly_ctx_t ctx);
920
921 FLINT_DLL void fmpz_mpoly_quasidiv_heap(fmpz_t scale, fmpz_mpoly_t q,
922 const fmpz_mpoly_t poly2, const fmpz_mpoly_t poly3,
923 const fmpz_mpoly_ctx_t ctx);
924
925 FLINT_DLL slong
926 _fmpz_mpoly_divrem_ideal_monagan_pearce(fmpz_mpoly_struct ** polyq,
927 fmpz ** polyr, ulong ** expr, slong * allocr, const fmpz * poly2,
928 const ulong * exp2, slong len2, fmpz_mpoly_struct * const * poly3,
929 ulong * const * exp3, slong len, slong N, slong bits,
930 const fmpz_mpoly_ctx_t ctx, const ulong * cmpmask);
931
932 FLINT_DLL void
933 fmpz_mpoly_divrem_ideal_monagan_pearce(fmpz_mpoly_struct ** q, fmpz_mpoly_t r,
934 const fmpz_mpoly_t poly2, fmpz_mpoly_struct * const * poly3, slong len,
935 const fmpz_mpoly_ctx_t ctx);
936
937 FLINT_DLL void
938 fmpz_mpoly_quasidivrem_ideal_heap(fmpz_t scale,
939 fmpz_mpoly_struct ** q, fmpz_mpoly_t r,
940 const fmpz_mpoly_t poly2, fmpz_mpoly_struct * const * poly3,
941 slong len, const fmpz_mpoly_ctx_t ctx);
942
943 /* Square root ***************************************************************/
944
945 FLINT_DLL slong _fmpz_mpoly_sqrt_heap(fmpz ** polyq, ulong ** expq,
946 slong * allocq, const fmpz * poly2, const ulong * exp2, slong len2,
947 flint_bitcnt_t bits, const mpoly_ctx_t mctx, int check);
948
949 FLINT_DLL int fmpz_mpoly_sqrt_heap(fmpz_mpoly_t q, const fmpz_mpoly_t poly2,
950 const fmpz_mpoly_ctx_t ctx, int check);
951
952 FMPZ_MPOLY_INLINE
fmpz_mpoly_sqrt(fmpz_mpoly_t q,const fmpz_mpoly_t poly2,const fmpz_mpoly_ctx_t ctx)953 int fmpz_mpoly_sqrt(fmpz_mpoly_t q, const fmpz_mpoly_t poly2,
954 const fmpz_mpoly_ctx_t ctx)
955 {
956 return fmpz_mpoly_sqrt_heap(q, poly2, ctx, 1);
957 }
958
959 FMPZ_MPOLY_INLINE
fmpz_mpoly_is_square(const fmpz_mpoly_t poly2,const fmpz_mpoly_ctx_t ctx)960 int fmpz_mpoly_is_square(const fmpz_mpoly_t poly2, const fmpz_mpoly_ctx_t ctx)
961 {
962 int res;
963 fmpz_mpoly_t q;
964 fmpz_mpoly_init(q, ctx);
965 res = fmpz_mpoly_sqrt_heap(q, poly2, ctx, 1);
966 fmpz_mpoly_clear(q, ctx);
967 return res;
968 }
969
970 /* GCD ***********************************************************************/
971
972 FLINT_DLL void fmpz_mpoly_term_content(fmpz_mpoly_t M, const fmpz_mpoly_t A,
973 const fmpz_mpoly_ctx_t ctx);
974
975 FLINT_DLL int fmpz_mpoly_content_vars(fmpz_mpoly_t g, const fmpz_mpoly_t A,
976 slong * vars, slong vars_length, const fmpz_mpoly_ctx_t ctx);
977
978 FLINT_DLL int fmpz_mpoly_gcd(fmpz_mpoly_t G,
979 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
980
981 FLINT_DLL int fmpz_mpoly_gcd_cofactors(fmpz_mpoly_t G,
982 fmpz_mpoly_t Abar, fmpz_mpoly_t Bbar, const fmpz_mpoly_t A,
983 const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
984
985 FLINT_DLL void fmpz_mpoly_deflation(fmpz * shift, fmpz * stride,
986 const fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx);
987
988 FLINT_DLL void fmpz_mpoly_deflate(fmpz_mpoly_t A, const fmpz_mpoly_t B,
989 const fmpz * shift, const fmpz * stride, const fmpz_mpoly_ctx_t ctx);
990
991 FLINT_DLL void fmpz_mpoly_inflate(fmpz_mpoly_t A, const fmpz_mpoly_t B,
992 const fmpz * shift, const fmpz * stride, const fmpz_mpoly_ctx_t ctx);
993
994 FLINT_DLL int fmpz_mpoly_gcd_hensel(fmpz_mpoly_t G,
995 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
996
997 FLINT_DLL int fmpz_mpoly_gcd_brown(fmpz_mpoly_t G,
998 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
999
1000 FLINT_DLL int fmpz_mpoly_gcd_subresultant(fmpz_mpoly_t G,
1001 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
1002
1003 FLINT_DLL int fmpz_mpoly_gcd_zippel(fmpz_mpoly_t G,
1004 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
1005
1006 FLINT_DLL int fmpz_mpoly_gcd_zippel2(fmpz_mpoly_t G,
1007 const fmpz_mpoly_t A, const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx);
1008
1009 /* Univariates ***************************************************************/
1010
1011 FLINT_DLL void fmpz_mpoly_univar_init(fmpz_mpoly_univar_t A,
1012 const fmpz_mpoly_ctx_t ctx);
1013
1014 FLINT_DLL void fmpz_mpoly_univar_clear(fmpz_mpoly_univar_t A,
1015 const fmpz_mpoly_ctx_t ctx);
1016
1017 FLINT_DLL void fmpz_mpoly_univar_fit_length(fmpz_mpoly_univar_t A,
1018 slong length, const fmpz_mpoly_ctx_t ctx);
1019
1020 FLINT_DLL void fmpz_mpoly_univar_print_pretty(const fmpz_mpoly_univar_t A,
1021 const char ** x, const fmpz_mpoly_ctx_t ctx);
1022
1023 FLINT_DLL void fmpz_mpoly_univar_assert_canonical(fmpz_mpoly_univar_t A,
1024 const fmpz_mpoly_ctx_t ctx);
1025
1026 FMPZ_MPOLY_INLINE
fmpz_mpoly_univar_zero(fmpz_mpoly_univar_t A,const fmpz_mpoly_ctx_t ctx)1027 void fmpz_mpoly_univar_zero(fmpz_mpoly_univar_t A, const fmpz_mpoly_ctx_t ctx)
1028 {
1029 A->length = 0;
1030 }
1031
1032 FLINT_DLL void fmpz_mpoly_univar_set_coeff_ui(fmpz_mpoly_univar_t A,
1033 ulong e, const fmpz_mpoly_t c, const fmpz_mpoly_ctx_t ctx);
1034
1035 FLINT_DLL void fmpz_mpoly_to_univar(fmpz_mpoly_univar_t A,
1036 const fmpz_mpoly_t B, slong var, const fmpz_mpoly_ctx_t ctx);
1037
1038 FLINT_DLL void _fmpz_mpoly_from_univar(fmpz_mpoly_t A, flint_bitcnt_t Abits,
1039 const fmpz_mpoly_univar_t B, slong var, const fmpz_mpoly_ctx_t ctx);
1040
1041 FLINT_DLL void fmpz_mpoly_from_univar(fmpz_mpoly_t A,
1042 const fmpz_mpoly_univar_t B, slong var, const fmpz_mpoly_ctx_t ctx);
1043
1044 FMPZ_MPOLY_INLINE
fmpz_mpoly_univar_swap(fmpz_mpoly_univar_t A,fmpz_mpoly_univar_t B,const fmpz_mpoly_ctx_t ctx)1045 void fmpz_mpoly_univar_swap(fmpz_mpoly_univar_t A, fmpz_mpoly_univar_t B,
1046 const fmpz_mpoly_ctx_t ctx)
1047 {
1048 fmpz_mpoly_univar_struct t = *A;
1049 *A = *B;
1050 *B = t;
1051 }
1052
1053 FMPZ_MPOLY_INLINE
fmpz_mpoly_univar_degree_fits_si(const fmpz_mpoly_univar_t A,const fmpz_mpoly_ctx_t ctx)1054 int fmpz_mpoly_univar_degree_fits_si(const fmpz_mpoly_univar_t A,
1055 const fmpz_mpoly_ctx_t ctx)
1056 {
1057 return A->length == 0 || fmpz_fits_si(A->exps + 0);
1058 }
1059
1060 FMPZ_MPOLY_INLINE
fmpz_mpoly_univar_length(const fmpz_mpoly_univar_t A,const fmpz_mpoly_ctx_t ctx)1061 slong fmpz_mpoly_univar_length(const fmpz_mpoly_univar_t A,
1062 const fmpz_mpoly_ctx_t ctx)
1063 {
1064 return A->length;
1065 }
1066
1067 FMPZ_MPOLY_INLINE
fmpz_mpoly_univar_get_term_exp_si(fmpz_mpoly_univar_t A,slong i,const fmpz_mpoly_ctx_t ctx)1068 slong fmpz_mpoly_univar_get_term_exp_si(fmpz_mpoly_univar_t A, slong i,
1069 const fmpz_mpoly_ctx_t ctx)
1070 {
1071 FLINT_ASSERT((ulong)i < (ulong)A->length);
1072 return fmpz_get_si(A->exps + i);
1073 }
1074
1075 FMPZ_MPOLY_INLINE
fmpz_mpoly_univar_get_term_coeff(fmpz_mpoly_t c,const fmpz_mpoly_univar_t A,slong i,const fmpz_mpoly_ctx_t ctx)1076 void fmpz_mpoly_univar_get_term_coeff(fmpz_mpoly_t c,
1077 const fmpz_mpoly_univar_t A, slong i, const fmpz_mpoly_ctx_t ctx)
1078 {
1079 FLINT_ASSERT((ulong)i < (ulong)A->length);
1080 fmpz_mpoly_set(c, A->coeffs + i, ctx);
1081 }
1082
1083 FMPZ_MPOLY_INLINE
fmpz_mpoly_univar_swap_term_coeff(fmpz_mpoly_t c,fmpz_mpoly_univar_t A,slong i,const fmpz_mpoly_ctx_t ctx)1084 void fmpz_mpoly_univar_swap_term_coeff(fmpz_mpoly_t c,
1085 fmpz_mpoly_univar_t A, slong i, const fmpz_mpoly_ctx_t ctx)
1086 {
1087 FLINT_ASSERT((ulong)i < (ulong)A->length);
1088 fmpz_mpoly_swap(c, A->coeffs + i, ctx);
1089 }
1090
1091 FLINT_DLL int fmpz_mpoly_univar_pseudo_gcd(fmpz_mpoly_univar_t gx,
1092 const fmpz_mpoly_univar_t ax, const fmpz_mpoly_univar_t bx,
1093 const fmpz_mpoly_ctx_t ctx);
1094
1095 FLINT_DLL int fmpz_mpoly_univar_resultant(fmpz_mpoly_t d,
1096 const fmpz_mpoly_univar_t ax, const fmpz_mpoly_univar_t bx,
1097 const fmpz_mpoly_ctx_t ctx);
1098
1099 FLINT_DLL int fmpz_mpoly_univar_discriminant(fmpz_mpoly_t d,
1100 const fmpz_mpoly_univar_t fx, const fmpz_mpoly_ctx_t ctx);
1101
1102 FLINT_DLL int fmpz_mpoly_resultant(fmpz_mpoly_t R, const fmpz_mpoly_t A,
1103 const fmpz_mpoly_t B, slong var, const fmpz_mpoly_ctx_t ctx);
1104
1105 FLINT_DLL int fmpz_mpoly_discriminant(fmpz_mpoly_t R, const fmpz_mpoly_t A,
1106 slong var, const fmpz_mpoly_ctx_t ctx);
1107
1108 /******************************************************************************
1109
1110 Internal functions (guaranteed to change without notice)
1111
1112 ******************************************************************************/
1113
1114 FLINT_DLL void mpoly_void_ring_init_fmpz_mpoly_ctx(mpoly_void_ring_t R,
1115 const fmpz_mpoly_ctx_t ctx);
1116
1117 FLINT_DLL void fmpz_mpoly_pow_fps(fmpz_mpoly_t A, const fmpz_mpoly_t B,
1118 ulong k, const fmpz_mpoly_ctx_t ctx);
1119
1120 FLINT_DLL void fmpz_mpolyl_lead_coeff(fmpz_mpoly_t c, const fmpz_mpoly_t A,
1121 slong num_vars, const fmpz_mpoly_ctx_t ctx);
1122
1123 FLINT_DLL int fmpz_mpolyl_content(fmpz_mpoly_t g, const fmpz_mpoly_t A,
1124 slong num_vars, const fmpz_mpoly_ctx_t ctx);
1125
1126 FLINT_DLL void _fmpz_mpoly_to_fmpz_poly_deflate(fmpz_poly_t A,
1127 const fmpz_mpoly_t B, slong var, const ulong * Bshift,
1128 const ulong * Bstride, const fmpz_mpoly_ctx_t ctx);
1129
1130 FLINT_DLL void _fmpz_mpoly_from_fmpz_poly_inflate(fmpz_mpoly_t A,
1131 flint_bitcnt_t Abits, const fmpz_poly_t B, slong var, const ulong * Ashift,
1132 const ulong * Astride, const fmpz_mpoly_ctx_t ctx);
1133
1134 FLINT_DLL int fmpz_mpoly_repack_bits(fmpz_mpoly_t A, const fmpz_mpoly_t B,
1135 flint_bitcnt_t Abits, const fmpz_mpoly_ctx_t ctx);
1136
1137 FLINT_DLL int fmpz_mpoly_repack_bits_inplace(fmpz_mpoly_t A, flint_bitcnt_t Abits,
1138 const fmpz_mpoly_ctx_t ctx);
1139
1140 typedef struct _fmpz_mpoly_stripe_struct
1141 {
1142 char * big_mem;
1143 slong big_mem_alloc;
1144 slong N;
1145 flint_bitcnt_t bits;
1146 const ulong * cmpmask;
1147 slong * startidx;
1148 slong * endidx;
1149 ulong * emin;
1150 ulong * emax;
1151 flint_bitcnt_t coeff_bits;
1152 int upperclosed;
1153 int flint_small;
1154 } fmpz_mpoly_stripe_struct;
1155
1156 typedef fmpz_mpoly_stripe_struct fmpz_mpoly_stripe_t[1];
1157
1158
1159 /* mpolyd ********************************************************************/
1160
1161 typedef struct
1162 {
1163 slong nvars;
1164 slong * perm;
1165 } fmpz_mpolyd_ctx_struct;
1166
1167 typedef fmpz_mpolyd_ctx_struct fmpz_mpolyd_ctx_t[1];
1168
1169
1170 FLINT_DLL void fmpz_mpolyd_init(fmpz_mpolyd_t poly, slong nvars);
1171
1172 FLINT_DLL void fmpz_mpolyd_fit_length(fmpz_mpolyd_t poly, slong len);
1173
1174 FLINT_DLL void fmpz_mpolyd_clear(fmpz_mpolyd_t poly);
1175
1176 /*****************************************************************************/
1177
1178 typedef struct {
1179 fmpz * powers;
1180 slong length;
1181 slong alloc;
1182 fmpz_t tmp;
1183 } fmpz_pow_cache_t[1];
1184
1185 void fmpz_pow_cache_init(fmpz_pow_cache_t T, const fmpz_t val);
1186
1187 void fmpz_pow_cache_clear(fmpz_pow_cache_t T);
1188
1189 int fmpz_pow_cache_mulpow_ui(fmpz_t a, const fmpz_t b, ulong k,
1190 fmpz_pow_cache_t T);
1191
1192 int fmpz_pow_cache_mulpow_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t k,
1193 fmpz_pow_cache_t T);
1194
1195 /*****************************************************************************/
1196
1197 FLINT_DLL void fmpz_mpoly_to_mpoly_perm_deflate_threaded_pool(
1198 fmpz_mpoly_t A, const fmpz_mpoly_ctx_t lctx,
1199 const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t ctx,
1200 const slong * perm, const ulong * shift, const ulong * stride,
1201 const thread_pool_handle * handles, slong num_handles);
1202
1203 FLINT_DLL void fmpz_mpoly_from_mpoly_perm_inflate(
1204 fmpz_mpoly_t A, flint_bitcnt_t Abits, const fmpz_mpoly_ctx_t ctx,
1205 const fmpz_mpoly_t B, const fmpz_mpoly_ctx_t lctx,
1206 const slong * perm, const ulong * shift, const ulong * stride);
1207
1208 FLINT_DLL void fmpz_mpoly_height(fmpz_t max,
1209 const fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx);
1210
1211 FLINT_DLL void fmpz_mpoly_heights(fmpz_t max, fmpz_t sum,
1212 const fmpz_mpoly_t A, const fmpz_mpoly_ctx_t ctx);
1213
1214 /* geobuckets ****************************************************************/
1215
1216 typedef struct fmpz_mpoly_geobucket
1217 {
1218 fmpz_mpoly_struct polys[FLINT_BITS/2];
1219 fmpz_mpoly_struct temps[FLINT_BITS/2];
1220 slong length;
1221 } fmpz_mpoly_geobucket_struct;
1222
1223 typedef fmpz_mpoly_geobucket_struct fmpz_mpoly_geobucket_t[1];
1224
1225 FLINT_DLL void fmpz_mpoly_geobucket_init(fmpz_mpoly_geobucket_t B,
1226 const fmpz_mpoly_ctx_t ctx);
1227
1228 FLINT_DLL void fmpz_mpoly_geobucket_clear(fmpz_mpoly_geobucket_t B,
1229 const fmpz_mpoly_ctx_t ctx);
1230
1231 FLINT_DLL void fmpz_mpoly_geobucket_empty(fmpz_mpoly_t p,
1232 fmpz_mpoly_geobucket_t B, const fmpz_mpoly_ctx_t ctx);
1233
1234 FLINT_DLL void fmpz_mpoly_geobucket_fit_length(fmpz_mpoly_geobucket_t B,
1235 slong i, const fmpz_mpoly_ctx_t ctx);
1236
1237 FLINT_DLL void fmpz_mpoly_geobucket_set(fmpz_mpoly_geobucket_t B,
1238 fmpz_mpoly_t p, const fmpz_mpoly_ctx_t ctx);
1239
1240 FLINT_DLL void fmpz_mpoly_geobucket_add(fmpz_mpoly_geobucket_t B,
1241 fmpz_mpoly_t p, const fmpz_mpoly_ctx_t ctx);
1242
1243 FLINT_DLL void fmpz_mpoly_geobucket_sub(fmpz_mpoly_geobucket_t B,
1244 fmpz_mpoly_t p, const fmpz_mpoly_ctx_t ctx);
1245
1246 /* Helpers for array methods *************************************************/
1247
1248 FLINT_DLL void _fmpz_mpoly_mul_array_chunked_DEG(fmpz_mpoly_t P,
1249 const fmpz_mpoly_t A, const fmpz_mpoly_t B,
1250 ulong degb, const fmpz_mpoly_ctx_t ctx);
1251
1252 FLINT_DLL void _fmpz_mpoly_mul_array_chunked_LEX(fmpz_mpoly_t P,
1253 const fmpz_mpoly_t A, const fmpz_mpoly_t B,
1254 const ulong * mults, const fmpz_mpoly_ctx_t ctx);
1255
1256 FLINT_DLL void _fmpz_mpoly_addmul_array1_slong1(ulong * poly1,
1257 const slong * poly2, const ulong * exp2, slong len2,
1258 const slong * poly3, const ulong * exp3, slong len3);
1259
1260 FLINT_DLL void _fmpz_mpoly_addmul_array1_slong(ulong * poly1,
1261 const slong * poly2, const ulong * exp2, slong len2,
1262 const slong * poly3, const ulong * exp3, slong len3);
1263
1264 FLINT_DLL void _fmpz_mpoly_addmul_array1_slong2(ulong * poly1,
1265 const slong * poly2, const ulong * exp2, slong len2,
1266 const slong * poly3, const ulong * exp3, slong len3);
1267
1268 FLINT_DLL void _fmpz_mpoly_addmul_array1_fmpz(fmpz * poly1,
1269 const fmpz * poly2, const ulong * exp2, slong len2,
1270 const fmpz * poly3, const ulong * exp3, slong len3);
1271
1272 FLINT_DLL void _fmpz_mpoly_submul_array1_slong(ulong * poly1,
1273 const slong * poly2, const ulong * exp2, slong len2,
1274 const slong * poly3, const ulong * exp3, slong len3);
1275
1276 FLINT_DLL void _fmpz_mpoly_submul_array1_slong2(ulong * poly1,
1277 const slong * poly2, const ulong * exp2, slong len2,
1278 const slong * poly3, const ulong * exp3, slong len3);
1279
1280 FLINT_DLL void _fmpz_mpoly_submul_array1_slong1(ulong * poly1,
1281 const slong * poly2, const ulong * exp2, slong len2,
1282 const slong * poly3, const ulong * exp3, slong len3);
1283
1284 FLINT_DLL void _fmpz_mpoly_submul_array1_fmpz(fmpz * poly1,
1285 const fmpz * poly2, const ulong * exp2, slong len2,
1286 const fmpz * poly3, const ulong * exp3, slong len3);
1287
1288 FLINT_DLL void _fmpz_mpoly_submul_array1_slong_1(ulong * poly1,
1289 slong d, const ulong exp2,
1290 const slong * poly3, const ulong * exp3, slong len3);
1291
1292 FLINT_DLL void _fmpz_mpoly_submul_array1_slong2_1(ulong * poly1,
1293 slong d, const ulong exp2,
1294 const slong * poly3, const ulong * exp3, slong len3);
1295
1296 FLINT_DLL void _fmpz_mpoly_submul_array1_fmpz_1(fmpz * poly1,
1297 const fmpz_t d, ulong exp2,
1298 const fmpz * poly3, const ulong * exp3, slong len3);
1299
1300 FLINT_DLL slong fmpz_mpoly_append_array_sm1_LEX(fmpz_mpoly_t P,
1301 slong Plen, ulong * coeff_array,
1302 const ulong * mults, slong num, slong array_size, slong top);
1303 FLINT_DLL slong fmpz_mpoly_append_array_sm2_LEX(fmpz_mpoly_t P,
1304 slong Plen, ulong * coeff_array,
1305 const ulong * mults, slong num, slong array_size, slong top);
1306 FLINT_DLL slong fmpz_mpoly_append_array_sm3_LEX(fmpz_mpoly_t P,
1307 slong Plen, ulong * coeff_array,
1308 const ulong * mults, slong num, slong array_size, slong top);
1309 FLINT_DLL slong fmpz_mpoly_append_array_fmpz_LEX(fmpz_mpoly_t P,
1310 slong Plen, fmpz * coeff_array,
1311 const ulong * mults, slong num, slong array_size, slong top);
1312
1313 FLINT_DLL slong fmpz_mpoly_append_array_sm1_DEGLEX(fmpz_mpoly_t P,
1314 slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb);
1315 FLINT_DLL slong fmpz_mpoly_append_array_sm2_DEGLEX(fmpz_mpoly_t P,
1316 slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb);
1317 FLINT_DLL slong fmpz_mpoly_append_array_sm3_DEGLEX(fmpz_mpoly_t P,
1318 slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb);
1319 FLINT_DLL slong fmpz_mpoly_append_array_fmpz_DEGLEX(fmpz_mpoly_t P,
1320 slong Plen, fmpz * coeff_array, slong top, slong nvars, slong degb);
1321
1322 FLINT_DLL slong fmpz_mpoly_append_array_sm1_DEGREVLEX(fmpz_mpoly_t P,
1323 slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb);
1324 FLINT_DLL slong fmpz_mpoly_append_array_sm2_DEGREVLEX(fmpz_mpoly_t P,
1325 slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb);
1326 FLINT_DLL slong fmpz_mpoly_append_array_sm3_DEGREVLEX(fmpz_mpoly_t P,
1327 slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb);
1328 FLINT_DLL slong fmpz_mpoly_append_array_fmpz_DEGREVLEX(fmpz_mpoly_t P,
1329 slong Plen, fmpz * coeff_array, slong top, slong nvars, slong degb);
1330
1331 FLINT_DLL slong _fmpz_mpoly_from_ulong_array(fmpz ** poly1,
1332 ulong ** exp1, slong * alloc, ulong * poly2,
1333 const slong * mults, slong num, slong bits, slong k);
1334
1335 FLINT_DLL slong _fmpz_mpoly_from_ulong_array2(fmpz ** poly1,
1336 ulong ** exp1, slong * alloc, ulong * poly2,
1337 const slong * mults, slong num, slong bits, slong k);
1338
1339 FLINT_DLL slong _fmpz_mpoly_from_ulong_array1(fmpz ** poly1,
1340 ulong ** exp1, slong * alloc, ulong * poly2,
1341 const slong * mults, slong num, slong bits, slong k);
1342
1343 FLINT_DLL slong _fmpz_mpoly_from_fmpz_array(fmpz ** poly1,
1344 ulong ** exp1, slong * alloc, fmpz * poly2,
1345 const slong * mults, slong num, slong bits, slong k);
1346
1347 FLINT_DLL void _fmpz_mpoly_to_ulong_array2(ulong * p, const fmpz * coeffs,
1348 const ulong * exps, slong len);
1349
1350 FLINT_DLL void _fmpz_mpoly_to_ulong_array1(ulong * p, const fmpz * coeffs,
1351 const ulong * exps, slong len);
1352
1353 FLINT_DLL void _fmpz_mpoly_to_ulong_array(ulong * p, const fmpz * coeffs,
1354 const ulong * exps, slong len);
1355
1356 FLINT_DLL void _fmpz_mpoly_to_fmpz_array(fmpz * p, const fmpz * coeffs,
1357 const ulong * exps, slong len);
1358
1359
1360 /* Misc arithmetic - has nothing to do with mpoly, should be moved out *******/
1361
1362 FMPZ_MPOLY_INLINE
_fmpz_mpoly_sub_uiuiui_fmpz(ulong * c,const fmpz_t d)1363 void _fmpz_mpoly_sub_uiuiui_fmpz(ulong * c, const fmpz_t d)
1364 {
1365 fmpz fc = *d;
1366
1367 if (!COEFF_IS_MPZ(fc))
1368 {
1369 ulong f0, f1, f2;
1370 f0 = fc;
1371 f1 = f2 = FLINT_SIGN_EXT(f0);
1372 sub_dddmmmsss(c[2], c[1], c[0], c[2], c[1], c[0], f2, f1, f0);
1373 } else
1374 {
1375 slong size = fmpz_size(d);
1376 __mpz_struct * m = COEFF_TO_PTR(fc);
1377 if (fmpz_sgn(d) < 0)
1378 mpn_add(c, c, 3, m->_mp_d, size);
1379 else
1380 mpn_sub(c, c, 3, m->_mp_d, size);
1381 }
1382 }
1383
1384 FMPZ_MPOLY_INLINE
_fmpz_mpoly_add_uiuiui_fmpz(ulong * c,const fmpz_t d)1385 void _fmpz_mpoly_add_uiuiui_fmpz(ulong * c, const fmpz_t d)
1386 {
1387 fmpz fc = *d;
1388
1389 if (!COEFF_IS_MPZ(fc))
1390 {
1391 ulong f0, f1, f2;
1392 f0 = fc;
1393 f1 = f2 = FLINT_SIGN_EXT(f0);
1394 add_sssaaaaaa(c[2], c[1], c[0], c[2], c[1], c[0], f2, f1, f0);
1395 } else
1396 {
1397 slong size = fmpz_size(d);
1398 __mpz_struct * m = COEFF_TO_PTR(fc);
1399 if (fmpz_sgn(d) < 0)
1400 mpn_sub(c, c, 3, m->_mp_d, size);
1401 else
1402 mpn_add(c, c, 3, m->_mp_d, size);
1403 }
1404 }
1405
1406 FMPZ_MPOLY_INLINE
_fmpz_mpoly_submul_uiuiui_fmpz(ulong * c,slong d1,slong d2)1407 void _fmpz_mpoly_submul_uiuiui_fmpz(ulong * c, slong d1, slong d2)
1408 {
1409 ulong p[2], p2;
1410 smul_ppmm(p[1], p[0], d1, d2);
1411 p2 = FLINT_SIGN_EXT(p[1]);
1412 sub_dddmmmsss(c[2], c[1], c[0], c[2], c[1], c[0], p2, p[1], p[0]);
1413 }
1414
1415 FMPZ_MPOLY_INLINE
_fmpz_mpoly_addmul_uiuiui_fmpz(ulong * c,slong d1,slong d2)1416 void _fmpz_mpoly_addmul_uiuiui_fmpz(ulong * c, slong d1, slong d2)
1417 {
1418 ulong p[2], p2;
1419 smul_ppmm(p[1], p[0], d1, d2);
1420 p2 = FLINT_SIGN_EXT(p[1]);
1421 add_sssaaaaaa(c[2], c[1], c[0], c[2], c[1], c[0], p2, p[1], p[0]);
1422 }
1423
1424
1425 FLINT_DLL mpz_srcptr _fmpz_mpoly_get_mpz_signed_uiuiui(ulong * sm, fmpz x,
1426 mpz_ptr t);
1427
1428 FMPZ_MPOLY_INLINE
flint_mpz_add_signed_uiuiui(mpz_ptr a,mpz_srcptr b,ulong c2,ulong c1,ulong c0)1429 void flint_mpz_add_signed_uiuiui(mpz_ptr a, mpz_srcptr b,
1430 ulong c2, ulong c1, ulong c0)
1431 {
1432 ulong cs, d[3];
1433 mpz_t c;
1434
1435 c->_mp_d = d;
1436 c->_mp_alloc = 3;
1437
1438 cs = FLINT_SIGN_EXT(c2);
1439
1440 sub_dddmmmsss(d[2], d[1], d[0], cs^c2, cs^c1, cs^c0, cs, cs, cs);
1441
1442 c->_mp_size = d[2] != 0 ? 3 :
1443 d[1] != 0 ? 2 :
1444 d[0] != 0;
1445 if (cs != 0)
1446 c->_mp_size = -c->_mp_size;
1447
1448 mpz_add(a, b, c);
1449 }
1450
1451
1452
1453 /******************************************************************************
1454
1455 Internal consistency checks
1456
1457 ******************************************************************************/
1458
1459 /*
1460 test that r is a valid remainder upon division by g
1461 this means that if c*x^a is a term of r and x^a is divisible by the leading
1462 monomial of g, then |c| < |leading coefficient of g|
1463 */
1464 FMPZ_MPOLY_INLINE
fmpz_mpoly_remainder_test(const fmpz_mpoly_t r,const fmpz_mpoly_t g,const fmpz_mpoly_ctx_t ctx)1465 void fmpz_mpoly_remainder_test(const fmpz_mpoly_t r, const fmpz_mpoly_t g,
1466 const fmpz_mpoly_ctx_t ctx)
1467 {
1468 slong i, N, bits;
1469 ulong mask = 0;
1470 ulong * rexp, * gexp;
1471
1472 bits = FLINT_MAX(r->bits, g->bits);
1473 N = mpoly_words_per_exp(bits, ctx->minfo);
1474
1475 if (g->length == 0 )
1476 flint_throw(FLINT_ERROR, "Zero denominator in remainder test");
1477
1478 if (r->length == 0 )
1479 return;
1480
1481 rexp = (ulong *) flint_malloc(N*r->length*sizeof(ulong));
1482 gexp = (ulong *) flint_malloc(N*1 *sizeof(ulong));
1483 mpoly_repack_monomials(rexp, bits, r->exps, r->bits, r->length, ctx->minfo);
1484 mpoly_repack_monomials(gexp, bits, g->exps, g->bits, 1, ctx->minfo);
1485
1486 /* mask with high bit set in each field of exponent vector */
1487 for (i = 0; i < FLINT_BITS/bits; i++)
1488 mask = (mask << bits) + (UWORD(1) << (bits - 1));
1489
1490 for (i = 0; i < r->length; i++)
1491 {
1492 int divides;
1493
1494 if (bits <= FLINT_BITS)
1495 divides = mpoly_monomial_divides_test(rexp + i*N, gexp + 0*N, N, mask);
1496 else
1497 divides = mpoly_monomial_divides_mp_test(rexp + i*N, gexp + 0*N, N, bits);
1498
1499 if (divides && fmpz_cmpabs(g->coeffs + 0, r->coeffs + i) <= 0)
1500 {
1501 flint_printf("fmpz_mpoly_remainder_test FAILED i = %wd\n", i);
1502 flint_printf("rem ");fmpz_mpoly_print_pretty(r, NULL, ctx); printf("\n\n");
1503 flint_printf("den ");fmpz_mpoly_print_pretty(g, NULL, ctx); printf("\n\n");
1504 flint_abort();
1505 }
1506 }
1507
1508 flint_free(rexp);
1509 flint_free(gexp);
1510 }
1511
1512
1513 /*
1514 test that r is a valid remainder upon division by g over Q
1515 this means that no term of r is divisible by lt(g)
1516 */
1517 FMPZ_MPOLY_INLINE
fmpz_mpoly_remainder_strongtest(const fmpz_mpoly_t r,const fmpz_mpoly_t g,const fmpz_mpoly_ctx_t ctx)1518 void fmpz_mpoly_remainder_strongtest(const fmpz_mpoly_t r, const fmpz_mpoly_t g,
1519 const fmpz_mpoly_ctx_t ctx)
1520 {
1521 slong i, N, bits;
1522 ulong mask = 0;
1523 ulong * rexp, * gexp;
1524
1525 bits = FLINT_MAX(r->bits, g->bits);
1526 N = mpoly_words_per_exp(bits, ctx->minfo);
1527
1528 if (g->length == 0 )
1529 flint_throw(FLINT_ERROR, "Zero denominator in remainder test");
1530
1531 if (r->length == 0 )
1532 return;
1533
1534 rexp = (ulong *) flint_malloc(N*r->length*sizeof(ulong));
1535 gexp = (ulong *) flint_malloc(N*1 *sizeof(ulong));
1536 mpoly_repack_monomials(rexp, bits, r->exps, r->bits, r->length, ctx->minfo);
1537 mpoly_repack_monomials(gexp, bits, g->exps, g->bits, 1, ctx->minfo);
1538
1539 /* mask with high bit set in each field of exponent vector */
1540 for (i = 0; i < FLINT_BITS/bits; i++)
1541 mask = (mask << bits) + (UWORD(1) << (bits - 1));
1542
1543 for (i = 0; i < r->length; i++)
1544 {
1545 int divides;
1546
1547 if (bits <= FLINT_BITS)
1548 divides = mpoly_monomial_divides_test(rexp + i*N, gexp + 0*N, N, mask);
1549 else
1550 divides = mpoly_monomial_divides_mp_test(rexp + i*N, gexp + 0*N, N, bits);
1551
1552 if (divides)
1553 {
1554 flint_printf("fmpz_mpoly_remainder_strongtest FAILED i = %wd\n", i);
1555 flint_printf("rem ");fmpz_mpoly_print_pretty(r, NULL, ctx); printf("\n\n");
1556 flint_printf("den ");fmpz_mpoly_print_pretty(g, NULL, ctx); printf("\n\n");
1557 flint_abort();
1558 }
1559 }
1560
1561 flint_free(rexp);
1562 flint_free(gexp);
1563 }
1564
1565 #ifdef __cplusplus
1566 }
1567 #endif
1568
1569 #endif
1570
1571