1 /*
2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013 William Hart
3 Copyright (C) 2009, 2011 Andy Novocin
4 Copyright (C) 2010 Sebastian Pancratz
5 Copyright (C) 2011 Fredrik Johansson
6
7 This file is part of FLINT.
8
9 FLINT is free software: you can redistribute it and/or modify it under
10 the terms of the GNU Lesser General Public License (LGPL) as published
11 by the Free Software Foundation; either version 2.1 of the License, or
12 (at your option) any later version. See <http://www.gnu.org/licenses/>.
13 */
14
15 #ifndef FMPZ_POLY_H
16 #define FMPZ_POLY_H
17
18 #ifdef FMPZ_POLY_INLINES_C
19 #define FMPZ_POLY_INLINE FLINT_DLL
20 #else
21 #define FMPZ_POLY_INLINE static __inline__
22 #endif
23
24 #undef ulong
25 #define ulong ulongxx /* interferes with system includes */
26 #include <stdio.h>
27 #undef ulong
28
29 #include <gmp.h>
30 #define ulong mp_limb_t
31
32 #include "flint.h"
33 #include "fmpz.h"
34 #include "fmpz_vec.h"
35 #include "nmod_poly.h"
36 #include "fmpq.h"
37
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41
42 #define FMPZ_POLY_INV_NEWTON_CUTOFF 32
43 #define FMPZ_POLY_SQRT_DIVCONQUER_CUTOFF 16
44 #define FMPZ_POLY_SQRTREM_DIVCONQUER_CUTOFF 16
45
46 /* Type definitions *********************************************************/
47
48 typedef struct
49 {
50 fmpz * coeffs;
51 slong alloc;
52 slong length;
53 } fmpz_poly_struct;
54
55 typedef fmpz_poly_struct fmpz_poly_t[1];
56
57 typedef struct
58 {
59 fmpz ** powers;
60 slong len;
61 } fmpz_poly_powers_precomp_struct;
62
63 typedef fmpz_poly_powers_precomp_struct fmpz_poly_powers_precomp_t[1];
64
65 typedef struct {
66 fmpz c;
67 fmpz_poly_struct *p;
68 slong *exp;
69 slong num;
70 slong alloc;
71 } fmpz_poly_factor_struct;
72
73 typedef fmpz_poly_factor_struct fmpz_poly_factor_t[1];
74
75 typedef struct
76 {
77 mp_limb_t ** jj; /* used by fft_convolution_precache */
78 slong n;
79 slong len2;
80 slong loglen;
81 slong bits2;
82 slong limbs;
83 fmpz_poly_t poly2;
84 } fmpz_poly_mul_precache_struct;
85
86 typedef fmpz_poly_mul_precache_struct fmpz_poly_mul_precache_t[1];
87
88 /* Memory management ********************************************************/
89
90 FLINT_DLL void fmpz_poly_init(fmpz_poly_t poly);
91
92 FLINT_DLL void fmpz_poly_init2(fmpz_poly_t poly, slong alloc);
93
94 FLINT_DLL void fmpz_poly_realloc(fmpz_poly_t poly, slong alloc);
95
96 FLINT_DLL void fmpz_poly_fit_length(fmpz_poly_t poly, slong len);
97
98 FLINT_DLL void fmpz_poly_clear(fmpz_poly_t poly);
99
100 FLINT_DLL void _fmpz_poly_normalise(fmpz_poly_t poly);
101
102 FMPZ_POLY_INLINE
_fmpz_poly_set_length(fmpz_poly_t poly,slong newlen)103 void _fmpz_poly_set_length(fmpz_poly_t poly, slong newlen)
104 {
105 if (poly->length > newlen)
106 {
107 slong i;
108 for (i = newlen; i < poly->length; i++)
109 _fmpz_demote(poly->coeffs + i);
110 }
111 poly->length = newlen;
112 }
113
114 FMPZ_POLY_INLINE
fmpz_poly_attach_truncate(fmpz_poly_t trunc,const fmpz_poly_t poly,slong n)115 void fmpz_poly_attach_truncate(fmpz_poly_t trunc,
116 const fmpz_poly_t poly, slong n)
117 {
118 trunc->coeffs = poly->coeffs;
119 trunc->alloc = poly->alloc;
120 trunc->length = FLINT_MIN(poly->length, n);
121 }
122
123 FMPZ_POLY_INLINE
fmpz_poly_attach_shift(fmpz_poly_t trunc,const fmpz_poly_t poly,slong n)124 void fmpz_poly_attach_shift(fmpz_poly_t trunc, const fmpz_poly_t poly, slong n)
125 {
126 trunc->coeffs = poly->coeffs + n;
127 trunc->alloc = poly->alloc - n;
128 trunc->length = FLINT_MAX(poly->length - n, 0);
129 }
130
131 /* Polynomial parameters ***************************************************/
132
133 FMPZ_POLY_INLINE
fmpz_poly_length(const fmpz_poly_t poly)134 slong fmpz_poly_length(const fmpz_poly_t poly)
135 {
136 return poly->length;
137 }
138
139 FMPZ_POLY_INLINE
fmpz_poly_degree(const fmpz_poly_t poly)140 slong fmpz_poly_degree(const fmpz_poly_t poly)
141 {
142 return poly->length - 1;
143 }
144
145 /* Assignment and basic manipulation ***************************************/
146
147 FLINT_DLL void fmpz_poly_set(fmpz_poly_t poly1, const fmpz_poly_t poly2);
148
149 FLINT_DLL void fmpz_poly_set_ui(fmpz_poly_t poly, ulong c);
150
151 FLINT_DLL void fmpz_poly_set_si(fmpz_poly_t poly, slong c);
152
153 FLINT_DLL void fmpz_poly_set_fmpz(fmpz_poly_t poly, const fmpz_t c);
154
155 FLINT_DLL void fmpz_poly_set_mpz(fmpz_poly_t poly, const mpz_t c);
156
157 FLINT_DLL int _fmpz_poly_set_str(fmpz * poly, const char * str);
158
159 FLINT_DLL int fmpz_poly_set_str(fmpz_poly_t poly, const char * str);
160
161 FLINT_DLL char * _fmpz_poly_get_str(const fmpz * poly, slong len);
162
163 FLINT_DLL char * fmpz_poly_get_str(const fmpz_poly_t poly);
164
165 FLINT_DLL char * _fmpz_poly_get_str_pretty(const fmpz * poly, slong len, const char * x);
166
167 FLINT_DLL char * fmpz_poly_get_str_pretty(const fmpz_poly_t poly, const char * x);
168
169 FMPZ_POLY_INLINE
fmpz_poly_zero(fmpz_poly_t poly)170 void fmpz_poly_zero(fmpz_poly_t poly)
171 {
172 _fmpz_poly_set_length(poly, 0);
173 }
174
175 FMPZ_POLY_INLINE
fmpz_poly_one(fmpz_poly_t poly)176 void fmpz_poly_one(fmpz_poly_t poly)
177 {
178 fmpz_poly_set_ui(poly, UWORD(1));
179 }
180
181 FLINT_DLL void fmpz_poly_zero_coeffs(fmpz_poly_t poly, slong i, slong j);
182
183 FLINT_DLL void fmpz_poly_swap(fmpz_poly_t poly1, fmpz_poly_t poly2);
184
185 FLINT_DLL void _fmpz_poly_reverse(fmpz * res, const fmpz * poly, slong len, slong n);
186
187 FLINT_DLL void fmpz_poly_reverse(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
188
189 FLINT_DLL ulong fmpz_poly_deflation(const fmpz_poly_t input);
190
191 FLINT_DLL void fmpz_poly_deflate(fmpz_poly_t result, const fmpz_poly_t input,
192 ulong deflation);
193
194 FLINT_DLL void fmpz_poly_inflate(fmpz_poly_t result, const fmpz_poly_t input,
195 ulong inflation);
196
197 FMPZ_POLY_INLINE
fmpz_poly_truncate(fmpz_poly_t poly,slong newlen)198 void fmpz_poly_truncate(fmpz_poly_t poly, slong newlen)
199 {
200 if (poly->length > newlen)
201 {
202 slong i;
203 for (i = newlen; i < poly->length; i++)
204 _fmpz_demote(poly->coeffs + i);
205 poly->length = newlen;
206 _fmpz_poly_normalise(poly);
207 }
208 }
209
210 FLINT_DLL void fmpz_poly_set_trunc(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
211
212 /* Randomisation ***********************************************************/
213
214 FLINT_DLL void fmpz_poly_randtest(fmpz_poly_t f, flint_rand_t state,
215 slong len, flint_bitcnt_t bits);
216
217 FLINT_DLL void fmpz_poly_randtest_unsigned(fmpz_poly_t f, flint_rand_t state,
218 slong len, flint_bitcnt_t bits);
219
220 FLINT_DLL void fmpz_poly_randtest_not_zero(fmpz_poly_t f, flint_rand_t state,
221 slong len, flint_bitcnt_t bits);
222
223 FLINT_DLL void fmpz_poly_randtest_no_real_root(fmpz_poly_t p, flint_rand_t state,
224 slong len, flint_bitcnt_t bits);
225
226 /* Getting and setting coefficients ****************************************/
227
228 FLINT_DLL slong fmpz_poly_get_coeff_si(const fmpz_poly_t poly, slong n);
229
230 FLINT_DLL void fmpz_poly_set_coeff_si(fmpz_poly_t poly, slong n, slong x);
231
232 FLINT_DLL ulong fmpz_poly_get_coeff_ui(const fmpz_poly_t poly, slong n);
233
234 FLINT_DLL void fmpz_poly_set_coeff_ui(fmpz_poly_t poly, slong n, ulong x);
235
236 FLINT_DLL void fmpz_poly_set_coeff_fmpz(fmpz_poly_t poly, slong n, const fmpz_t x);
237
238 FLINT_DLL void fmpz_poly_get_coeff_fmpz(fmpz_t x, const fmpz_poly_t poly, slong n);
239
240 #define fmpz_poly_get_coeff_ptr(poly, n) \
241 ((n) < (poly)->length ? (poly)->coeffs + (n) : NULL)
242
243 #define fmpz_poly_lead(poly) \
244 ((poly)->length ? (poly)->coeffs + (poly)->length - 1 : NULL)
245
246 /* Comparison **************************************************************/
247
248 FLINT_DLL int fmpz_poly_equal(const fmpz_poly_t poly1, const fmpz_poly_t poly2);
249
250 FLINT_DLL int fmpz_poly_equal_trunc(const fmpz_poly_t poly1,
251 const fmpz_poly_t poly2, slong n);
252
253 #define fmpz_poly_is_zero(poly) \
254 ((poly)->length == 0)
255
256 FMPZ_POLY_INLINE
_fmpz_poly_is_one(const fmpz * poly,slong len)257 int _fmpz_poly_is_one(const fmpz *poly, slong len)
258 {
259 return (len > 0 && fmpz_is_one(poly)
260 && _fmpz_vec_is_zero(poly + 1, len - 1));
261 }
262
263 FMPZ_POLY_INLINE
fmpz_poly_is_one(const fmpz_poly_t op)264 int fmpz_poly_is_one(const fmpz_poly_t op)
265 {
266 return (op->length) == 1 && (*(op->coeffs) == WORD(1));
267 }
268
269 FMPZ_POLY_INLINE
fmpz_poly_is_unit(const fmpz_poly_t op)270 int fmpz_poly_is_unit(const fmpz_poly_t op)
271 {
272 return (op->length == 1) && (*(op->coeffs) == WORD(1) || *(op->coeffs) == WORD(-1));
273 }
274
275 FMPZ_POLY_INLINE
fmpz_poly_is_gen(const fmpz_poly_t op)276 int fmpz_poly_is_gen(const fmpz_poly_t op)
277 {
278 return (op->length) == 2 && (*(op->coeffs + 1) == WORD(1)) && (*(op->coeffs + 0) == WORD(0));
279 }
280
281 /* Deprecated */
282 #define fmpz_poly_is_x fmpz_poly_is_gen
283
284 FMPZ_POLY_INLINE
fmpz_poly_equal_fmpz(const fmpz_poly_t poly,const fmpz_t c)285 int fmpz_poly_equal_fmpz(const fmpz_poly_t poly, const fmpz_t c)
286 {
287 return ((poly->length == 0) && fmpz_is_zero(c)) ||
288 ((poly->length == 1) && fmpz_equal(poly->coeffs, c));
289 }
290
291 /* Addition and subtraction ************************************************/
292
293 FLINT_DLL void _fmpz_poly_add(fmpz * res, const fmpz * poly1, slong len1,
294 const fmpz * poly2, slong len2);
295
296 FLINT_DLL void fmpz_poly_add(fmpz_poly_t res, const fmpz_poly_t poly1,
297 const fmpz_poly_t poly2);
298
299 FLINT_DLL void fmpz_poly_add_series(fmpz_poly_t res, const fmpz_poly_t poly1,
300 const fmpz_poly_t poly2, slong n);
301
302 FLINT_DLL void _fmpz_poly_sub(fmpz * res, const fmpz * poly1, slong len1,
303 const fmpz * poly2, slong len2);
304
305 FLINT_DLL void fmpz_poly_sub(fmpz_poly_t res, const fmpz_poly_t poly1,
306 const fmpz_poly_t poly2);
307
308 FLINT_DLL void fmpz_poly_sub_series(fmpz_poly_t res, const fmpz_poly_t poly1,
309 const fmpz_poly_t poly2, slong n);
310
311 FLINT_DLL void fmpz_poly_neg(fmpz_poly_t res, const fmpz_poly_t poly);
312
313 /* Scalar absolute value multiplication and division ***********************/
314
315 FLINT_DLL void fmpz_poly_scalar_abs(fmpz_poly_t res, const fmpz_poly_t poly);
316
317 FLINT_DLL void fmpz_poly_scalar_mul_ui(fmpz_poly_t poly1,
318 const fmpz_poly_t poly2, ulong x);
319
320 FLINT_DLL void fmpz_poly_scalar_mul_si(fmpz_poly_t poly1,
321 const fmpz_poly_t poly2, slong x);
322
323 FLINT_DLL void fmpz_poly_scalar_mul_fmpz(fmpz_poly_t poly1,
324 const fmpz_poly_t poly2, const fmpz_t x);
325
326 FLINT_DLL void fmpz_poly_scalar_addmul_fmpz(fmpz_poly_t poly1,
327 const fmpz_poly_t poly2, const fmpz_t x);
328
329 FLINT_DLL void fmpz_poly_scalar_submul_fmpz(fmpz_poly_t poly1,
330 const fmpz_poly_t poly2, const fmpz_t x);
331
332 FLINT_DLL void fmpz_poly_scalar_fdiv_ui(fmpz_poly_t poly1,
333 const fmpz_poly_t poly2, ulong x);
334
335 FLINT_DLL void fmpz_poly_scalar_fdiv_si(fmpz_poly_t poly1,
336 const fmpz_poly_t poly2, slong x);
337
338 FLINT_DLL void fmpz_poly_scalar_fdiv_fmpz(fmpz_poly_t poly1,
339 const fmpz_poly_t poly2, const fmpz_t x);
340
341 FLINT_DLL void fmpz_poly_scalar_tdiv_ui(fmpz_poly_t poly1,
342 const fmpz_poly_t poly2, ulong x);
343
344 FLINT_DLL void fmpz_poly_scalar_tdiv_si(fmpz_poly_t poly1,
345 const fmpz_poly_t poly2, slong x);
346
347 FLINT_DLL void fmpz_poly_scalar_tdiv_fmpz(fmpz_poly_t poly1,
348 const fmpz_poly_t poly2, const fmpz_t x);
349
350 FLINT_DLL void fmpz_poly_scalar_divexact_ui(fmpz_poly_t poly1,
351 const fmpz_poly_t poly2, ulong x);
352
353 FLINT_DLL void fmpz_poly_scalar_divexact_si(fmpz_poly_t poly1,
354 const fmpz_poly_t poly2, slong x);
355
356 FLINT_DLL void fmpz_poly_scalar_divexact_fmpz(fmpz_poly_t poly1,
357 const fmpz_poly_t poly2, const fmpz_t x);
358
359 FLINT_DLL void fmpz_poly_scalar_fdiv_2exp(fmpz_poly_t poly1, const fmpz_poly_t poly2,
360 ulong exp);
361
362 FLINT_DLL void fmpz_poly_scalar_tdiv_2exp(fmpz_poly_t poly1, const fmpz_poly_t poly2,
363 ulong exp);
364
365 FLINT_DLL void fmpz_poly_scalar_mul_2exp(fmpz_poly_t poly1, const fmpz_poly_t poly2,
366 ulong exp);
367
368 FMPZ_POLY_INLINE
fmpz_poly_scalar_mod_fmpz(fmpz_poly_t poly1,const fmpz_poly_t poly2,const fmpz_t x)369 void fmpz_poly_scalar_mod_fmpz(fmpz_poly_t poly1,
370 const fmpz_poly_t poly2, const fmpz_t x)
371 {
372 if (poly2->length == 0)
373 {
374 fmpz_poly_zero(poly1);
375 }
376 else
377 {
378 fmpz_poly_fit_length(poly1, poly2->length);
379 _fmpz_vec_scalar_mod_fmpz(poly1->coeffs, poly2->coeffs, poly2->length, x);
380 _fmpz_poly_set_length(poly1, poly2->length);
381 _fmpz_poly_normalise(poly1);
382 }
383 }
384
385 FMPZ_POLY_INLINE
fmpz_poly_scalar_smod_fmpz(fmpz_poly_t poly1,const fmpz_poly_t poly2,const fmpz_t x)386 void fmpz_poly_scalar_smod_fmpz(fmpz_poly_t poly1,
387 const fmpz_poly_t poly2, const fmpz_t x)
388 {
389 if (poly2->length == 0)
390 {
391 fmpz_poly_zero(poly1);
392 }
393 else
394 {
395 fmpz_poly_fit_length(poly1, poly2->length);
396 _fmpz_vec_scalar_smod_fmpz(poly1->coeffs, poly2->coeffs, poly2->length, x);
397 _fmpz_poly_set_length(poly1, poly2->length);
398 _fmpz_poly_normalise(poly1);
399
400 }
401 }
402
403 FLINT_DLL slong _fmpz_poly_remove_content_2exp(fmpz * pol, slong len);
404
405 FLINT_DLL void _fmpz_poly_scale_2exp(fmpz * pol, slong len, slong k);
406
407 /* Bit packing *************************************************************/
408
409 FLINT_DLL void _fmpz_poly_bit_pack(mp_ptr arr, const fmpz * poly,
410 slong len, flint_bitcnt_t bit_size, int negate);
411
412 FLINT_DLL int _fmpz_poly_bit_unpack(fmpz * poly, slong len,
413 mp_srcptr arr, flint_bitcnt_t bit_size, int negate);
414
415 FLINT_DLL void _fmpz_poly_bit_unpack_unsigned(fmpz * poly, slong len,
416 mp_srcptr arr, flint_bitcnt_t bit_size);
417
418 FLINT_DLL void fmpz_poly_bit_pack(fmpz_t f, const fmpz_poly_t poly,
419 flint_bitcnt_t bit_size);
420
421 FLINT_DLL void fmpz_poly_bit_unpack(fmpz_poly_t poly, const fmpz_t f,
422 flint_bitcnt_t bit_size);
423
424 FLINT_DLL void fmpz_poly_bit_unpack_unsigned(fmpz_poly_t poly, const fmpz_t f,
425 flint_bitcnt_t bit_size);
426
427
428 /* Multiplication **********************************************************/
429
430 FLINT_DLL void _fmpz_poly_mul_classical(fmpz * res, const fmpz * poly1, slong len1,
431 const fmpz * poly2, slong len2);
432
433 FLINT_DLL void fmpz_poly_mul_classical(fmpz_poly_t res,
434 const fmpz_poly_t poly1, const fmpz_poly_t poly2);
435
436 FLINT_DLL void _fmpz_poly_mullow_classical(fmpz * res, const fmpz * poly1, slong len1,
437 const fmpz * poly2, slong len2, slong n);
438
439 FLINT_DLL void fmpz_poly_mullow_classical(fmpz_poly_t res, const fmpz_poly_t poly1,
440 const fmpz_poly_t poly2, slong n);
441
442 FLINT_DLL void _fmpz_poly_mulhigh_classical(fmpz * res, const fmpz * poly1,
443 slong len1, const fmpz * poly2, slong len2, slong start);
444
445 FLINT_DLL void fmpz_poly_mulhigh_classical(fmpz_poly_t res,
446 const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong start);
447
448 FLINT_DLL void _fmpz_poly_mulmid_classical(fmpz * res, const fmpz * poly1,
449 slong len1, const fmpz * poly2, slong len2);
450
451 FLINT_DLL void fmpz_poly_mulmid_classical(fmpz_poly_t res,
452 const fmpz_poly_t poly1, const fmpz_poly_t poly2);
453
454 FLINT_DLL void fmpz_poly_mul_karatsuba(fmpz_poly_t res,
455 const fmpz_poly_t poly1, const fmpz_poly_t poly2);
456
457 FLINT_DLL void _fmpz_poly_mul_karatsuba(fmpz * res, const fmpz * poly1,
458 slong len1, const fmpz * poly2, slong len2);
459
460 FLINT_DLL void _fmpz_poly_mullow_karatsuba_n(fmpz * res, const fmpz * poly1,
461 const fmpz * poly2, slong n);
462
463 FLINT_DLL void fmpz_poly_mullow_karatsuba_n(fmpz_poly_t res,
464 const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
465
466 FLINT_DLL void _fmpz_poly_mulhigh_karatsuba_n(fmpz * res, const fmpz * poly1,
467 const fmpz * poly2, slong len);
468
469 FLINT_DLL void fmpz_poly_mulhigh_karatsuba_n(fmpz_poly_t res,
470 const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong length);
471
472 FLINT_DLL void _fmpz_poly_mul_KS(fmpz * res, const fmpz * poly1, slong len1,
473 const fmpz * poly2, slong len2);
474
475 FLINT_DLL void fmpz_poly_mul_KS(fmpz_poly_t res,
476 const fmpz_poly_t poly1, const fmpz_poly_t poly2);
477
478 FLINT_DLL void _fmpz_poly_mullow_KS(fmpz * res, const fmpz * poly1, slong len1,
479 const fmpz * poly2, slong len2, slong n);
480
481 FLINT_DLL void fmpz_poly_mullow_KS(fmpz_poly_t res, const fmpz_poly_t poly1,
482 const fmpz_poly_t poly2, slong n);
483
484 FLINT_DLL void _fmpz_poly_mul_SS(fmpz * output, const fmpz * input1, slong length1,
485 const fmpz * input2, slong length2);
486
487 FLINT_DLL void fmpz_poly_mul_SS(fmpz_poly_t res,
488 const fmpz_poly_t poly1, const fmpz_poly_t poly2);
489
490 FLINT_DLL void _fmpz_poly_mullow_SS(fmpz * output, const fmpz * input1, slong length1,
491 const fmpz * input2, slong length2, slong n);
492
493 FLINT_DLL void fmpz_poly_mullow_SS(fmpz_poly_t res,
494 const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
495
496 FLINT_DLL void _fmpz_poly_mul(fmpz * res, const fmpz * poly1,
497 slong len1, const fmpz * poly2, slong len2);
498
499 FLINT_DLL void fmpz_poly_mul(fmpz_poly_t res,
500 const fmpz_poly_t poly1, const fmpz_poly_t poly2);
501
502 FLINT_DLL void _fmpz_poly_mullow(fmpz * res, const fmpz * poly1, slong len1,
503 const fmpz * poly2, slong len2, slong n);
504
505 FLINT_DLL void fmpz_poly_mullow(fmpz_poly_t res,
506 const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
507
508 FLINT_DLL void fmpz_poly_mulhigh_n(fmpz_poly_t res,
509 const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
510
511 /* FFT precached multiplication **********************************************/
512
513 FLINT_DLL void fmpz_poly_mul_SS_precache_init(fmpz_poly_mul_precache_t pre,
514 slong len1, slong bits1, const fmpz_poly_t poly2);
515
516 FLINT_DLL void fmpz_poly_mul_precache_clear(fmpz_poly_mul_precache_t pre);
517
518 FLINT_DLL void _fmpz_poly_mullow_SS_precache(fmpz * output,
519 const fmpz * input1, slong len1, fmpz_poly_mul_precache_t pre, slong trunc);
520
521 FLINT_DLL void fmpz_poly_mullow_SS_precache(fmpz_poly_t res,
522 const fmpz_poly_t poly1, fmpz_poly_mul_precache_t pre, slong n);
523
fmpz_poly_mul_SS_precache(fmpz_poly_t res,const fmpz_poly_t poly1,fmpz_poly_mul_precache_t pre)524 FMPZ_POLY_INLINE void fmpz_poly_mul_SS_precache(fmpz_poly_t res,
525 const fmpz_poly_t poly1, fmpz_poly_mul_precache_t pre)
526 {
527 fmpz_poly_mullow_SS_precache(res, poly1, pre,
528 FLINT_MAX(poly1->length + pre->len2 - 1, 0));
529 }
530
531 /* Squaring ******************************************************************/
532
533 FLINT_DLL void _fmpz_poly_sqr_KS(fmpz * rop, const fmpz * op, slong len);
534
535 FLINT_DLL void fmpz_poly_sqr_KS(fmpz_poly_t rop, const fmpz_poly_t op);
536
537 FLINT_DLL void fmpz_poly_sqr_karatsuba(fmpz_poly_t rop, const fmpz_poly_t op);
538
539 FLINT_DLL void _fmpz_poly_sqr_karatsuba(fmpz * rop, const fmpz * op, slong len);
540
541 FLINT_DLL void _fmpz_poly_sqr_classical(fmpz * rop, const fmpz * op, slong len);
542
543 FLINT_DLL void fmpz_poly_sqr_classical(fmpz_poly_t rop, const fmpz_poly_t op);
544
545 FLINT_DLL void _fmpz_poly_sqr(fmpz * rop, const fmpz * op, slong len);
546
547 FLINT_DLL void fmpz_poly_sqr(fmpz_poly_t rop, const fmpz_poly_t op);
548
549 FLINT_DLL void _fmpz_poly_sqrlow_KS(fmpz * res, const fmpz * poly, slong len, slong n);
550
551 FLINT_DLL void fmpz_poly_sqrlow_KS(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
552
553 FLINT_DLL void _fmpz_poly_sqrlow_karatsuba_n(fmpz * res, const fmpz * poly, slong n);
554
555 FLINT_DLL void fmpz_poly_sqrlow_karatsuba_n(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
556
557 FLINT_DLL void _fmpz_poly_sqrlow_classical(fmpz * res, const fmpz * poly, slong len, slong n);
558
559 FLINT_DLL void fmpz_poly_sqrlow_classical(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
560
561 FLINT_DLL void _fmpz_poly_sqrlow(fmpz * res, const fmpz * poly, slong len, slong n);
562
563 FLINT_DLL void fmpz_poly_sqrlow(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
564
565 /* Powering ****************************************************************/
566
567 FLINT_DLL void _fmpz_poly_pow_multinomial(fmpz * res, const fmpz * poly, slong len, ulong e);
568
569 FLINT_DLL void fmpz_poly_pow_multinomial(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
570
571 FLINT_DLL void _fmpz_poly_pow_binomial(fmpz * res, const fmpz * poly, ulong e);
572
573 FLINT_DLL void fmpz_poly_pow_binomial(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
574
575 FLINT_DLL void _fmpz_poly_pow_binexp(fmpz * res, const fmpz * poly, slong len, ulong e);
576
577 FLINT_DLL void fmpz_poly_pow_binexp(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
578
579 FLINT_DLL void _fmpz_poly_pow_addchains(fmpz * res, const fmpz * poly, slong len, const int * a, int n);
580
581 FLINT_DLL void fmpz_poly_pow_addchains(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
582
583 FLINT_DLL void _fmpz_poly_pow_small(fmpz * res, const fmpz * poly, slong len, ulong e);
584
585 FLINT_DLL void _fmpz_poly_pow(fmpz * res, const fmpz * poly, slong len, ulong e);
586
587 FLINT_DLL void fmpz_poly_pow(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
588
589 FLINT_DLL void _fmpz_poly_pow_trunc(fmpz * res, const fmpz * poly, ulong e, slong n);
590
591 void
592 FLINT_DLL fmpz_poly_pow_trunc(fmpz_poly_t res, const fmpz_poly_t poly, ulong e, slong n);
593
594 /* Shifting ****************************************************************/
595
596 FLINT_DLL void _fmpz_poly_shift_left(fmpz * res, const fmpz * poly, slong len, slong n);
597
598 FLINT_DLL void _fmpz_poly_shift_right(fmpz * res, const fmpz * poly, slong len, slong n);
599
600 FLINT_DLL void fmpz_poly_shift_left(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
601
602 FLINT_DLL void fmpz_poly_shift_right(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
603
604 /* Norms *******************************************************************/
605
606 FLINT_DLL void _fmpz_poly_2norm(fmpz_t res, const fmpz * poly, slong len);
607
608 FLINT_DLL void fmpz_poly_2norm(fmpz_t res, const fmpz_poly_t poly);
609
610 FLINT_DLL flint_bitcnt_t _fmpz_poly_2norm_normalised_bits(const fmpz * poly, slong len);
611
612 FMPZ_POLY_INLINE
fmpz_poly_max_limbs(const fmpz_poly_t poly)613 ulong fmpz_poly_max_limbs(const fmpz_poly_t poly)
614 {
615 return _fmpz_vec_max_limbs(poly->coeffs, poly->length);
616 }
617
618 FMPZ_POLY_INLINE
fmpz_poly_max_bits(const fmpz_poly_t poly)619 slong fmpz_poly_max_bits(const fmpz_poly_t poly)
620 {
621 return _fmpz_vec_max_bits(poly->coeffs, poly->length);
622 }
623
624 FMPZ_POLY_INLINE
fmpz_poly_height(fmpz_t res,const fmpz_poly_t poly)625 void fmpz_poly_height(fmpz_t res, const fmpz_poly_t poly)
626 {
627 _fmpz_vec_height(res, poly->coeffs, poly->length);
628 }
629
630 /* Greatest common divisor *************************************************/
631
632 FLINT_DLL void _fmpz_poly_gcd_subresultant(fmpz * res, const fmpz * poly1, slong len1,
633 const fmpz * poly2, slong len2);
634
635 FLINT_DLL void fmpz_poly_gcd_subresultant(fmpz_poly_t res, const fmpz_poly_t poly1,
636 const fmpz_poly_t poly2);
637
638 FLINT_DLL int _fmpz_poly_gcd_heuristic(fmpz * res, const fmpz * poly1, slong len1,
639 const fmpz * poly2, slong len2);
640
641 FLINT_DLL int fmpz_poly_gcd_heuristic(fmpz_poly_t res,
642 const fmpz_poly_t poly1, const fmpz_poly_t poly2);
643
644 FLINT_DLL void _fmpz_poly_gcd_modular(fmpz * res, const fmpz * poly1, slong len1,
645 const fmpz * poly2, slong len2);
646
647 FLINT_DLL void fmpz_poly_gcd_modular(fmpz_poly_t res,
648 const fmpz_poly_t poly1, const fmpz_poly_t poly2);
649
650 FLINT_DLL void _fmpz_poly_gcd(fmpz * res, const fmpz * poly1, slong len1,
651 const fmpz * poly2, slong len2);
652
653 FLINT_DLL void fmpz_poly_gcd(fmpz_poly_t res, const fmpz_poly_t poly1,
654 const fmpz_poly_t poly2);
655
656 FLINT_DLL void _fmpz_poly_lcm(fmpz * res, const fmpz * poly1, slong len1,
657 const fmpz * poly2, slong len2);
658
659 FLINT_DLL void fmpz_poly_lcm(fmpz_poly_t res, const fmpz_poly_t poly1,
660 const fmpz_poly_t poly2);
661
662 FLINT_DLL void _fmpz_poly_resultant_euclidean(fmpz_t res, const fmpz * poly1, slong len1,
663 const fmpz * poly2, slong len2);
664
665 FLINT_DLL void fmpz_poly_resultant_euclidean(fmpz_t res, const fmpz_poly_t poly1,
666 const fmpz_poly_t poly2);
667
668 FLINT_DLL void _fmpz_poly_resultant_modular(fmpz_t res, const fmpz * poly1, slong len1,
669 const fmpz * poly2, slong len2);
670
671 FLINT_DLL void fmpz_poly_resultant_modular(fmpz_t res, const fmpz_poly_t poly1,
672 const fmpz_poly_t poly2);
673
674 FLINT_DLL void _fmpz_poly_resultant(fmpz_t res, const fmpz * poly1, slong len1,
675 const fmpz * poly2, slong len2);
676
677 FLINT_DLL void fmpz_poly_resultant(fmpz_t res, const fmpz_poly_t poly1,
678 const fmpz_poly_t poly2);
679
680 FLINT_DLL void _fmpz_poly_resultant_modular_div(fmpz_t res,
681 const fmpz * poly1, slong len1,
682 const fmpz * poly2, slong len2, const fmpz_t divisor, slong nbits);
683
684 FLINT_DLL void fmpz_poly_resultant_modular_div(fmpz_t res,
685 const fmpz_poly_t poly1, const fmpz_poly_t poly2,
686 const fmpz_t divisor, slong nbits);
687
688 FLINT_DLL void _fmpz_poly_xgcd_modular(fmpz_t r, fmpz * s, fmpz * t,
689 const fmpz * poly1, slong len1, const fmpz * poly2, slong len2);
690
691 FLINT_DLL void fmpz_poly_xgcd_modular(fmpz_t r, fmpz_poly_t s, fmpz_poly_t t,
692 const fmpz_poly_t poly1, const fmpz_poly_t poly2);
693
694 FMPZ_POLY_INLINE
_fmpz_poly_xgcd(fmpz_t r,fmpz * s,fmpz * t,const fmpz * poly1,slong len1,const fmpz * poly2,slong len2)695 void _fmpz_poly_xgcd(fmpz_t r, fmpz * s, fmpz * t,
696 const fmpz * poly1, slong len1, const fmpz * poly2, slong len2)
697 {
698 _fmpz_poly_xgcd_modular(r, s, t, poly1, len1, poly2, len2);
699 }
700
701 FMPZ_POLY_INLINE
fmpz_poly_xgcd(fmpz_t r,fmpz_poly_t s,fmpz_poly_t t,const fmpz_poly_t poly1,const fmpz_poly_t poly2)702 void fmpz_poly_xgcd(fmpz_t r, fmpz_poly_t s, fmpz_poly_t t,
703 const fmpz_poly_t poly1, const fmpz_poly_t poly2)
704 {
705 fmpz_poly_xgcd_modular(r, s, t, poly1, poly2);
706 }
707
708 /* Discriminant ********************************************************/
709
710 FLINT_DLL void _fmpz_poly_discriminant(fmpz_t res, const fmpz * poly, slong len);
711
712 FLINT_DLL void fmpz_poly_discriminant(fmpz_t res, const fmpz_poly_t poly);
713
714 /* Gaussian content ********************************************************/
715
716 FLINT_DLL void _fmpz_poly_content(fmpz_t res, const fmpz * poly, slong len);
717
718 FLINT_DLL void fmpz_poly_content(fmpz_t res, const fmpz_poly_t poly);
719
720 FLINT_DLL void _fmpz_poly_primitive_part(fmpz * res, const fmpz * poly, slong len);
721
722 FLINT_DLL void fmpz_poly_primitive_part(fmpz_poly_t res, const fmpz_poly_t poly);
723
724 /* Square-free *************************************************************/
725
726 FLINT_DLL int _fmpz_poly_is_squarefree(const fmpz * poly, slong len);
727
728 FLINT_DLL int fmpz_poly_is_squarefree(const fmpz_poly_t poly);
729
730 /* Euclidean division ******************************************************/
731
732 FLINT_DLL int _fmpz_poly_divrem_basecase(fmpz * Q, fmpz * R, const fmpz * A,
733 slong lenA, const fmpz * B, slong lenB, int exact);
734
735 FLINT_DLL void fmpz_poly_divrem_basecase(fmpz_poly_t Q, fmpz_poly_t R,
736 const fmpz_poly_t A, const fmpz_poly_t B);
737
738 FLINT_DLL int _fmpz_poly_divrem_divconquer_recursive(fmpz * Q, fmpz * BQ,
739 fmpz * W, const fmpz * A, const fmpz * B, slong lenB, int exact);
740
741 FLINT_DLL int _fmpz_poly_divrem_divconquer(fmpz * Q, fmpz * R,
742 const fmpz * A, slong lenA, const fmpz * B, slong lenB, int exact);
743
744 FLINT_DLL void fmpz_poly_divrem_divconquer(fmpz_poly_t Q, fmpz_poly_t R,
745 const fmpz_poly_t A, const fmpz_poly_t B);
746
747 FLINT_DLL int _fmpz_poly_divrem(fmpz * Q, fmpz * R, const fmpz * A, slong lenA,
748 const fmpz * B, slong lenB, int exact);
749
750 FLINT_DLL void fmpz_poly_divrem(fmpz_poly_t Q, fmpz_poly_t R,
751 const fmpz_poly_t A, const fmpz_poly_t B);
752
753 FLINT_DLL int _fmpz_poly_div_basecase(fmpz * Q, fmpz * R, const fmpz * A,
754 slong lenA, const fmpz * B, slong lenB, int exact);
755
756 FLINT_DLL void fmpz_poly_div_basecase(fmpz_poly_t Q,
757 const fmpz_poly_t A, const fmpz_poly_t B);
758
759 FLINT_DLL int _fmpz_poly_divremlow_divconquer_recursive(fmpz * Q, fmpz * QB,
760 const fmpz * A, const fmpz * B, slong lenB, int exact);
761
762 FLINT_DLL int _fmpz_poly_div_divconquer_recursive(fmpz * Q, fmpz * temp,
763 const fmpz * A, const fmpz * B, slong lenB, int exact);
764
765 FLINT_DLL int _fmpz_poly_div_divconquer(fmpz * Q, const fmpz * A, slong lenA,
766 const fmpz * B, slong lenB, int exact);
767
768 FLINT_DLL void fmpz_poly_div_divconquer(fmpz_poly_t Q,
769 const fmpz_poly_t A, const fmpz_poly_t B);
770
771 FLINT_DLL int _fmpz_poly_div(fmpz * Q, const fmpz * A, slong lenA,
772 const fmpz * B, slong lenB, int exact);
773
774 FLINT_DLL void fmpz_poly_div(fmpz_poly_t Q, const fmpz_poly_t A,
775 const fmpz_poly_t B);
776
777 FLINT_DLL void _fmpz_poly_preinvert(fmpz * B_inv, const fmpz * B, slong n);
778
779 FLINT_DLL void fmpz_poly_preinvert(fmpz_poly_t B_inv, const fmpz_poly_t B);
780
781 FLINT_DLL void _fmpz_poly_div_preinv(fmpz * Q, const fmpz * A, slong len1,
782 const fmpz * B, const fmpz * B_inv, slong len2);
783
784 FLINT_DLL void fmpz_poly_div_preinv(fmpz_poly_t Q, const fmpz_poly_t A,
785 const fmpz_poly_t B, const fmpz_poly_t B_inv);
786
787 FLINT_DLL void _fmpz_poly_divrem_preinv(fmpz * Q, fmpz * A, slong len1,
788 const fmpz * B, const fmpz * B_inv, slong len2);
789
790 FLINT_DLL void fmpz_poly_divrem_preinv(fmpz_poly_t Q, fmpz_poly_t R,
791 const fmpz_poly_t A, const fmpz_poly_t B, const fmpz_poly_t B_inv);
792
793 FLINT_DLL fmpz ** _fmpz_poly_powers_precompute(const fmpz * B, slong len);
794
795 FLINT_DLL void fmpz_poly_powers_precompute(fmpz_poly_powers_precomp_t pinv,
796 fmpz_poly_t poly);
797
798 FLINT_DLL void _fmpz_poly_powers_clear(fmpz ** powers, slong len);
799
800 FLINT_DLL void fmpz_poly_powers_clear(fmpz_poly_powers_precomp_t pinv);
801
802 FLINT_DLL void _fmpz_poly_rem_powers_precomp(fmpz * A, slong m,
803 const fmpz * B, slong n, fmpz ** const powers);
804
805 FLINT_DLL void fmpz_poly_rem_powers_precomp(fmpz_poly_t R,
806 const fmpz_poly_t A, const fmpz_poly_t B,
807 const fmpz_poly_powers_precomp_t B_inv);
808
809 FLINT_DLL void _fmpz_poly_rem_basecase(fmpz * Q, const fmpz * A, slong lenA,
810 const fmpz * B, slong lenB);
811
812 FLINT_DLL void fmpz_poly_rem_basecase(fmpz_poly_t R,
813 const fmpz_poly_t A, const fmpz_poly_t B);
814
815 FLINT_DLL void _fmpz_poly_rem(fmpz * R, const fmpz * A, slong lenA,
816 const fmpz * B, slong lenB);
817
818 FLINT_DLL void fmpz_poly_rem(fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B);
819
820 FLINT_DLL void fmpz_poly_div_root(fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_t c);
821
822 FLINT_DLL void _fmpz_poly_div_root(fmpz * Q, const fmpz * A, slong len, const fmpz_t c);
823
824 /* Power series division ***************************************************/
825
826 FLINT_DLL void _fmpz_poly_inv_series_basecase(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
827
828 FLINT_DLL void fmpz_poly_inv_series_basecase(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
829
830 FLINT_DLL void _fmpz_poly_inv_series_newton(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
831
832 FLINT_DLL void fmpz_poly_inv_series_newton(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
833
834 FLINT_DLL void _fmpz_poly_inv_series(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
835
836 FLINT_DLL void fmpz_poly_inv_series(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
837
838 FLINT_DLL void _fmpz_poly_div_series_basecase(fmpz * Q, const fmpz * A, slong Alen,
839 const fmpz * B, slong Blen, slong n);
840
841 FLINT_DLL void _fmpz_poly_div_series_divconquer(fmpz * Q, const fmpz * A, slong Alen,
842 const fmpz * B, slong Blen, slong n);
843
844 FLINT_DLL void _fmpz_poly_div_series(fmpz * Q, const fmpz * A, slong Alen,
845 const fmpz * B, slong Blen, slong n);
846
847 FLINT_DLL void fmpz_poly_div_series_basecase(fmpz_poly_t Q,
848 const fmpz_poly_t A, const fmpz_poly_t B, slong n);
849
850 FLINT_DLL void fmpz_poly_div_series_divconquer(fmpz_poly_t Q,
851 const fmpz_poly_t A, const fmpz_poly_t B, slong n);
852
853 FLINT_DLL void fmpz_poly_div_series(fmpz_poly_t Q, const fmpz_poly_t A,
854 const fmpz_poly_t B, slong n);
855
856 /* Divisibility testing ***************************************************/
857
858 FLINT_DLL int _fmpz_poly_divides(fmpz * q, const fmpz * a,
859 slong len1, const fmpz * b, slong len2);
860
861 FLINT_DLL int fmpz_poly_divides(fmpz_poly_t q,
862 const fmpz_poly_t a, const fmpz_poly_t b);
863
864 FLINT_DLL slong fmpz_poly_remove(fmpz_poly_t res, const fmpz_poly_t poly1,
865 const fmpz_poly_t poly2);
866
867 /* Pseudo division *********************************************************/
868
869 FLINT_DLL void _fmpz_poly_pseudo_divrem_basecase(fmpz * Q, fmpz * R,
870 ulong * d, const fmpz * A, slong A_len,
871 const fmpz * B, slong B_len, const fmpz_preinvn_t inv);
872
873 FLINT_DLL void fmpz_poly_pseudo_divrem_basecase(fmpz_poly_t Q, fmpz_poly_t R,
874 ulong * d, const fmpz_poly_t A, const fmpz_poly_t B);
875
876 FLINT_DLL void _fmpz_poly_pseudo_divrem_divconquer(fmpz * Q, fmpz * R,
877 ulong * d, const fmpz * A, slong lenA,
878 const fmpz * B, slong lenB, const fmpz_preinvn_t inv);
879
880 FLINT_DLL void fmpz_poly_pseudo_divrem_divconquer(fmpz_poly_t Q, fmpz_poly_t R,
881 ulong * d, const fmpz_poly_t A, const fmpz_poly_t B);
882
883 FLINT_DLL void _fmpz_poly_pseudo_divrem_cohen(fmpz * Q, fmpz * R, const fmpz * A,
884 slong lenA, const fmpz * B, slong lenB);
885
886 FLINT_DLL void fmpz_poly_pseudo_divrem_cohen(fmpz_poly_t Q, fmpz_poly_t R,
887 const fmpz_poly_t A, const fmpz_poly_t B);
888
889 FLINT_DLL void _fmpz_poly_pseudo_rem_cohen(fmpz * R, const fmpz * A, slong lenA,
890 const fmpz * B, slong lenB);
891
892 FLINT_DLL void fmpz_poly_pseudo_rem_cohen(fmpz_poly_t R, const fmpz_poly_t A,
893 const fmpz_poly_t B);
894
895 FMPZ_POLY_INLINE
_fmpz_poly_pseudo_divrem(fmpz * Q,fmpz * R,ulong * d,const fmpz * A,slong A_len,const fmpz * B,slong B_len,const fmpz_preinvn_t inv)896 void _fmpz_poly_pseudo_divrem(fmpz * Q, fmpz * R,
897 ulong * d, const fmpz * A, slong A_len,
898 const fmpz * B, slong B_len, const fmpz_preinvn_t inv)
899 {
900 _fmpz_poly_pseudo_divrem_divconquer(Q, R, d, A, A_len, B, B_len, inv);
901 }
902
903 FMPZ_POLY_INLINE
fmpz_poly_pseudo_divrem(fmpz_poly_t Q,fmpz_poly_t R,ulong * d,const fmpz_poly_t A,const fmpz_poly_t B)904 void fmpz_poly_pseudo_divrem(fmpz_poly_t Q, fmpz_poly_t R,
905 ulong * d, const fmpz_poly_t A, const fmpz_poly_t B)
906 {
907 fmpz_poly_pseudo_divrem_divconquer(Q, R, d, A, B);
908 }
909
910 FLINT_DLL void _fmpz_poly_pseudo_div(fmpz * Q, ulong * d, const fmpz * A,
911 slong lenA, const fmpz * B, slong lenB, const fmpz_preinvn_t inv);
912
913 FLINT_DLL void fmpz_poly_pseudo_div(fmpz_poly_t Q, ulong * d,
914 const fmpz_poly_t A, const fmpz_poly_t B);
915
916 FLINT_DLL void _fmpz_poly_pseudo_rem(fmpz * R, ulong * d, const fmpz * A,
917 slong lenA, const fmpz * B, slong lenB, const fmpz_preinvn_t inv);
918
919 FLINT_DLL void fmpz_poly_pseudo_rem(fmpz_poly_t R, ulong * d,
920 const fmpz_poly_t A, const fmpz_poly_t B);
921
922 FLINT_DLL void fmpz_poly_divlow_smodp(fmpz * res,
923 const fmpz_poly_t f, const fmpz_poly_t g, const fmpz_t p, slong n);
924
925 FLINT_DLL void fmpz_poly_divhigh_smodp(fmpz * res,
926 const fmpz_poly_t f, const fmpz_poly_t g, const fmpz_t p, slong n);
927
928 /* Derivative **************************************************************/
929
930 FLINT_DLL void _fmpz_poly_derivative(fmpz * rpoly, const fmpz * poly, slong len);
931
932 FLINT_DLL void fmpz_poly_derivative(fmpz_poly_t res, const fmpz_poly_t poly);
933
934 /* Evaluation **************************************************************/
935
936 void
937 FLINT_DLL _fmpz_poly_evaluate_divconquer_fmpz(fmpz_t res, const fmpz * poly, slong len,
938 const fmpz_t a);
939
940 FLINT_DLL void fmpz_poly_evaluate_divconquer_fmpz(fmpz_t res, const fmpz_poly_t poly,
941 const fmpz_t a);
942
943 FLINT_DLL void _fmpz_poly_evaluate_horner_fmpz(fmpz_t res, const fmpz * f, slong len,
944 const fmpz_t a);
945
946 FLINT_DLL void fmpz_poly_evaluate_horner_fmpz(fmpz_t res, const fmpz_poly_t f,
947 const fmpz_t a);
948
949 FLINT_DLL void _fmpz_poly_evaluate_fmpz(fmpz_t res, const fmpz * f, slong len, const fmpz_t a);
950
951 FLINT_DLL void fmpz_poly_evaluate_fmpz(fmpz_t res, const fmpz_poly_t f, const fmpz_t a);
952
953 FLINT_DLL void _fmpz_poly_evaluate_horner_fmpq(fmpz_t rnum, fmpz_t rden,
954 const fmpz * f, slong len,
955 const fmpz_t anum, const fmpz_t aden);
956
957 FLINT_DLL void fmpz_poly_evaluate_horner_fmpq(fmpq_t res, const fmpz_poly_t f,
958 const fmpq_t a);
959
960 FLINT_DLL void _fmpz_poly_evaluate_divconquer_fmpq(fmpz_t rnum, fmpz_t rden,
961 const fmpz * f, slong len,
962 const fmpz_t anum, const fmpz_t aden);
963
964 FLINT_DLL void fmpz_poly_evaluate_divconquer_fmpq(fmpq_t res,
965 const fmpz_poly_t f, const fmpq_t a);
966
967 FLINT_DLL void _fmpz_poly_evaluate_fmpq(fmpz_t rnum, fmpz_t rden,
968 const fmpz * f, slong len,
969 const fmpz_t anum, const fmpz_t aden);
970
971 FLINT_DLL void fmpz_poly_evaluate_fmpq(fmpq_t res,
972 const fmpz_poly_t f, const fmpq_t a);
973
974
975 FLINT_DLL void fmpz_poly_evaluate_mpq(mpq_t res,
976 const fmpz_poly_t f, const mpq_t a);
977
978 FLINT_DLL mp_limb_t _fmpz_poly_evaluate_mod(const fmpz * poly, slong len,
979 mp_limb_t a, mp_limb_t n, mp_limb_t ninv);
980
981 FLINT_DLL mp_limb_t fmpz_poly_evaluate_mod(const fmpz_poly_t poly, mp_limb_t a,
982 mp_limb_t n);
983
984 FLINT_DLL double _fmpz_poly_evaluate_horner_d(const fmpz * poly, slong n,
985 double d);
986
987 FLINT_DLL double fmpz_poly_evaluate_horner_d(const fmpz_poly_t poly, double d);
988
989 FLINT_DLL double _fmpz_poly_evaluate_horner_d_2exp(slong * exp,
990 const fmpz * poly, slong n, double d);
991
992 FLINT_DLL double fmpz_poly_evaluate_horner_d_2exp(slong * exp,
993 const fmpz_poly_t poly, double d);
994
995 FLINT_DLL double _fmpz_poly_evaluate_horner_d_2exp2(slong * exp, const fmpz * poly,
996 slong n, double d, slong dexp, ulong prec_in);
997
998 FLINT_DLL double fmpz_poly_evaluate_horner_d_2exp2(slong * exp,
999 const fmpz_poly_t poly, double d, slong dexp, ulong prec);
1000
1001 /* Composition *************************************************************/
1002
1003 FLINT_DLL void _fmpz_poly_compose_horner(fmpz * res, const fmpz * poly1, slong len1,
1004 const fmpz * poly2, slong len2);
1005
1006 FLINT_DLL void fmpz_poly_compose_horner(fmpz_poly_t res, const fmpz_poly_t poly1,
1007 const fmpz_poly_t poly2);
1008
1009 FLINT_DLL void _fmpz_poly_compose_divconquer(fmpz * res, const fmpz * poly1, slong len1,
1010 const fmpz * poly2, slong len2);
1011
1012 FLINT_DLL void fmpz_poly_compose_divconquer(fmpz_poly_t res, const fmpz_poly_t poly1,
1013 const fmpz_poly_t poly2);
1014
1015 FLINT_DLL void _fmpz_poly_compose(fmpz * res, const fmpz * poly1, slong len1,
1016 const fmpz * poly2, slong len2);
1017
1018 FLINT_DLL void fmpz_poly_compose(fmpz_poly_t res, const fmpz_poly_t poly1,
1019 const fmpz_poly_t poly2);
1020
1021 /* Taylor shift ************************************************************/
1022
1023 FLINT_DLL void _fmpz_poly_taylor_shift_horner(fmpz * poly, const fmpz_t c, slong n);
1024
1025 FLINT_DLL void fmpz_poly_taylor_shift_horner(fmpz_poly_t g, const fmpz_poly_t f,
1026 const fmpz_t c);
1027
1028 FLINT_DLL void _fmpz_poly_taylor_shift_divconquer(fmpz * poly, const fmpz_t c, slong n);
1029
1030 FLINT_DLL void fmpz_poly_taylor_shift_divconquer(fmpz_poly_t g, const fmpz_poly_t f,
1031 const fmpz_t c);
1032
1033 FLINT_DLL void _fmpz_poly_taylor_shift_multi_mod(fmpz * poly, const fmpz_t c, slong n);
1034
1035 FMPZ_POLY_INLINE
fmpz_poly_taylor_shift_multi_mod(fmpz_poly_t g,const fmpz_poly_t f,const fmpz_t c)1036 void fmpz_poly_taylor_shift_multi_mod(fmpz_poly_t g, const fmpz_poly_t f, const fmpz_t c)
1037 {
1038 if (f != g)
1039 fmpz_poly_set(g, f);
1040 _fmpz_poly_taylor_shift_multi_mod(g->coeffs, c, g->length);
1041 }
1042
1043 FLINT_DLL void _fmpz_poly_taylor_shift(fmpz * poly, const fmpz_t c, slong n);
1044
1045 FLINT_DLL void fmpz_poly_taylor_shift(fmpz_poly_t g, const fmpz_poly_t f, const fmpz_t c);
1046
1047 /* Power series composition and compositional inverse **********************/
1048
1049 FLINT_DLL void _fmpz_poly_compose_series_brent_kung(fmpz * res, const fmpz * poly1, slong len1,
1050 const fmpz * poly2, slong len2, slong n);
1051
1052 FLINT_DLL void fmpz_poly_compose_series_brent_kung(fmpz_poly_t res,
1053 const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
1054
1055 FLINT_DLL void _fmpz_poly_compose_series_horner(fmpz * res, const fmpz * poly1, slong len1,
1056 const fmpz * poly2, slong len2, slong n);
1057
1058 FLINT_DLL void fmpz_poly_compose_series_horner(fmpz_poly_t res,
1059 const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
1060
1061 FLINT_DLL void _fmpz_poly_compose_series(fmpz * res, const fmpz * poly1, slong len1,
1062 const fmpz * poly2, slong len2, slong n);
1063
1064 FLINT_DLL void fmpz_poly_compose_series(fmpz_poly_t res,
1065 const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
1066
1067 FLINT_DLL void _fmpz_poly_revert_series_lagrange(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
1068
1069 FLINT_DLL void fmpz_poly_revert_series_lagrange(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
1070
1071 FLINT_DLL void _fmpz_poly_revert_series_lagrange_fast(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
1072
1073 FLINT_DLL void fmpz_poly_revert_series_lagrange_fast(fmpz_poly_t Qinv,
1074 const fmpz_poly_t Q, slong n);
1075
1076 FLINT_DLL void _fmpz_poly_revert_series_newton(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
1077
1078 FLINT_DLL void fmpz_poly_revert_series_newton(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
1079
1080 FLINT_DLL void _fmpz_poly_revert_series(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
1081
1082 FLINT_DLL void fmpz_poly_revert_series(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
1083
1084 /* Square root *************************************************************/
1085
1086 FLINT_DLL int _fmpz_poly_sqrtrem_classical(fmpz * res, fmpz * r,
1087 const fmpz * poly, slong len);
1088
1089 FLINT_DLL int fmpz_poly_sqrtrem_classical(fmpz_poly_t b,
1090 fmpz_poly_t r, const fmpz_poly_t a);
1091
1092 FLINT_DLL int _fmpz_poly_sqrtrem_divconquer(fmpz * res, fmpz * r,
1093 const fmpz * poly, slong len, fmpz * temp);
1094
1095 FLINT_DLL int fmpz_poly_sqrtrem_divconquer(fmpz_poly_t b,
1096 fmpz_poly_t r, const fmpz_poly_t a);
1097
1098 FLINT_DLL int _fmpz_poly_sqrt_classical(fmpz * res, const fmpz * poly,
1099 slong len, int exact);
1100
1101 FLINT_DLL int fmpz_poly_sqrt_classical(fmpz_poly_t b, const fmpz_poly_t a);
1102
1103 FLINT_DLL int _fmpz_poly_sqrt_divconquer(fmpz * res, const fmpz * poly,
1104 slong len, int exact);
1105
1106 FLINT_DLL int fmpz_poly_sqrt_divconquer(fmpz_poly_t b, const fmpz_poly_t a);
1107
1108 FLINT_DLL int _fmpz_poly_sqrt_KS(fmpz *rop, const fmpz *op, slong len);
1109
1110 FLINT_DLL int fmpz_poly_sqrt_KS(fmpz_poly_t b, const fmpz_poly_t a);
1111
1112 FLINT_DLL int _fmpz_poly_sqrt(fmpz * res, const fmpz * poly, slong len);
1113
1114 FLINT_DLL int fmpz_poly_sqrt(fmpz_poly_t b, const fmpz_poly_t a);
1115
1116 FLINT_DLL int _fmpz_poly_sqrt_series(fmpz * res,
1117 const fmpz * poly, slong len, slong n);
1118
1119 FLINT_DLL int fmpz_poly_sqrt_series(fmpz_poly_t b,
1120 const fmpz_poly_t a, slong n);
1121
1122 /* Power sums ****************************************************************/
1123
1124 FLINT_DLL void _fmpz_poly_power_sums_naive(fmpz * res, const fmpz * poly, slong len, slong n);
1125
1126 FLINT_DLL void fmpz_poly_power_sums_naive(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
1127
1128 FLINT_DLL void fmpz_poly_power_sums(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
1129
1130 FLINT_DLL void _fmpz_poly_power_sums_to_poly(fmpz * res, const fmpz * poly, slong len);
1131
1132 FLINT_DLL void fmpz_poly_power_sums_to_poly(fmpz_poly_t res, const fmpz_poly_t Q);
1133
1134 /* Signature ***************************************************************/
1135
1136 FLINT_DLL void _fmpz_poly_signature(slong * r1, slong * r2, const fmpz * poly, slong len);
1137
1138 FLINT_DLL void fmpz_poly_signature(slong * r1, slong * r2, const fmpz_poly_t poly);
1139
1140 /* Input and output ********************************************************/
1141 FLINT_DLL int _fmpz_poly_fprint(FILE * file, const fmpz * poly, slong len);
1142
1143 FLINT_DLL int fmpz_poly_fprint(FILE * file, const fmpz_poly_t poly);
1144
1145 FLINT_DLL int _fmpz_poly_fprint_pretty(FILE * file,
1146 const fmpz * poly, slong len, const char * x);
1147
1148 FLINT_DLL int fmpz_poly_fprint_pretty(FILE * file,
1149 const fmpz_poly_t poly, const char * x);
1150
1151 FMPZ_POLY_INLINE
_fmpz_poly_print_pretty(const fmpz * poly,slong len,const char * x)1152 int _fmpz_poly_print_pretty(const fmpz * poly, slong len, const char * x)
1153 {
1154 return _fmpz_poly_fprint_pretty(stdout, poly, len, x);
1155 }
1156
1157 FMPZ_POLY_INLINE
_fmpz_poly_print(const fmpz * poly,slong n)1158 int _fmpz_poly_print(const fmpz * poly, slong n)
1159 {
1160 return _fmpz_poly_fprint(stdout, poly, n);
1161 }
1162
1163 FMPZ_POLY_INLINE
fmpz_poly_print(const fmpz_poly_t poly)1164 int fmpz_poly_print(const fmpz_poly_t poly)
1165 {
1166 return fmpz_poly_fprint(stdout, poly);
1167 }
1168
1169 FMPZ_POLY_INLINE
fmpz_poly_print_pretty(const fmpz_poly_t poly,const char * x)1170 int fmpz_poly_print_pretty(const fmpz_poly_t poly, const char * x)
1171 {
1172 return fmpz_poly_fprint_pretty(stdout, poly, x);
1173 }
1174
1175 FLINT_DLL int fmpz_poly_fread(FILE * file, fmpz_poly_t poly);
1176
1177 FLINT_DLL int fmpz_poly_fread_pretty(FILE *file, fmpz_poly_t poly, char **x);
1178
1179 FMPZ_POLY_INLINE
fmpz_poly_read(fmpz_poly_t poly)1180 int fmpz_poly_read(fmpz_poly_t poly)
1181 {
1182 return fmpz_poly_fread(stdin, poly);
1183 }
1184
1185 FMPZ_POLY_INLINE
fmpz_poly_read_pretty(fmpz_poly_t poly,char ** x)1186 int fmpz_poly_read_pretty(fmpz_poly_t poly, char **x)
1187 {
1188 return fmpz_poly_fread_pretty(stdin, poly, x);
1189 }
1190
1191 FMPZ_POLY_INLINE
fmpz_poly_debug(const fmpz_poly_t poly)1192 void fmpz_poly_debug(const fmpz_poly_t poly)
1193 {
1194 flint_printf("(alloc = %wd, length = %wd, vec = ", poly->alloc, poly->length);
1195 if (poly->coeffs)
1196 {
1197 flint_printf("{");
1198 _fmpz_vec_print(poly->coeffs, poly->alloc);
1199 flint_printf("}");
1200 }
1201 else
1202 {
1203 flint_printf("NULL");
1204 }
1205 flint_printf(")");
1206 fflush(stdout);
1207 }
1208
1209 /* CRT ********************************************************************/
1210
1211 FLINT_DLL void fmpz_poly_get_nmod_poly(nmod_poly_t res, const fmpz_poly_t poly);
1212
1213 FLINT_DLL void fmpz_poly_set_nmod_poly(fmpz_poly_t res, const nmod_poly_t poly);
1214
1215 FLINT_DLL void fmpz_poly_set_nmod_poly_unsigned(fmpz_poly_t res, const nmod_poly_t poly);
1216
1217 void
1218 FLINT_DLL _fmpz_poly_CRT_ui_precomp(fmpz * res, const fmpz * poly1, slong len1,
1219 const fmpz_t m1, mp_srcptr poly2, slong len2, mp_limb_t m2,
1220 mp_limb_t m2inv, fmpz_t m1m2, mp_limb_t c, int sign);
1221
1222 FLINT_DLL void _fmpz_poly_CRT_ui(fmpz * res, const fmpz * poly1, slong len1,
1223 const fmpz_t m1, mp_srcptr poly2, slong len2, mp_limb_t m2,
1224 mp_limb_t m2inv, int sign);
1225
1226 FLINT_DLL void fmpz_poly_CRT_ui(fmpz_poly_t res, const fmpz_poly_t poly1,
1227 const fmpz_t m1, const nmod_poly_t poly2,
1228 int sign);
1229
1230
1231 /* Products *****************************************************************/
1232
1233 FLINT_DLL void _fmpz_poly_product_roots_fmpz_vec(fmpz * poly,
1234 const fmpz * xs, slong n);
1235
1236 FLINT_DLL void fmpz_poly_product_roots_fmpz_vec(fmpz_poly_t poly,
1237 const fmpz * xs, slong n);
1238
1239 FLINT_DLL void _fmpz_poly_product_roots_fmpq_vec(fmpz * poly,
1240 const fmpq * xs, slong n);
1241
1242 FLINT_DLL void fmpz_poly_product_roots_fmpq_vec(fmpz_poly_t poly,
1243 const fmpq * xs, slong n);
1244
1245
1246 /* Newton basis *************************************************************/
1247
1248 FLINT_DLL void _fmpz_poly_monomial_to_newton(fmpz * poly, const fmpz * roots, slong n);
1249
1250 FLINT_DLL void _fmpz_poly_newton_to_monomial(fmpz * poly, const fmpz * roots, slong n);
1251
1252
1253 /* Multipoint evaluation and interpolation *********************************/
1254
1255 FLINT_DLL void fmpz_poly_evaluate_fmpz_vec(fmpz * res, const fmpz_poly_t f,
1256 const fmpz * a, slong n);
1257
1258 FLINT_DLL void fmpz_poly_interpolate_fmpz_vec(fmpz_poly_t poly,
1259 const fmpz * xs, const fmpz * ys, slong n);
1260
1261 /* Hensel lifting ************************************************************/
1262
1263 FLINT_DLL void fmpz_poly_hensel_build_tree(slong * link, fmpz_poly_t *v, fmpz_poly_t *w,
1264 const nmod_poly_factor_t fac);
1265
1266 FLINT_DLL void fmpz_poly_hensel_lift(fmpz_poly_t Gout, fmpz_poly_t Hout,
1267 fmpz_poly_t Aout, fmpz_poly_t Bout,
1268 const fmpz_poly_t f,
1269 const fmpz_poly_t g, const fmpz_poly_t h,
1270 const fmpz_poly_t a, const fmpz_poly_t b,
1271 const fmpz_t p, const fmpz_t p1);
1272
1273 FLINT_DLL void _fmpz_poly_hensel_lift_without_inverse(fmpz *G, fmpz *H,
1274 const fmpz *f, slong lenF,
1275 const fmpz *g, slong lenG, const fmpz *h, slong lenH,
1276 const fmpz *a, slong lenA, const fmpz *b, slong lenB,
1277 const fmpz_t p, const fmpz_t p1);
1278
1279 FLINT_DLL void fmpz_poly_hensel_lift_without_inverse(fmpz_poly_t Gout, fmpz_poly_t Hout,
1280 const fmpz_poly_t f, const fmpz_poly_t g, const fmpz_poly_t h,
1281 const fmpz_poly_t a, const fmpz_poly_t b,
1282 const fmpz_t p, const fmpz_t p1);
1283
1284 FLINT_DLL void _fmpz_poly_hensel_lift_only_inverse(fmpz *A, fmpz *B,
1285 const fmpz *G, slong lenG, const fmpz *H, slong lenH,
1286 const fmpz *a, slong lenA, const fmpz *b, slong lenB,
1287 const fmpz_t p, const fmpz_t p1);
1288
1289 FLINT_DLL void fmpz_poly_hensel_lift_only_inverse(fmpz_poly_t Aout, fmpz_poly_t Bout,
1290 const fmpz_poly_t G, const fmpz_poly_t H,
1291 const fmpz_poly_t a, const fmpz_poly_t b,
1292 const fmpz_t p, const fmpz_t p1);
1293
1294 FLINT_DLL void fmpz_poly_hensel_lift_tree_recursive(slong *link,
1295 fmpz_poly_t *v, fmpz_poly_t *w, fmpz_poly_t f, slong j, slong inv,
1296 const fmpz_t p0, const fmpz_t p1);
1297
1298 FLINT_DLL void fmpz_poly_hensel_lift_tree(slong *link, fmpz_poly_t *v, fmpz_poly_t *w,
1299 fmpz_poly_t f, slong r, const fmpz_t p, slong e0, slong e1, slong inv);
1300
1301 FLINT_DLL slong _fmpz_poly_hensel_start_lift(fmpz_poly_factor_t lifted_fac, slong *link,
1302 fmpz_poly_t *v, fmpz_poly_t *w, const fmpz_poly_t f,
1303 const nmod_poly_factor_t local_fac, slong target_exp);
1304
1305 FLINT_DLL slong _fmpz_poly_hensel_continue_lift(fmpz_poly_factor_t lifted_fac,
1306 slong *link, fmpz_poly_t *v, fmpz_poly_t *w, const fmpz_poly_t f,
1307 slong prev, slong curr, slong N, const fmpz_t p);
1308
1309 FLINT_DLL void fmpz_poly_hensel_lift_once(fmpz_poly_factor_t lifted_fac,
1310 const fmpz_poly_t f,
1311 const nmod_poly_factor_t local_fac, slong N);
1312
1313 /* Some functions for backwards compatibility */
1314
1315 FMPZ_POLY_INLINE
fmpz_poly_scalar_mul_mpz(fmpz_poly_t poly1,const fmpz_poly_t poly2,const mpz_t x)1316 void fmpz_poly_scalar_mul_mpz(fmpz_poly_t poly1,
1317 const fmpz_poly_t poly2, const mpz_t x)
1318 {
1319 fmpz_t t;
1320 fmpz_init_set_readonly(t, x);
1321 fmpz_poly_scalar_mul_fmpz(poly1, poly2, t);
1322 fmpz_clear_readonly(t);
1323 }
1324
1325 FMPZ_POLY_INLINE
fmpz_poly_scalar_divexact_mpz(fmpz_poly_t poly1,const fmpz_poly_t poly2,const mpz_t x)1326 void fmpz_poly_scalar_divexact_mpz(fmpz_poly_t poly1,
1327 const fmpz_poly_t poly2, const mpz_t x)
1328 {
1329 fmpz_t t;
1330 fmpz_init_set_readonly(t, x);
1331 fmpz_poly_scalar_divexact_fmpz(poly1, poly2, t);
1332 fmpz_clear_readonly(t);
1333 }
1334
1335 FMPZ_POLY_INLINE
fmpz_poly_scalar_fdiv_mpz(fmpz_poly_t poly1,const fmpz_poly_t poly2,const mpz_t x)1336 void fmpz_poly_scalar_fdiv_mpz(fmpz_poly_t poly1,
1337 const fmpz_poly_t poly2, const mpz_t x)
1338 {
1339 fmpz_t t;
1340 fmpz_init_set_readonly(t, x);
1341 fmpz_poly_scalar_fdiv_fmpz(poly1, poly2, t);
1342 fmpz_clear_readonly(t);
1343 }
1344
1345 FMPZ_POLY_INLINE
fmpz_poly_set_coeff_mpz(fmpz_poly_t poly,slong n,const mpz_t x)1346 void fmpz_poly_set_coeff_mpz(fmpz_poly_t poly, slong n,
1347 const mpz_t x)
1348 {
1349 fmpz_t t;
1350 fmpz_init_set_readonly(t, x);
1351 fmpz_poly_set_coeff_fmpz(poly, n, t);
1352 fmpz_clear_readonly(t);
1353 }
1354
1355 FMPZ_POLY_INLINE
fmpz_poly_get_coeff_mpz(mpz_t x,const fmpz_poly_t poly,slong n)1356 void fmpz_poly_get_coeff_mpz(mpz_t x, const fmpz_poly_t poly, slong n)
1357 {
1358 fmpz_t t;
1359 fmpz_init(t);
1360 fmpz_poly_get_coeff_fmpz(t, poly, n);
1361 fmpz_get_mpz(x, t);
1362 fmpz_clear(t);
1363 }
1364
1365 /* Roots */
1366
1367 FLINT_DLL void _fmpz_poly_bound_roots(fmpz_t bound, const fmpz * poly, slong len);
1368
1369 FLINT_DLL void fmpz_poly_bound_roots(fmpz_t bound, const fmpz_poly_t poly);
1370
1371 FLINT_DLL void _fmpz_poly_num_real_roots_sturm(slong * n_neg, slong * n_pos, const fmpz * pol, slong len);
1372
1373 FLINT_DLL slong fmpz_poly_num_real_roots_sturm(const fmpz_poly_t poly);
1374
1375 FLINT_DLL slong _fmpz_poly_num_real_roots(const fmpz * pol, slong len);
1376
1377 FLINT_DLL slong fmpz_poly_num_real_roots(const fmpz_poly_t poly);
1378
1379 /* CLD bounds */
1380
1381 FLINT_DLL void fmpz_poly_CLD_bound(fmpz_t res, const fmpz_poly_t f, slong n);
1382
1383 /* Special polynomials */
1384
1385 FLINT_DLL void _fmpz_poly_cyclotomic(fmpz * a, ulong n, mp_ptr factors,
1386 slong num_factors, ulong phi);
1387 FLINT_DLL void fmpz_poly_cyclotomic(fmpz_poly_t poly, ulong n);
1388
1389 FLINT_DLL ulong _fmpz_poly_is_cyclotomic(const fmpz * poly, slong len);
1390
1391 FLINT_DLL ulong fmpz_poly_is_cyclotomic(const fmpz_poly_t poly);
1392
1393 FLINT_DLL void _fmpz_poly_cos_minpoly(fmpz * f, ulong n);
1394
1395 FLINT_DLL void fmpz_poly_cos_minpoly(fmpz_poly_t f, ulong n);
1396
1397 FLINT_DLL void _fmpz_poly_swinnerton_dyer(fmpz * T, ulong n);
1398
1399 FLINT_DLL void fmpz_poly_swinnerton_dyer(fmpz_poly_t poly, ulong n);
1400
1401 FLINT_DLL void _fmpz_poly_chebyshev_t(fmpz * coeffs, ulong n);
1402
1403 FLINT_DLL void fmpz_poly_chebyshev_t(fmpz_poly_t poly, ulong n);
1404
1405 FLINT_DLL void _fmpz_poly_chebyshev_u(fmpz * coeffs, ulong n);
1406
1407 FLINT_DLL void fmpz_poly_chebyshev_u(fmpz_poly_t poly, ulong n);
1408
1409 FLINT_DLL void _fmpz_poly_legendre_pt(fmpz * coeffs, ulong n);
1410
1411 FLINT_DLL void fmpz_poly_legendre_pt(fmpz_poly_t poly, ulong n);
1412
1413 FLINT_DLL void _fmpz_poly_hermite_h(fmpz * coeffs, ulong n);
1414
1415 FLINT_DLL void fmpz_poly_hermite_h(fmpz_poly_t poly, ulong n);
1416
1417 FLINT_DLL void _fmpz_poly_hermite_he(fmpz * coeffs, ulong n);
1418
1419 FLINT_DLL void fmpz_poly_hermite_he(fmpz_poly_t poly, ulong n);
1420
1421 FLINT_DLL void _fmpz_poly_fibonacci(fmpz * coeffs, ulong n);
1422
1423 FLINT_DLL void fmpz_poly_fibonacci(fmpz_poly_t poly, ulong n);
1424
1425 FLINT_DLL void _fmpz_poly_eta_qexp(fmpz * f, slong e, slong n);
1426
1427 FLINT_DLL void fmpz_poly_eta_qexp(fmpz_poly_t f, slong e, slong n);
1428
1429 FLINT_DLL void _fmpz_poly_theta_qexp(fmpz * f, slong e, slong n);
1430
1431 FLINT_DLL void fmpz_poly_theta_qexp(fmpz_poly_t f, slong e, slong n);
1432
1433 /* Inlines *******************************************************************/
1434
1435 FLINT_DLL void fmpz_poly_add_si(fmpz_poly_t res, const fmpz_poly_t poly, slong c);
1436 FLINT_DLL void fmpz_poly_sub_si(fmpz_poly_t res, const fmpz_poly_t poly, slong c);
1437 FLINT_DLL void fmpz_poly_si_sub(fmpz_poly_t res, slong c, const fmpz_poly_t poly);
1438 FLINT_DLL void fmpz_poly_add_fmpz(fmpz_poly_t res, const fmpz_poly_t poly, fmpz_t c);
1439 FLINT_DLL void fmpz_poly_sub_fmpz(fmpz_poly_t res, const fmpz_poly_t poly, fmpz_t c);
1440 FLINT_DLL void fmpz_poly_fmpz_sub(fmpz_poly_t res, fmpz_t c, const fmpz_poly_t poly);
1441
1442 #ifdef __cplusplus
1443 }
1444 #endif
1445
1446 #include "fmpz_poly_factor.h"
1447
1448 #endif
1449
1450