1 /*
2 Copyright (C) 2012 Andres Goens
3 Copyright (C) 2012 Sebastian Pancratz
4 Copyright (C) 2013 Mike Hansen
5
6 This file is part of FLINT.
7
8 FLINT is free software: you can redistribute it and/or modify it under
9 the terms of the GNU Lesser General Public License (LGPL) as published
10 by the Free Software Foundation; either version 2.1 of the License, or
11 (at your option) any later version. See <http://www.gnu.org/licenses/>.
12 */
13
14 #ifdef T
15
16 #ifdef __cplusplus
17 extern "C" {
18 #endif
19
20 /* Type definitions *********************************************************/
21
22 typedef struct
23 {
24 TEMPLATE(T, struct) *coeffs;
25 slong alloc;
26 slong length;
27 }
28 TEMPLATE(T, poly_struct);
29
30 typedef TEMPLATE(T, poly_struct) TEMPLATE(T, poly_t)[1];
31
32 /* Memory management ********************************************************/
33
34 FLINT_DLL void TEMPLATE(T, poly_init)(TEMPLATE(T, poly_t) poly, const TEMPLATE(T, ctx_t) ctx);
35
36 FLINT_DLL void TEMPLATE(T, poly_init2)(TEMPLATE(T, poly_t) poly, slong alloc,
37 const TEMPLATE(T, ctx_t) ctx);
38
39 FLINT_DLL void TEMPLATE(T, poly_realloc)(TEMPLATE(T, poly_t) poly, slong alloc,
40 const TEMPLATE(T, ctx_t) ctx);
41
42 FLINT_DLL void TEMPLATE(T, poly_truncate)(TEMPLATE(T, poly_t) poly, slong len,
43 const TEMPLATE(T, ctx_t) ctx);
44
45 FLINT_DLL void TEMPLATE(T, poly_set_trunc)(TEMPLATE(T, poly_t) poly1, TEMPLATE(T, poly_t) poly2, slong len,
46 const TEMPLATE(T, ctx_t) ctx);
47
48 FLINT_DLL void TEMPLATE(T, poly_fit_length)(TEMPLATE(T, poly_t) poly, slong len,
49 const TEMPLATE(T, ctx_t) ctx);
50
51 FLINT_DLL void TEMPLATE(T, poly_clear)(TEMPLATE(T, poly_t) poly,
52 const TEMPLATE(T, ctx_t) ctx);
53
54 FLINT_DLL void _TEMPLATE(T, poly_normalise)(TEMPLATE(T, poly_t) poly,
55 const TEMPLATE(T, ctx_t) ctx);
56
57 FLINT_DLL void _TEMPLATE(T, poly_normalise2)(const TEMPLATE(T, struct) *poly, slong *length,
58 const TEMPLATE(T, ctx_t) ctx);
59
60 FQ_POLY_TEMPLATES_INLINE void
_TEMPLATE(T,poly_set_length)61 _TEMPLATE(T, poly_set_length)(TEMPLATE(T, poly_t) poly, slong len,
62 const TEMPLATE(T, ctx_t) ctx)
63 {
64 if (poly->length > len)
65 {
66 slong i;
67
68 for (i = len; i < poly->length; i++)
69 TEMPLATE(T, zero)(poly->coeffs + i, ctx);
70 }
71 poly->length = len;
72 }
73
74 /* Polynomial parameters ***************************************************/
75
76 FQ_POLY_TEMPLATES_INLINE slong
TEMPLATE(T,poly_length)77 TEMPLATE(T, poly_length)(const TEMPLATE(T, poly_t) poly,
78 const TEMPLATE(T, ctx_t) ctx)
79 {
80 return poly->length;
81 }
82
83 FQ_POLY_TEMPLATES_INLINE slong
TEMPLATE(T,poly_degree)84 TEMPLATE(T, poly_degree)(const TEMPLATE(T, poly_t) poly,
85 const TEMPLATE(T, ctx_t) ctx)
86 {
87 return poly->length - 1;
88 }
89
TEMPLATE(T,struct)90 FQ_POLY_TEMPLATES_INLINE TEMPLATE(T, struct) *
91 TEMPLATE(T, poly_lead)(const TEMPLATE(T, poly_t) poly,
92 const TEMPLATE(T, ctx_t) ctx)
93 {
94 return poly->length > 0 ? poly->coeffs + (poly->length - 1) : NULL;
95 }
96
97 /* Randomisation ***********************************************************/
98
99 FLINT_DLL void TEMPLATE(T, poly_randtest)(TEMPLATE(T, poly_t) f, flint_rand_t state,
100 slong len, const TEMPLATE(T, ctx_t) ctx);
101
102 FLINT_DLL void TEMPLATE(T, poly_randtest_not_zero)(TEMPLATE(T, poly_t) f, flint_rand_t state,
103 slong len, const TEMPLATE(T, ctx_t) ctx);
104
105 FLINT_DLL void TEMPLATE(T, poly_randtest_monic) (TEMPLATE(T, poly_t) f, flint_rand_t state,
106 slong len, const TEMPLATE(T, ctx_t) ctx);
107
108 FLINT_DLL void TEMPLATE(T, poly_randtest_irreducible) (TEMPLATE(T, poly_t) f,
109 flint_rand_t state, slong len,
110 const TEMPLATE(T, ctx_t) ctx);
111
112
113 /* Assignment and basic manipulation ***************************************/
114
115 FLINT_DLL void _TEMPLATE(T, poly_set)(TEMPLATE(T, struct) *rop, const TEMPLATE(T, struct) *op,
116 slong len, const TEMPLATE(T, ctx_t) ctx);
117
118 FLINT_DLL void TEMPLATE(T, poly_set)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op,
119 const TEMPLATE(T, ctx_t) ctx);
120
121 FLINT_DLL void TEMPLATE3(T, poly_set, T)(TEMPLATE(T, poly_t) poly, const TEMPLATE(T, t) c,
122 const TEMPLATE(T, ctx_t) ctx);
123
124 FLINT_DLL void TEMPLATE(T, poly_set_fmpz_mod_poly)(TEMPLATE(T, poly_t) rop,
125 const fmpz_mod_poly_t op,
126 const TEMPLATE(T, ctx_t) ctx);
127
128 FLINT_DLL void TEMPLATE(T, poly_set_nmod_poly)(TEMPLATE(T, poly_t) rop,
129 const nmod_poly_t op,
130 const TEMPLATE(T, ctx_t) ctx);
131
132 FLINT_DLL void TEMPLATE(T, poly_swap)(TEMPLATE(T, poly_t) op1, TEMPLATE(T, poly_t) op2,
133 const TEMPLATE(T, ctx_t) ctx);
134
135 FQ_POLY_TEMPLATES_INLINE void
_TEMPLATE(T,poly_zero)136 _TEMPLATE(T, poly_zero)(TEMPLATE(T, struct) *rop, slong len,
137 const TEMPLATE(T, ctx_t) ctx)
138 {
139 slong i;
140
141 for (i = 0; i < len; i++)
142 TEMPLATE(T, zero)(rop + i, ctx);
143 }
144
145 FQ_POLY_TEMPLATES_INLINE void
TEMPLATE(T,poly_zero)146 TEMPLATE(T, poly_zero)(TEMPLATE(T, poly_t) poly, const TEMPLATE(T, ctx_t) ctx)
147 {
148 _TEMPLATE(T, poly_set_length)(poly, 0, ctx);
149 }
150
151 FLINT_DLL void TEMPLATE(T, poly_one)(TEMPLATE(T, poly_t) poly, const TEMPLATE(T, ctx_t) ctx);
152
153 FLINT_DLL void TEMPLATE(T, poly_gen)(TEMPLATE(T, poly_t) f, const TEMPLATE(T, ctx_t) ctx);
154
155 FLINT_DLL void _TEMPLATE(T, poly_make_monic)(TEMPLATE(T, struct) *rop,
156 const TEMPLATE(T, struct) *op, slong length,
157 const TEMPLATE(T, ctx_t) ctx);
158
159 FLINT_DLL void TEMPLATE(T, poly_make_monic)(TEMPLATE(T, poly_t) rop,
160 const TEMPLATE(T, poly_t) op,
161 const TEMPLATE(T, ctx_t) ctx);
162
163 FLINT_DLL void _TEMPLATE(T, poly_reverse)(TEMPLATE(T, struct) * res,
164 const TEMPLATE(T, struct) * poly, slong len, slong n,
165 const TEMPLATE(T, ctx_t) ctx);
166
167 FLINT_DLL void TEMPLATE(T, poly_reverse)(TEMPLATE(T, poly_t) res,
168 const TEMPLATE(T, poly_t) poly, slong n,
169 const TEMPLATE(T, ctx_t) ctx);
170
171 FLINT_DLL ulong TEMPLATE(T, poly_deflation)(const TEMPLATE(T, poly_t) input,
172 const TEMPLATE(T, ctx_t) ctx);
173
174 FLINT_DLL void TEMPLATE(T, poly_deflate)(TEMPLATE(T, poly_t) result,
175 const TEMPLATE(T, poly_t) input, ulong deflation,
176 const TEMPLATE(T, ctx_t) ctx);
177
178 FLINT_DLL void TEMPLATE(T, poly_inflate)(TEMPLATE(T, poly_t) result,
179 const TEMPLATE(T, poly_t) input, ulong inflation,
180 const TEMPLATE(T, ctx_t) ctx);
181
182 /* Getting and setting coefficients ****************************************/
183
184 FLINT_DLL void TEMPLATE(T, poly_get_coeff)(TEMPLATE(T, t) x, const TEMPLATE(T, poly_t) poly,
185 slong n, const TEMPLATE(T, ctx_t) ctx);
186
187 FLINT_DLL void TEMPLATE(T, poly_set_coeff)(TEMPLATE(T, poly_t) poly, slong n,
188 const TEMPLATE(T, t) x,
189 const TEMPLATE(T, ctx_t) ctx);
190
191 FQ_POLY_TEMPLATES_INLINE void
TEMPLATE(T,poly_set_coeff_fmpz)192 TEMPLATE(T, poly_set_coeff_fmpz)(TEMPLATE(T, poly_t) poly, slong n,
193 const fmpz_t x, const TEMPLATE(T, ctx_t) ctx)
194 {
195 TEMPLATE(T, poly_fit_length)(poly, n + 1, ctx);
196 TEMPLATE(T, set_fmpz)(poly->coeffs + n, x, ctx);
197 if (n + 1 > poly->length)
198 {
199 _TEMPLATE(T, poly_set_length)(poly, n + 1, ctx);
200 }
201 _TEMPLATE(T, poly_normalise)(poly, ctx);
202 }
203
204 FQ_POLY_TEMPLATES_INLINE int
TEMPLATE(T,poly_is_gen)205 TEMPLATE(T, poly_is_gen)(const TEMPLATE(T, poly_t) poly,
206 const TEMPLATE(T, ctx_t) ctx)
207 {
208 return ((poly->length == 2) &&
209 TEMPLATE(T, is_zero)(poly->coeffs, ctx) &&
210 TEMPLATE(T, is_one)(poly->coeffs + 1, ctx));
211 }
212
213 /* Comparison **************************************************************/
214
215 FLINT_DLL int TEMPLATE(T, poly_equal)(const TEMPLATE(T, poly_t) poly1,
216 const TEMPLATE(T, poly_t) poly2,
217 const TEMPLATE(T, ctx_t) ctx);
218
219 FLINT_DLL int TEMPLATE(T, poly_equal_trunc)(const TEMPLATE(T, poly_t) poly1,
220 const TEMPLATE(T, poly_t) poly2,
221 slong n, const TEMPLATE(T, ctx_t) ctx);
222
223 FQ_POLY_TEMPLATES_INLINE int
TEMPLATE(T,poly_is_zero)224 TEMPLATE(T, poly_is_zero)(const TEMPLATE(T, poly_t) poly,
225 const TEMPLATE(T, ctx_t) ctx)
226 {
227 return (poly->length == 0);
228 }
229
230 FQ_POLY_TEMPLATES_INLINE int
TEMPLATE(T,poly_is_one)231 TEMPLATE(T, poly_is_one)(const TEMPLATE(T, poly_t) op,
232 const TEMPLATE(T, ctx_t) ctx)
233 {
234 return (op->length == 1) && (TEMPLATE(T, is_one)(op->coeffs + 0, ctx));
235 }
236
237 FQ_POLY_TEMPLATES_INLINE int
TEMPLATE(T,poly_is_unit)238 TEMPLATE(T, poly_is_unit)(const TEMPLATE(T, poly_t) op,
239 const TEMPLATE(T, ctx_t) ctx)
240 {
241 return (op->length == 1) && (!(TEMPLATE(T, is_zero)(op->coeffs + 0, ctx)));
242 }
243
244 FQ_POLY_TEMPLATES_INLINE int
TEMPLATE3(T,poly_equal,T)245 TEMPLATE3(T, poly_equal, T)(const TEMPLATE(T, poly_t) poly,
246 const TEMPLATE(T, t) c,
247 const TEMPLATE(T, ctx_t) ctx)
248 {
249 return ((poly->length == 0) && TEMPLATE(T, is_zero)(c, ctx)) ||
250 ((poly->length == 1) && TEMPLATE(T, equal)(poly->coeffs, c, ctx));
251 }
252
253 /* Addition and subtraction ************************************************/
254
255 FLINT_DLL void _TEMPLATE(T, poly_add)(TEMPLATE(T, struct) *res,
256 const TEMPLATE(T, struct) *poly1, slong len1,
257 const TEMPLATE(T, struct) *poly2, slong len2,
258 const TEMPLATE(T, ctx_t) ctx);
259
260 FLINT_DLL void TEMPLATE(T, poly_add)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op1,
261 const TEMPLATE(T, poly_t) op2,
262 const TEMPLATE(T, ctx_t) ctx);
263
264 FLINT_DLL void TEMPLATE(T, poly_add_si)(TEMPLATE(T, poly_t) rop,
265 const TEMPLATE(T, poly_t) op1, slong c,
266 const TEMPLATE(T, ctx_t) ctx);
267
268 FLINT_DLL void TEMPLATE(T, poly_add_series)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op1,
269 const TEMPLATE(T, poly_t) op2,
270 slong n, const TEMPLATE(T, ctx_t) ctx);
271
272 FLINT_DLL void _TEMPLATE(T, poly_sub)(TEMPLATE(T, struct) *res,
273 const TEMPLATE(T, struct) *poly1, slong len1,
274 const TEMPLATE(T, struct) *poly2, slong len2,
275 const TEMPLATE(T, ctx_t) ctx);
276
277 FLINT_DLL void TEMPLATE(T, poly_sub)(TEMPLATE(T, poly_t) rop,
278 const TEMPLATE(T, poly_t) op1,
279 const TEMPLATE(T, poly_t) op2,
280 const TEMPLATE(T, ctx_t) ctx);
281
282 FLINT_DLL void TEMPLATE(T, poly_sub_series)(TEMPLATE(T, poly_t) rop,
283 const TEMPLATE(T, poly_t) op1,
284 const TEMPLATE(T, poly_t) op2,
285 slong n, const TEMPLATE(T, ctx_t) ctx);
286
287 FLINT_DLL void _TEMPLATE(T, poly_neg)(TEMPLATE(T, struct) *rop,
288 const TEMPLATE(T, struct) *op, slong len,
289 const TEMPLATE(T, ctx_t) ctx);
290
291 FLINT_DLL void TEMPLATE(T, poly_neg)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op,
292 const TEMPLATE(T, ctx_t) ctx);
293
294 /* Scalar multiplication and division **************************************/
295
296 FLINT_DLL void _TEMPLATE3(T, poly_scalar_mul, T)(TEMPLATE(T, struct) *rop,
297 const TEMPLATE(T, struct) *op, slong len,
298 const TEMPLATE(T, t) x,
299 const TEMPLATE(T, ctx_t) ctx);
300
301 FLINT_DLL void TEMPLATE3(T, poly_scalar_mul, T)(TEMPLATE(T, poly_t) rop,
302 const TEMPLATE(T, poly_t) op,
303 const TEMPLATE(T, t) x,
304 const TEMPLATE(T, ctx_t) ctx);
305
306 FLINT_DLL void _TEMPLATE3(T, poly_scalar_addmul, T)(TEMPLATE(T, struct) *rop,
307 const TEMPLATE(T, struct) *op, slong len,
308 const TEMPLATE(T, t) x,
309 const TEMPLATE(T, ctx_t) ctx);
310
311 FLINT_DLL void _TEMPLATE3(T, poly_scalar_div, T)(TEMPLATE(T, struct) *rop,
312 const TEMPLATE(T, struct) *op, slong len,
313 const TEMPLATE(T, t) x,
314 const TEMPLATE(T, ctx_t) ctx);
315
316 FLINT_DLL void TEMPLATE3(T, poly_scalar_div, T)(TEMPLATE(T, poly_t) rop,
317 const TEMPLATE(T, poly_t) op,
318 const TEMPLATE(T, t) x,
319 const TEMPLATE(T, ctx_t) ctx);
320
321 FLINT_DLL void _TEMPLATE3(T, poly_scalar_addmul, T)(TEMPLATE(T, struct) *rop,
322 const TEMPLATE(T, struct) *op, slong len,
323 const TEMPLATE(T, t) x,
324 const TEMPLATE(T, ctx_t) ctx);
325
326 FLINT_DLL void TEMPLATE3(T, poly_scalar_addmul, T)(TEMPLATE(T, poly_t) rop,
327 const TEMPLATE(T, poly_t) op,
328 const TEMPLATE(T, t) x,
329 const TEMPLATE(T, ctx_t) ctx);
330
331 FLINT_DLL void _TEMPLATE3(T, poly_scalar_submul, T)(TEMPLATE(T, struct) *rop,
332 const TEMPLATE(T, struct) *op, slong len,
333 const TEMPLATE(T, t) x,
334 const TEMPLATE(T, ctx_t) ctx);
335
336 FLINT_DLL void TEMPLATE3(T, poly_scalar_submul, T)(TEMPLATE(T, poly_t) rop,
337 const TEMPLATE(T, poly_t) op,
338 const TEMPLATE(T, t) x,
339 const TEMPLATE(T, ctx_t) ctx);
340
341 /* Multiplication **********************************************************/
342
343 FLINT_DLL void _TEMPLATE(T, poly_mul_classical)(TEMPLATE(T, struct) *rop,
344 const TEMPLATE(T, struct) *op1, slong len1,
345 const TEMPLATE(T, struct) *op2, slong len2,
346 const TEMPLATE(T, ctx_t) ctx);
347
348 FLINT_DLL void TEMPLATE(T, poly_mul_classical)(TEMPLATE(T, poly_t) rop,
349 const TEMPLATE(T, poly_t) op1,
350 const TEMPLATE(T, poly_t) op2,
351 const TEMPLATE(T, ctx_t) ctx);
352
353 FLINT_DLL void _TEMPLATE(T, poly_mul_reorder)(TEMPLATE(T, struct) *rop,
354 const TEMPLATE(T, struct) *op1, slong len1,
355 const TEMPLATE(T, struct) *op2, slong len2,
356 const TEMPLATE(T, ctx_t) ctx);
357
358 FLINT_DLL void TEMPLATE(T, poly_mul_reorder)(TEMPLATE(T, poly_t) rop,
359 const TEMPLATE(T, poly_t) op1,
360 const TEMPLATE(T, poly_t) op2,
361 const TEMPLATE(T, ctx_t) ctx);
362
363 FLINT_DLL void _TEMPLATE(T, poly_mul_univariate)(TEMPLATE(T, struct) *rop,
364 const TEMPLATE(T, struct) *op1, slong len1,
365 const TEMPLATE(T, struct) *op2, slong len2,
366 const TEMPLATE(T, ctx_t) ctx);
367
368 FLINT_DLL void TEMPLATE(T, poly_mul_univariate)(TEMPLATE(T, poly_t) rop,
369 const TEMPLATE(T, poly_t) op1,
370 const TEMPLATE(T, poly_t) op2,
371 const TEMPLATE(T, ctx_t) ctx);
372
373 FLINT_DLL void _TEMPLATE(T, poly_mul_KS)(TEMPLATE(T, struct) *rop,
374 const TEMPLATE(T, struct) *op1, slong len1,
375 const TEMPLATE(T, struct) *op2, slong len2,
376 const TEMPLATE(T, ctx_t) ctx);
377
378 FLINT_DLL void TEMPLATE(T, poly_mul_KS)(TEMPLATE(T, poly_t) rop,
379 const TEMPLATE(T, poly_t) op1,
380 const TEMPLATE(T, poly_t) op2,
381 const TEMPLATE(T, ctx_t) ctx);
382
383 FLINT_DLL void _TEMPLATE(T, poly_mul)(TEMPLATE(T, struct) *rop,
384 const TEMPLATE(T, struct) *op1, slong len1,
385 const TEMPLATE(T, struct) *op2, slong len2,
386 const TEMPLATE(T, ctx_t) ctx);
387
388 FLINT_DLL void TEMPLATE(T, poly_mul)(TEMPLATE(T, poly_t) rop,
389 const TEMPLATE(T, poly_t) op1,
390 const TEMPLATE(T, poly_t) op2,
391 const TEMPLATE(T, ctx_t) ctx);
392
393 FLINT_DLL void _TEMPLATE(T, poly_mullow_classical)(TEMPLATE(T, struct) *rop,
394 const TEMPLATE(T, struct) *op1, slong len1,
395 const TEMPLATE(T, struct) *op2, slong len2,
396 slong n,
397 const TEMPLATE(T, ctx_t) ctx);
398
399 FLINT_DLL void TEMPLATE(T, poly_mullow_classical)(TEMPLATE(T, poly_t) rop,
400 const TEMPLATE(T, poly_t) op1,
401 const TEMPLATE(T, poly_t) op2,
402 slong n, const
403 TEMPLATE(T, ctx_t) ctx);
404
405 FLINT_DLL void _TEMPLATE(T, poly_mullow_KS)(TEMPLATE(T, struct) *rop,
406 const TEMPLATE(T, struct) *op1, slong len1,
407 const TEMPLATE(T, struct) *op2, slong len2,
408 slong n,
409 const TEMPLATE(T, ctx_t) ctx);
410
411 FLINT_DLL void TEMPLATE(T, poly_mullow_KS)(TEMPLATE(T, poly_t) rop,
412 const TEMPLATE(T, poly_t) op1,
413 const TEMPLATE(T, poly_t) op2,
414 slong n,
415 const TEMPLATE(T, ctx_t) ctx);
416
417 FLINT_DLL void _TEMPLATE(T, poly_mullow_univariate)(TEMPLATE(T, struct) *rop,
418 const TEMPLATE(T, struct) *op1, slong len1,
419 const TEMPLATE(T, struct) *op2, slong len2,
420 slong n,
421 const TEMPLATE(T, ctx_t) ctx);
422
423 FLINT_DLL void TEMPLATE(T, poly_mullow_univariate)(TEMPLATE(T, poly_t) rop,
424 const TEMPLATE(T, poly_t) op1,
425 const TEMPLATE(T, poly_t) op2,
426 slong n,
427 const TEMPLATE(T, ctx_t) ctx);
428
429 FLINT_DLL void _TEMPLATE(T, poly_mullow)(TEMPLATE(T, struct) *rop,
430 const TEMPLATE(T, struct) *op1, slong len1,
431 const TEMPLATE(T, struct) *op2, slong len2,
432 slong n,
433 const TEMPLATE(T, ctx_t) ctx);
434
435 FLINT_DLL void TEMPLATE(T, poly_mullow)(TEMPLATE(T, poly_t) rop,
436 const TEMPLATE(T, poly_t) op1,
437 const TEMPLATE(T, poly_t) op2,
438 slong n,
439 const TEMPLATE(T, ctx_t) ctx);
440
441 FLINT_DLL void _TEMPLATE(T, poly_mulhigh_classical)(
442 TEMPLATE(T, struct)* rop,
443 const TEMPLATE(T, struct)* op1, slong len1,
444 const TEMPLATE(T, struct)* op2, slong len2,
445 slong start,
446 const TEMPLATE(T, ctx_t) ctx);
447
448 FLINT_DLL void TEMPLATE(T, poly_mulhigh_classical)(TEMPLATE(T, poly_t) rop,
449 const TEMPLATE(T, poly_t) op1,
450 const TEMPLATE(T, poly_t) op2,
451 slong start,
452 const TEMPLATE(T, ctx_t) ctx);
453
454 FLINT_DLL void _TEMPLATE(T, poly_mulhigh)(TEMPLATE(T, struct)* res,
455 const TEMPLATE(T, struct)* poly1, slong len1,
456 const TEMPLATE(T, struct)* poly2, slong len2,
457 slong n, TEMPLATE(T, ctx_t) ctx);
458
459 FLINT_DLL void TEMPLATE(T, poly_mulhigh)(TEMPLATE(T, poly_t) rop,
460 const TEMPLATE(T, poly_t) op1,
461 const TEMPLATE(T, poly_t) op2, slong start,
462 const TEMPLATE(T, ctx_t) ctx);
463
464 FLINT_DLL void _TEMPLATE(T, poly_mulmod)(TEMPLATE(T, struct) * res,
465 const TEMPLATE(T, struct) * poly1, slong len1,
466 const TEMPLATE(T, struct) * poly2, slong len2,
467 const TEMPLATE(T, struct) * f, slong lenf,
468 const TEMPLATE(T, ctx_t) ctx);
469
470 FLINT_DLL void TEMPLATE(T, poly_mulmod)(TEMPLATE(T, poly_t) res,
471 const TEMPLATE(T, poly_t) poly1,
472 const TEMPLATE(T, poly_t) poly2,
473 const TEMPLATE(T, poly_t) f,
474 const TEMPLATE(T, ctx_t) ctx);
475
476 FLINT_DLL void _TEMPLATE(T, poly_mulmod_preinv)(TEMPLATE(T, struct) *res,
477 const TEMPLATE(T, struct) *poly1, slong len1,
478 const TEMPLATE(T, struct) *poly2, slong len2,
479 const TEMPLATE(T, struct) *f, slong lenf,
480 const TEMPLATE(T, struct) *finv, slong lenfinv,
481 const TEMPLATE(T, ctx_t) ctx);
482 FLINT_DLL void TEMPLATE(T, poly_mulmod_preinv)(TEMPLATE(T, poly_t) res,
483 const TEMPLATE(T, poly_t) poly1,
484 const TEMPLATE(T, poly_t) poly2,
485 const TEMPLATE(T, poly_t) f,
486 const TEMPLATE(T, poly_t) finv,
487 const TEMPLATE(T, ctx_t) ctx);
488
489 /* Squaring ******************************************************************/
490
491 FLINT_DLL void _TEMPLATE(T, poly_sqr_classical)(TEMPLATE(T, struct) *rop,
492 const TEMPLATE(T, struct) *op, slong len,
493 const TEMPLATE(T, ctx_t) ctx);
494
495 FLINT_DLL void TEMPLATE(T, poly_sqr_classical)(TEMPLATE(T, poly_t) rop,
496 const TEMPLATE(T, poly_t) op,
497 const TEMPLATE(T, ctx_t) ctx);
498
499 FLINT_DLL void _TEMPLATE(T, poly_sqr_reorder)(TEMPLATE(T, struct) *rop,
500 const TEMPLATE(T, struct) *op, slong len,
501 const TEMPLATE(T, ctx_t) ctx);
502
503 FLINT_DLL void TEMPLATE(T, poly_sqr_reorder)(TEMPLATE(T, poly_t) rop,
504 const TEMPLATE(T, poly_t) op,
505 const TEMPLATE(T, ctx_t) ctx);
506
507 FLINT_DLL void _TEMPLATE(T, poly_sqr_KS)(TEMPLATE(T, struct) *rop,
508 const TEMPLATE(T, struct) *op, slong len,
509 const TEMPLATE(T, ctx_t) ctx);
510
511 FLINT_DLL void TEMPLATE(T, poly_sqr_KS)(TEMPLATE(T, poly_t) rop,
512 const TEMPLATE(T, poly_t) op,
513 const TEMPLATE(T, ctx_t) ctx);
514
515 FLINT_DLL void _TEMPLATE(T, poly_sqr)(TEMPLATE(T, struct) *rop,
516 const TEMPLATE(T, struct) *op, slong len,
517 const TEMPLATE(T, ctx_t) ctx);
518
519 FLINT_DLL void TEMPLATE(T, poly_sqr)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op,
520 const TEMPLATE(T, ctx_t) ctx);
521
522 /* Powering ****************************************************************/
523
524 FLINT_DLL void _TEMPLATE(T, poly_pow)(TEMPLATE(T, struct) *rop,
525 const TEMPLATE(T, struct) *op, slong len,
526 ulong e,
527 const TEMPLATE(T, ctx_t) ctx);
528
529 FLINT_DLL void TEMPLATE(T, poly_pow)(TEMPLATE(T, poly_t) rop,
530 const TEMPLATE(T, poly_t) op,
531 ulong e,
532 const TEMPLATE(T, ctx_t) ctx);
533
534 FLINT_DLL void _TEMPLATE(T, poly_pow_trunc_binexp) (TEMPLATE(T, struct) * res,
535 const TEMPLATE(T, struct) * poly, ulong e,
536 slong trunc, const TEMPLATE(T, ctx_t) ctx);
537
538 FLINT_DLL void TEMPLATE(T, poly_pow_trunc_binexp) (TEMPLATE(T, poly_t) res,
539 const TEMPLATE(T, poly_t) poly, ulong e,
540 slong trunc, const TEMPLATE(T, ctx_t) ctx);
541
542 FLINT_DLL void _TEMPLATE(T, poly_pow_trunc) (TEMPLATE(T, struct) * res,
543 const TEMPLATE(T, struct) * poly, ulong e,
544 slong trunc, const TEMPLATE(T, ctx_t) ctx);
545
546 FLINT_DLL void TEMPLATE(T, poly_pow_trunc) (TEMPLATE(T, poly_t) res,
547 const TEMPLATE(T, poly_t) poly, ulong e, slong trunc, const TEMPLATE(T, ctx_t) ctx);
548
549 FLINT_DLL void _TEMPLATE(T, poly_powmod_fmpz_binexp)(TEMPLATE(T, struct) * res,
550 const TEMPLATE(T, struct) * poly,
551 const fmpz_t e,
552 const TEMPLATE(T, struct) * f, slong lenf,
553 const TEMPLATE(T, ctx_t) ctx);
554
555 FLINT_DLL void TEMPLATE(T, poly_powmod_fmpz_binexp)(TEMPLATE(T, poly_t) res,
556 const TEMPLATE(T, poly_t) poly,
557 const fmpz_t e,
558 const TEMPLATE(T, poly_t) f,
559 const TEMPLATE(T, ctx_t) ctx);
560
561 FLINT_DLL void _TEMPLATE(T, poly_powmod_fmpz_binexp_preinv)(
562 TEMPLATE(T, struct) * res,
563 const TEMPLATE(T, struct) * poly,
564 const fmpz_t e,
565 const TEMPLATE(T, struct) * f, slong lenf,
566 const TEMPLATE(T, struct) *finv, slong lenfinv,
567 const TEMPLATE(T, ctx_t) ctx);
568
569 FLINT_DLL void TEMPLATE(T, poly_powmod_fmpz_binexp_preinv)(
570 TEMPLATE(T, poly_t) res,
571 const TEMPLATE(T, poly_t) poly, const fmpz_t e,
572 const TEMPLATE(T, poly_t) f, const TEMPLATE(T, poly_t) finv,
573 const TEMPLATE(T, ctx_t) ctx);
574
575 FLINT_DLL void _TEMPLATE(T, poly_powmod_ui_binexp)(
576 TEMPLATE(T, struct) * res,
577 const TEMPLATE(T, struct) * poly,
578 ulong e,
579 const TEMPLATE(T, struct) * f, slong lenf,
580 const TEMPLATE(T, ctx_t) ctx);
581
582 FLINT_DLL void TEMPLATE(T, poly_powmod_ui_binexp)(
583 TEMPLATE(T, poly_t) res,
584 const TEMPLATE(T, poly_t) poly, ulong e,
585 const TEMPLATE(T, poly_t) f,
586 const TEMPLATE(T, ctx_t) ctx);
587
588 FLINT_DLL void _TEMPLATE(T, poly_powmod_ui_binexp_preinv)(
589 TEMPLATE(T, struct) * res,
590 const TEMPLATE(T, struct) * poly,
591 ulong e,
592 const TEMPLATE(T, struct) * f, slong lenf,
593 const TEMPLATE(T, struct) * finv, slong lenfinv,
594 const TEMPLATE(T, ctx_t) ctx);
595
596 FLINT_DLL void TEMPLATE(T, poly_powmod_ui_binexp_preinv)(
597 TEMPLATE(T, poly_t) res,
598 const TEMPLATE(T, poly_t) poly,
599 ulong e,
600 const TEMPLATE(T, poly_t) f,
601 const TEMPLATE(T, poly_t) finv,
602 const TEMPLATE(T, ctx_t) ctx);
603
604 FLINT_DLL void _TEMPLATE(T, poly_powmod_fmpz_sliding_preinv)(
605 TEMPLATE(T, struct) * res,
606 const TEMPLATE(T, struct) * poly,
607 const fmpz_t e, ulong k,
608 const TEMPLATE(T, struct) * f, slong lenf,
609 const TEMPLATE(T, struct) * finv, slong lenfinv,
610 const TEMPLATE(T, ctx_t) ctx);
611
612 FLINT_DLL void TEMPLATE(T, poly_powmod_fmpz_sliding_preinv)(
613 TEMPLATE(T, poly_t) res,
614 const TEMPLATE(T, poly_t) poly,
615 const fmpz_t e, ulong k,
616 const TEMPLATE(T, poly_t) f,
617 const TEMPLATE(T, poly_t) finv,
618 const TEMPLATE(T, ctx_t) ctx);
619
620
621 FLINT_DLL void _TEMPLATE(T, poly_powmod_x_fmpz_preinv)(
622 TEMPLATE(T, struct) * res, const fmpz_t e,
623 const TEMPLATE(T, struct) * f, slong lenf,
624 const TEMPLATE(T, struct)* finv, slong lenfinv,
625 const TEMPLATE(T, ctx_t) ctx);
626
627 FLINT_DLL void TEMPLATE(T, poly_powmod_x_fmpz_preinv)(
628 TEMPLATE(T, poly_t) res, const fmpz_t e,
629 const TEMPLATE(T, poly_t) f,
630 const TEMPLATE(T, poly_t) finv,
631 const TEMPLATE(T, ctx_t) ctx);
632
633 /* Shifting ****************************************************************/
634
635 FLINT_DLL void _TEMPLATE(T, poly_shift_left)(TEMPLATE(T, struct) *rop,
636 const TEMPLATE(T, struct) *op, slong len,
637 slong n,
638 const TEMPLATE(T, ctx_t) ctx);
639
640 FLINT_DLL void TEMPLATE(T, poly_shift_left)(TEMPLATE(T, poly_t) rop,
641 const TEMPLATE(T, poly_t) op,
642 slong n,
643 const TEMPLATE(T, ctx_t) ctx);
644
645 FLINT_DLL void _TEMPLATE(T, poly_shift_right)(TEMPLATE(T, struct) *rop,
646 const TEMPLATE(T, struct) *op, slong len,
647 slong n,
648 const TEMPLATE(T, ctx_t) ctx);
649
650 FLINT_DLL void TEMPLATE(T, poly_shift_right)(TEMPLATE(T, poly_t) rop,
651 const TEMPLATE(T, poly_t) op,
652 slong n,
653 const TEMPLATE(T, ctx_t) ctx);
654
655 /* Norms *******************************************************************/
656
657 FLINT_DLL slong _TEMPLATE(T, poly_hamming_weight)(const TEMPLATE(T, struct) *op, slong len,
658 const TEMPLATE(T, ctx_t) ctx);
659
660 FLINT_DLL slong TEMPLATE(T, poly_hamming_weight)(const TEMPLATE(T, poly_t) op,
661 const TEMPLATE(T, ctx_t) ctx);
662
663 /* Greatest common divisor *************************************************/
664
665 FLINT_DLL void TEMPLATE(T, poly_gcd_euclidean)(TEMPLATE(T, poly_t) rop,
666 const TEMPLATE(T, poly_t) op1,
667 const TEMPLATE(T, poly_t) op2,
668 const TEMPLATE(T, ctx_t) ctx);
669
670 FLINT_DLL slong _TEMPLATE(T, poly_gcd_euclidean)(TEMPLATE(T, struct)* G,
671 const TEMPLATE(T, struct)* A, slong lenA,
672 const TEMPLATE(T, struct)* B, slong lenB,
673 const TEMPLATE(T, t) invB,
674 const TEMPLATE(T, ctx_t) ctx);
675
676 FLINT_DLL slong _TEMPLATE(T, poly_gcd)(TEMPLATE(T, struct)* G,
677 const TEMPLATE(T, struct)* A, slong lenA,
678 const TEMPLATE(T, struct)* B, slong lenB,
679 const TEMPLATE(T, t) invB,
680 const TEMPLATE(T, ctx_t) ctx);
681
682 FLINT_DLL void TEMPLATE(T, poly_gcd)(TEMPLATE(T, poly_t) rop,
683 const TEMPLATE(T, poly_t) op1,
684 const TEMPLATE(T, poly_t) op2,
685 const TEMPLATE(T, ctx_t) ctx);
686
687 FLINT_DLL slong _TEMPLATE(T, poly_gcd_euclidean_f)(TEMPLATE(T, t) f, TEMPLATE(T, struct)* G,
688 const TEMPLATE(T, struct)* A, slong lenA,
689 const TEMPLATE(T, struct)* B, slong lenB,
690 const TEMPLATE(T, ctx_t) ctx);
691
692 FLINT_DLL void TEMPLATE(T, poly_gcd_euclidean_f)(TEMPLATE(T, t) f, TEMPLATE(T, poly_t) G,
693 const TEMPLATE(T, poly_t) A,
694 const TEMPLATE(T, poly_t) B,
695 const TEMPLATE(T, ctx_t) ctx);
696
697 FLINT_DLL slong _TEMPLATE(T, poly_hgcd)(TEMPLATE(T, struct) **M, slong *lenM,
698 TEMPLATE(T, struct)* A, slong *lenA,
699 TEMPLATE(T, struct)* B, slong *lenB,
700 const TEMPLATE(T, struct)* a, slong lena,
701 const TEMPLATE(T, struct)* b, slong lenb,
702 const TEMPLATE(T, ctx_t) ctx);
703
704
705 FLINT_DLL slong _TEMPLATE(T, poly_gcd_hgcd)(TEMPLATE(T, struct)* G,
706 const TEMPLATE(T, struct)* A, slong lenA,
707 const TEMPLATE(T, struct)* B, slong lenB,
708 const TEMPLATE(T, t) invB,
709 const TEMPLATE(T, ctx_t) ctx);
710
711 FLINT_DLL void TEMPLATE(T, poly_gcd_hgcd)(TEMPLATE(T, poly_t) G,
712 const TEMPLATE(T, poly_t) A,
713 const TEMPLATE(T, poly_t) B,
714 const TEMPLATE(T, ctx_t) ctx);
715
716 FLINT_DLL slong _TEMPLATE(T, poly_xgcd_euclidean_f)(TEMPLATE(T, t) f, TEMPLATE(T, struct) *G,
717 TEMPLATE(T, struct) *S,
718 TEMPLATE(T, struct) *T,
719 const TEMPLATE(T, struct) *A, slong lenA,
720 const TEMPLATE(T, struct) *B, slong lenB,
721 const TEMPLATE(T, ctx_t) ctx);
722
723 FLINT_DLL void TEMPLATE(T, poly_xgcd_euclidean_f)(TEMPLATE(T, t) f, TEMPLATE(T, poly_t) G,
724 TEMPLATE(T, poly_t) S,
725 TEMPLATE(T, poly_t) T,
726 const TEMPLATE(T, poly_t) A,
727 const TEMPLATE(T, poly_t) B,
728 const TEMPLATE(T, ctx_t) ctx);
729
730 FLINT_DLL slong _TEMPLATE(T, poly_xgcd_euclidean)(TEMPLATE(T, struct) *G,
731 TEMPLATE(T, struct) *S,
732 TEMPLATE(T, struct) *T,
733 const TEMPLATE(T, struct) *A, slong lenA,
734 const TEMPLATE(T, struct) *B, slong lenB,
735 const TEMPLATE(T, t) invB,
736 const TEMPLATE(T, ctx_t) ctx);
737
738 FLINT_DLL void TEMPLATE(T, poly_xgcd_euclidean)(TEMPLATE(T, poly_t) G,
739 TEMPLATE(T, poly_t) S, TEMPLATE(T, poly_t) T,
740 const TEMPLATE(T, poly_t) A,
741 const TEMPLATE(T, poly_t) B,
742 const TEMPLATE(T, ctx_t) ctx);
743
744 FQ_POLY_TEMPLATES_INLINE slong
_TEMPLATE(T,poly_xgcd)745 _TEMPLATE(T, poly_xgcd)(TEMPLATE(T, struct) *G,
746 TEMPLATE(T, struct) *S, TEMPLATE(T, struct) *T,
747 const TEMPLATE(T, struct) *A, slong lenA,
748 const TEMPLATE(T, struct) *B, slong lenB,
749 const TEMPLATE(T, t) invB,
750 const TEMPLATE(T, ctx_t) ctx)
751 {
752 return _TEMPLATE(T, poly_xgcd_euclidean)(G, S, T, A, lenA,
753 B, lenB, invB, ctx);
754 }
755
756
757 FQ_POLY_TEMPLATES_INLINE void
TEMPLATE(T,poly_xgcd)758 TEMPLATE(T, poly_xgcd)(TEMPLATE(T, poly_t) G,
759 TEMPLATE(T, poly_t) S, TEMPLATE(T, poly_t) T,
760 const TEMPLATE(T, poly_t) A,
761 const TEMPLATE(T, poly_t) B,
762 const TEMPLATE(T, ctx_t) ctx)
763 {
764 TEMPLATE(T, poly_xgcd_euclidean)(G, S, T, A, B, ctx);
765 }
766
767
768 /* Euclidean division ******************************************************/
769
770 FLINT_DLL ulong TEMPLATE(T, poly_remove)(TEMPLATE(T, poly_t) f,
771 const TEMPLATE(T, poly_t) g,
772 const TEMPLATE(T, ctx_t) ctx);
773
774 FLINT_DLL void _TEMPLATE(T, poly_div_basecase)(TEMPLATE(T, struct) *Q, TEMPLATE(T, struct) *R,
775 const TEMPLATE(T, struct) *A, slong lenA,
776 const TEMPLATE(T, struct) *B, slong lenB,
777 const TEMPLATE(T, t) invB,
778 const TEMPLATE(T, ctx_t) ctx);
779
780 FLINT_DLL void TEMPLATE(T, poly_div_basecase)(TEMPLATE(T, poly_t) Q,
781 const TEMPLATE(T, poly_t) A,
782 const TEMPLATE(T, poly_t) B,
783 const TEMPLATE(T, ctx_t) ctx);
784
785 FLINT_DLL void _TEMPLATE(T, poly_divrem_basecase)(TEMPLATE(T, struct) *Q,
786 TEMPLATE(T, struct) *R,
787 const TEMPLATE(T, struct) *A, slong lenA,
788 const TEMPLATE(T, struct) *B, slong lenB,
789 const TEMPLATE(T, t) invB,
790 const TEMPLATE(T, ctx_t) ctx);
791
792 FLINT_DLL void TEMPLATE(T, poly_divrem_basecase)(TEMPLATE(T, poly_t) Q, TEMPLATE(T, poly_t) R,
793 const TEMPLATE(T, poly_t) A,
794 const TEMPLATE(T, poly_t) B,
795 const TEMPLATE(T, ctx_t) ctx);
796
797 FLINT_DLL void _TEMPLATE(T, poly_divrem_divconquer_recursive)(
798 TEMPLATE(T, struct) * Q, TEMPLATE(T, struct) * BQ,
799 TEMPLATE(T, struct) * W,
800 const TEMPLATE(T, struct) * A,
801 const TEMPLATE(T, struct) * B, slong lenB,
802 const TEMPLATE(T, t) invB,
803 const TEMPLATE(T, ctx_t) ctx);
804
805 FLINT_DLL void _TEMPLATE(T, poly_divrem_divconquer)(
806 TEMPLATE(T, struct) *Q, TEMPLATE(T, struct) *R,
807 const TEMPLATE(T, struct) *A, slong lenA,
808 const TEMPLATE(T, struct) *B, slong lenB,
809 const TEMPLATE(T, t) invB,
810 const TEMPLATE(T, ctx_t) ctx);
811
812 FLINT_DLL void TEMPLATE(T, poly_divrem_divconquer)(TEMPLATE(T, poly_t) Q,
813 TEMPLATE(T, poly_t) R,
814 const TEMPLATE(T, poly_t) A,
815 const TEMPLATE(T, poly_t) B,
816 const TEMPLATE(T, ctx_t) ctx);
817
818 FQ_POLY_TEMPLATES_INLINE void
_TEMPLATE(T,poly_divrem)819 _TEMPLATE(T, poly_divrem)(TEMPLATE(T, struct) *Q, TEMPLATE(T, struct) *R,
820 const TEMPLATE(T, struct) *A, slong lenA,
821 const TEMPLATE(T, struct) *B, slong lenB,
822 const TEMPLATE(T, t) invB,
823 const TEMPLATE(T, ctx_t) ctx)
824 {
825 _TEMPLATE(T, poly_divrem_divconquer)(Q, R, A, lenA, B, lenB, invB, ctx);
826 }
827
828 FQ_POLY_TEMPLATES_INLINE void
TEMPLATE(T,poly_divrem)829 TEMPLATE(T, poly_divrem)(TEMPLATE(T, poly_t) Q, TEMPLATE(T, poly_t) R,
830 const TEMPLATE(T, poly_t) A,
831 const TEMPLATE(T, poly_t) B,
832 const TEMPLATE(T, ctx_t) ctx)
833 {
834 TEMPLATE(T, poly_divrem_divconquer)(Q, R, A, B, ctx);
835 }
836
837 FQ_POLY_TEMPLATES_INLINE void
_TEMPLATE(T,poly_rem)838 _TEMPLATE(T, poly_rem)(TEMPLATE(T, struct) *R,
839 const TEMPLATE(T, struct) *A, slong lenA,
840 const TEMPLATE(T, struct) *B, slong lenB,
841 const TEMPLATE(T, t) invB,
842 const TEMPLATE(T, ctx_t) ctx)
843 {
844 TEMPLATE(T, struct) *Q = _TEMPLATE(T, vec_init)(lenA - lenB + 1, ctx);
845
846 if (lenA < lenB)
847 {
848 _TEMPLATE(T, vec_set)(R, A, lenA, ctx);
849 _TEMPLATE(T, vec_zero)(R + lenA, lenB - 1 - lenA, ctx);
850 }
851 else
852 {
853 TEMPLATE(T, struct) *T = _TEMPLATE(T, vec_init)(lenA, ctx);
854 _TEMPLATE(T, poly_divrem_divconquer)(Q, T, A, lenA, B, lenB, invB, ctx);
855 _TEMPLATE(T, vec_set)(R, T, lenB - 1, ctx);
856 _TEMPLATE(T, vec_clear)(T, lenA, ctx);
857 }
858
859 _TEMPLATE(T, vec_clear)(Q, lenA - lenB + 1, ctx);
860 }
861
862
863
864 FQ_POLY_TEMPLATES_INLINE void
TEMPLATE(T,poly_rem)865 TEMPLATE(T, poly_rem)(TEMPLATE(T, poly_t) R,
866 const TEMPLATE(T, poly_t) A, const TEMPLATE(T, poly_t) B,
867 const TEMPLATE(T, ctx_t) ctx)
868 {
869 TEMPLATE(T, poly_t) Q;
870 TEMPLATE(T, poly_init)(Q, ctx);
871 TEMPLATE(T, poly_divrem)(Q, R, A, B, ctx);
872 TEMPLATE(T, poly_clear)(Q, ctx);
873 }
874
875 FLINT_DLL void _TEMPLATE(T, poly_inv_series_newton)(TEMPLATE(T, struct) * Qinv,
876 const TEMPLATE(T, struct) * Q, slong n,
877 const TEMPLATE(T, t) cinv,
878 const TEMPLATE(T, ctx_t) ctx);
879
880 FLINT_DLL void TEMPLATE(T, poly_inv_series_newton)(TEMPLATE(T, poly_t) Qinv,
881 const TEMPLATE(T, poly_t) Q, slong n,
882 const TEMPLATE(T, ctx_t) ctx);
883
884 FQ_POLY_TEMPLATES_INLINE void
_TEMPLATE(T,poly_inv_series)885 _TEMPLATE(T, poly_inv_series)(TEMPLATE(T, struct) * Qinv,
886 const TEMPLATE(T, struct) * Q, slong n,
887 const TEMPLATE(T, t) cinv,
888 const TEMPLATE(T, ctx_t) ctx)
889 {
890 _TEMPLATE(T, poly_inv_series_newton) (Qinv, Q, n, cinv, ctx);
891 }
892
893 FQ_POLY_TEMPLATES_INLINE void
TEMPLATE(T,poly_inv_series)894 TEMPLATE(T, poly_inv_series)(TEMPLATE(T, poly_t) Qinv,
895 const TEMPLATE(T, poly_t) Q, slong n,
896 const TEMPLATE(T, ctx_t) ctx)
897 {
898 TEMPLATE(T, poly_inv_series_newton) (Qinv, Q, n, ctx);
899 }
900
901 FLINT_DLL void _TEMPLATE(T, poly_div_series) (TEMPLATE(T, struct) * Q,
902 const TEMPLATE(T, struct) * A, slong Alen,
903 const TEMPLATE(T, struct) * B, slong Blen,
904 slong n, const TEMPLATE(T, ctx_t) ctx);
905
906 FLINT_DLL void TEMPLATE(T, poly_div_series)(TEMPLATE(T, poly_t) Q,
907 const TEMPLATE(T, poly_t) A, const TEMPLATE(T, poly_t) B,
908 slong n, const TEMPLATE(T, ctx_t) ctx);
909
910 FLINT_DLL void _TEMPLATE(T, poly_div_newton_n_preinv) (
911 TEMPLATE(T, struct) *Q,
912 const TEMPLATE(T, struct) *A, slong lenA,
913 const TEMPLATE(T, struct)* B, slong lenB,
914 const TEMPLATE(T, struct)* Binv, slong lenBinv,
915 const TEMPLATE(T, ctx_t) ctx);
916
917 FLINT_DLL void TEMPLATE(T, poly_div_newton_n_preinv) (TEMPLATE(T, poly_t) Q,
918 const TEMPLATE(T, poly_t) A,
919 const TEMPLATE(T, poly_t) B,
920 const TEMPLATE(T, poly_t) Binv,
921 const TEMPLATE(T, ctx_t) ctx);
922
923 FLINT_DLL void _TEMPLATE(T, poly_divrem_newton_n_preinv) (
924 TEMPLATE(T, struct)* Q, TEMPLATE(T, struct)* R,
925 const TEMPLATE(T, struct)* A, slong lenA,
926 const TEMPLATE(T, struct)* B, slong lenB,
927 const TEMPLATE(T, struct)* Binv, slong lenBinv,
928 const TEMPLATE(T, ctx_t) ctx);
929
930 FLINT_DLL void TEMPLATE(T, poly_divrem_newton_n_preinv)(
931 TEMPLATE(T, poly_t) Q, TEMPLATE(T, poly_t) R,
932 const TEMPLATE(T, poly_t) A, const TEMPLATE(T, poly_t) B,
933 const TEMPLATE(T, poly_t) Binv, const TEMPLATE(T, ctx_t) ctx);
934
935
936 FLINT_DLL void _TEMPLATE(T, poly_divrem_f)(TEMPLATE(T, t) f,
937 TEMPLATE(T, struct)* Q, TEMPLATE(T, struct)* R,
938 const TEMPLATE(T, struct)* A, slong lenA,
939 const TEMPLATE(T, struct)* B, slong lenB,
940 const TEMPLATE(T, ctx_t) ctx);
941
942 FLINT_DLL void TEMPLATE(T, poly_divrem_f)(TEMPLATE(T, t) f,
943 TEMPLATE(T, poly_t) Q, TEMPLATE(T, poly_t) R,
944 const TEMPLATE(T, poly_t) A,
945 const TEMPLATE(T, poly_t) B,
946 const TEMPLATE(T, ctx_t) ctx);
947
948 /* Divisibility testing ***************************************************/
949
950 FLINT_DLL int _TEMPLATE(T, poly_divides)(TEMPLATE(T, struct) *Q,
951 const TEMPLATE(T, struct) *A, slong lenA,
952 const TEMPLATE(T, struct) *B, slong lenB,
953 const TEMPLATE(T, t) invB,
954 const TEMPLATE(T, ctx_t) ctx);
955
956 FLINT_DLL int TEMPLATE(T, poly_divides)(TEMPLATE(T, poly_t) Q,
957 const TEMPLATE(T, poly_t) A, const TEMPLATE(T, poly_t) B,
958 const TEMPLATE(T, ctx_t) ctx);
959
960 /* Derivative **************************************************************/
961
962 FLINT_DLL void _TEMPLATE(T, poly_derivative)(TEMPLATE(T, struct) *rop,
963 const TEMPLATE(T, struct) *op, slong len,
964 const TEMPLATE(T, ctx_t) ctx);
965
966 FLINT_DLL void TEMPLATE(T, poly_derivative)(TEMPLATE(T, poly_t) rop,
967 const TEMPLATE(T, poly_t) op,
968 const TEMPLATE(T, ctx_t) ctx);
969
970 /* Evaluation **************************************************************/
971
972 FLINT_DLL void _TEMPLATE3(T, poly_evaluate, T)(TEMPLATE(T, t) rop,
973 const TEMPLATE(T, struct) *op, slong len,
974 const TEMPLATE(T, t) a,
975 const TEMPLATE(T, ctx_t) ctx);
976
977 FLINT_DLL void TEMPLATE3(T, poly_evaluate, T)(TEMPLATE(T, t) res,
978 const TEMPLATE(T, poly_t) f,
979 const TEMPLATE(T, t) a,
980 const TEMPLATE(T, ctx_t) ctx);
981
982 FLINT_DLL void _TEMPLATE4(T, poly_evaluate, T, vec)(TEMPLATE(T, struct) * ys,
983 const TEMPLATE(T, struct) *coeffs, slong len,
984 const TEMPLATE(T, struct) *xs, slong n,
985 const TEMPLATE(T, ctx_t) ctx);
986
987 FLINT_DLL void TEMPLATE4(T, poly_evaluate, T, vec)(TEMPLATE(T, struct) * ys,
988 const TEMPLATE(T, poly_t) poly,
989 const TEMPLATE(T, struct) * xs, slong n,
990 const TEMPLATE(T, ctx_t) ctx);
991
992 FLINT_DLL TEMPLATE(T, poly_struct) **
993 _TEMPLATE(T, poly_tree_alloc)(slong len, const TEMPLATE(T, ctx_t) ctx);
994
995 FLINT_DLL void _TEMPLATE(T, poly_tree_free)(TEMPLATE(T, poly_struct) ** tree, slong len,
996 const TEMPLATE(T, ctx_t) ctx);
997
998 FLINT_DLL void _TEMPLATE(T, poly_tree_build)(TEMPLATE(T, poly_struct) ** tree,
999 const TEMPLATE(T, struct) * roots,
1000 slong len,
1001 const TEMPLATE(T, ctx_t) ctx);
1002
1003 FLINT_DLL void _TEMPLATE4(T, poly_evaluate, T, vec_fast_precomp)
1004 (TEMPLATE(T, struct) * vs,
1005 const TEMPLATE(T, struct) * poly, slong plen,
1006 TEMPLATE(T, poly_struct) * const * tree, slong len,
1007 const TEMPLATE(T, ctx_t) ctx);
1008
1009 FLINT_DLL void _TEMPLATE4(T, poly_evaluate, T, vec_fast)(TEMPLATE(T, struct) * ys,
1010 const TEMPLATE(T, struct) * poly, slong plen,
1011 const TEMPLATE(T, struct) * xs, slong n,
1012 const TEMPLATE(T, ctx_t) ctx);
1013
1014 FLINT_DLL void TEMPLATE4(T, poly_evaluate, T, vec_fast)(TEMPLATE(T, struct) * ys,
1015 const TEMPLATE(T, poly_t) poly,
1016 const TEMPLATE(T, struct) *xs, slong n,
1017 const TEMPLATE(T, ctx_t) ctx);
1018
1019 FLINT_DLL void _TEMPLATE4(T, poly_evaluate, T, vec_iter)(TEMPLATE(T, struct) * ys,
1020 const TEMPLATE(T, struct) * coeffs, slong len,
1021 const TEMPLATE(T, struct) * xs, slong n,
1022 const TEMPLATE(T, ctx_t) ctx);
1023
1024 FLINT_DLL void TEMPLATE4(T, poly_evaluate, T, vec_iter)(TEMPLATE(T, struct) * ys,
1025 const TEMPLATE(T, poly_t) poly,
1026 const TEMPLATE(T, struct) * xs, slong n,
1027 const TEMPLATE(T, ctx_t) ctx);
1028
1029 /* Composition *************************************************************/
1030
1031 FLINT_DLL void _TEMPLATE(T, poly_compose_divconquer)(
1032 TEMPLATE(T, struct) *rop,
1033 const TEMPLATE(T, struct) *op1, slong len1,
1034 const TEMPLATE(T, struct) *op2, slong len2,
1035 const TEMPLATE(T, ctx_t) ctx);
1036
1037 FLINT_DLL void TEMPLATE(T, poly_compose_divconquer)(TEMPLATE(T, poly_t) rop,
1038 const TEMPLATE(T, poly_t) op1,
1039 const TEMPLATE(T, poly_t) op2,
1040 const TEMPLATE(T, ctx_t) ctx);
1041
1042 FLINT_DLL void _TEMPLATE(T, poly_compose_horner)(TEMPLATE(T, struct) *rop,
1043 const TEMPLATE(T, struct) *op1, slong len1,
1044 const TEMPLATE(T, struct) *op2, slong len2,
1045 const TEMPLATE(T, ctx_t) ctx);
1046
1047 FLINT_DLL void TEMPLATE(T, poly_compose_horner)(TEMPLATE(T, poly_t) rop,
1048 const TEMPLATE(T, poly_t) op1,
1049 const TEMPLATE(T, poly_t) op2,
1050 const TEMPLATE(T, ctx_t) ctx);
1051
1052 FLINT_DLL void _TEMPLATE(T, poly_compose)(TEMPLATE(T, struct) *rop,
1053 const TEMPLATE(T, struct) *op1, slong len1,
1054 const TEMPLATE(T, struct) *op2, slong len2,
1055 const TEMPLATE(T, ctx_t) ctx);
1056
1057 FLINT_DLL void TEMPLATE(T, poly_compose)(TEMPLATE(T, poly_t) rop,
1058 const TEMPLATE(T, poly_t) op1,
1059 const TEMPLATE(T, poly_t) op2,
1060 const TEMPLATE(T, ctx_t) ctx);
1061
1062 FLINT_DLL void _TEMPLATE(T, poly_compose_mod)(TEMPLATE(T, struct) * res,
1063 const TEMPLATE(T, struct) * f, slong lenf,
1064 const TEMPLATE(T, struct) * g,
1065 const TEMPLATE(T, struct) * h, slong lenh,
1066 const TEMPLATE(T, ctx_t) ctx);
1067
1068 FLINT_DLL void TEMPLATE(T, poly_compose_mod)(TEMPLATE(T, poly_t) res,
1069 const TEMPLATE(T, poly_t) poly1,
1070 const TEMPLATE(T, poly_t) poly2,
1071 const TEMPLATE(T, poly_t) poly3,
1072 const TEMPLATE(T, ctx_t) ctx);
1073
1074 FLINT_DLL void _TEMPLATE(T, poly_compose_mod_preinv)(
1075 TEMPLATE(T, struct) * res,
1076 const TEMPLATE(T, struct) * f, slong lenf,
1077 const TEMPLATE(T, struct) * g,
1078 const TEMPLATE(T, struct) * h, slong lenh,
1079 const TEMPLATE(T, struct) * hinv, slong lenhinv,
1080 const TEMPLATE(T, ctx_t) ctx);
1081
1082 FLINT_DLL void TEMPLATE(T, poly_compose_mod_preinv)(TEMPLATE(T, poly_t) res,
1083 const TEMPLATE(T, poly_t) poly1,
1084 const TEMPLATE(T, poly_t) poly2,
1085 const TEMPLATE(T, poly_t) poly3,
1086 const TEMPLATE(T, poly_t) poly3inv,
1087 const TEMPLATE(T, ctx_t) ctx);
1088
1089
1090 FLINT_DLL void _TEMPLATE(T, poly_compose_mod_horner)(
1091 TEMPLATE(T, struct) * res,
1092 const TEMPLATE(T, struct) * f, slong lenf,
1093 const TEMPLATE(T, struct) * g,
1094 const TEMPLATE(T, struct) * h, slong lenh,
1095 const TEMPLATE(T, ctx_t) ctx);
1096
1097 FLINT_DLL void TEMPLATE(T, poly_compose_mod_horner)(TEMPLATE(T, poly_t) res,
1098 const TEMPLATE(T, poly_t) poly1,
1099 const TEMPLATE(T, poly_t) poly2,
1100 const TEMPLATE(T, poly_t) poly3,
1101 const TEMPLATE(T, ctx_t) ctx);
1102
1103 FLINT_DLL void _TEMPLATE(T, poly_compose_mod_horner_preinv)(
1104 TEMPLATE(T, struct) * res,
1105 const TEMPLATE(T, struct) * f, slong lenf,
1106 const TEMPLATE(T, struct) * g,
1107 const TEMPLATE(T, struct) * h, slong lenh,
1108 const TEMPLATE(T, struct) * hinv, slong lenhinv,
1109 const TEMPLATE(T, ctx_t) ctx);
1110
1111 FLINT_DLL void TEMPLATE(T, poly_compose_mod_horner_preinv)(TEMPLATE(T, poly_t) res,
1112 const TEMPLATE(T, poly_t) poly1,
1113 const TEMPLATE(T, poly_t) poly2,
1114 const TEMPLATE(T, poly_t) poly3,
1115 const TEMPLATE(T, poly_t) poly3inv,
1116 const TEMPLATE(T, ctx_t) ctx);
1117
1118 FLINT_DLL void TEMPLATE(T, poly_compose_mod_brent_kung)(TEMPLATE(T, poly_t) res,
1119 const TEMPLATE(T, poly_t) poly1,
1120 const TEMPLATE(T, poly_t) poly2,
1121 const TEMPLATE(T, poly_t) poly3,
1122 const TEMPLATE(T, ctx_t) ctx);
1123
1124 FLINT_DLL void _TEMPLATE(T, poly_compose_mod_brent_kung)(
1125 TEMPLATE(T, struct) * res,
1126 const TEMPLATE(T, struct) * poly1, slong len1,
1127 const TEMPLATE(T, struct) * poly2,
1128 const TEMPLATE(T, struct) * poly3, slong len3,
1129 const TEMPLATE(T, ctx_t) ctx);
1130
1131 FLINT_DLL void _TEMPLATE(T, poly_compose_mod_brent_kung_preinv)(
1132 TEMPLATE(T, struct) * res,
1133 const TEMPLATE(T, struct) * poly1, slong len1,
1134 const TEMPLATE(T, struct) * poly2,
1135 const TEMPLATE(T, struct) * poly3, slong len3,
1136 const TEMPLATE(T, struct) * poly3inv, slong len3inv,
1137 const TEMPLATE(T, ctx_t) ctx);
1138
1139 FLINT_DLL void TEMPLATE(T, poly_compose_mod_brent_kung_preinv)(
1140 TEMPLATE(T, poly_t) res,
1141 const TEMPLATE(T, poly_t) poly1,
1142 const TEMPLATE(T, poly_t) poly2,
1143 const TEMPLATE(T, poly_t) poly3,
1144 const TEMPLATE(T, poly_t) poly3inv,
1145 const TEMPLATE(T, ctx_t) ctx);
1146
1147 FLINT_DLL void _TEMPLATE(T, poly_reduce_matrix_mod_poly) (TEMPLATE(T, mat_t) A,
1148 const TEMPLATE(T, mat_t) B,
1149 const TEMPLATE(T, poly_t) f,
1150 const TEMPLATE(T, ctx_t) ctx);
1151
1152 FLINT_DLL void _TEMPLATE(T, poly_precompute_matrix) (
1153 TEMPLATE(T, mat_t A),
1154 const TEMPLATE(T, struct)* poly1,
1155 const TEMPLATE(T, struct)* poly2, slong len2,
1156 const TEMPLATE(T, struct)* poly2inv, slong len2inv,
1157 const TEMPLATE(T, ctx_t) ctx);
1158
1159 FLINT_DLL void TEMPLATE(T, poly_precompute_matrix) (TEMPLATE(T, mat_t A),
1160 const TEMPLATE(T, poly_t) poly1,
1161 const TEMPLATE(T, poly_t) poly2,
1162 const TEMPLATE(T, poly_t) poly2inv,
1163 const TEMPLATE(T, ctx_t) ctx);
1164
1165 FLINT_DLL void _TEMPLATE(T, poly_compose_mod_brent_kung_precomp_preinv)(
1166 TEMPLATE(T, struct)* res,
1167 const TEMPLATE(T, struct)* poly1, slong len1,
1168 const TEMPLATE(T, mat_t) A,
1169 const TEMPLATE(T, struct)* poly3, slong len3,
1170 const TEMPLATE(T, struct)* poly3inv, slong len3inv,
1171 const TEMPLATE(T, ctx_t) ctx);
1172
1173 FLINT_DLL void TEMPLATE(T, poly_compose_mod_brent_kung_precomp_preinv)(
1174 TEMPLATE(T, poly_t) res,
1175 const TEMPLATE(T, poly_t) poly1,
1176 const TEMPLATE(T, mat_t) A,
1177 const TEMPLATE(T, poly_t) poly3,
1178 const TEMPLATE(T, poly_t) poly3inv,
1179 const TEMPLATE(T, ctx_t) ctx);
1180
1181 /* Input and output ********************************************************/
1182
1183 FLINT_DLL int _TEMPLATE(T, poly_fprint_pretty)(FILE *file,
1184 const TEMPLATE(T, struct) *poly, slong len,
1185 const char *x,
1186 const TEMPLATE(T, ctx_t) ctx);
1187
1188 FLINT_DLL int TEMPLATE(T, poly_fprint_pretty)(FILE * file,
1189 const TEMPLATE(T, poly_t) poly,
1190 const char *x,
1191 const TEMPLATE(T, ctx_t) ctx);
1192
1193 FLINT_DLL int _TEMPLATE(T, poly_fprint)(FILE * file,
1194 const TEMPLATE(T, struct) *poly, slong len,
1195 const TEMPLATE(T, ctx_t) ctx);
1196
1197 FLINT_DLL int TEMPLATE(T, poly_fprint)(FILE * file,
1198 const TEMPLATE(T, poly_t) poly,
1199 const TEMPLATE(T, ctx_t) ctx);
1200
1201 FQ_POLY_TEMPLATES_INLINE int
_TEMPLATE(T,poly_print)1202 _TEMPLATE(T, poly_print)(const TEMPLATE(T, struct) *poly, slong len,
1203 const TEMPLATE(T, ctx_t) ctx)
1204 {
1205 return _TEMPLATE(T, poly_fprint)(stdout, poly, len, ctx);
1206 }
1207
1208 FQ_POLY_TEMPLATES_INLINE int
TEMPLATE(T,poly_print)1209 TEMPLATE(T, poly_print)(const TEMPLATE(T, poly_t) poly,
1210 const TEMPLATE(T, ctx_t) ctx)
1211 {
1212 return TEMPLATE(T, poly_fprint)(stdout, poly, ctx);
1213 }
1214
1215
1216 FQ_POLY_TEMPLATES_INLINE int
_TEMPLATE(T,poly_print_pretty)1217 _TEMPLATE(T, poly_print_pretty)(const TEMPLATE(T, struct) *poly, slong len,
1218 const char *x, const TEMPLATE(T, ctx_t) ctx)
1219 {
1220 return _TEMPLATE(T, poly_fprint_pretty)(stdout, poly, len, x, ctx);
1221 }
1222
1223 FQ_POLY_TEMPLATES_INLINE int
TEMPLATE(T,poly_print_pretty)1224 TEMPLATE(T, poly_print_pretty)(const TEMPLATE(T, poly_t) poly,
1225 const char *x,
1226 const TEMPLATE(T, ctx_t) ctx)
1227 {
1228 return TEMPLATE(T, poly_fprint_pretty)(stdout, poly, x, ctx);
1229 }
1230
1231 FLINT_DLL char * _TEMPLATE(T, poly_get_str_pretty)(const TEMPLATE(T, struct) * poly, slong len,
1232 const char *x,
1233 const TEMPLATE(T, ctx_t) ctx);
1234
1235 FLINT_DLL char * TEMPLATE(T, poly_get_str_pretty)(const TEMPLATE(T, poly_t) poly,
1236 const char *x,
1237 const TEMPLATE(T, ctx_t) ctx);
1238
1239 FLINT_DLL char * _TEMPLATE(T, poly_get_str)(const TEMPLATE(T, struct) * poly, slong len,
1240 const TEMPLATE(T, ctx_t) ctx);
1241
1242 FLINT_DLL char * TEMPLATE(T, poly_get_str)(const TEMPLATE(T, poly_t) poly,
1243 const TEMPLATE(T, ctx_t) ctx);
1244
1245 /* Characteristic polynomial ************************************************/
1246
1247 FLINT_DLL
1248 void TEMPLATE(T, mat_charpoly_danilevsky) (TEMPLATE(T, poly_t) p,
1249 const TEMPLATE(T, mat_t) A, const TEMPLATE(T, ctx_t) ctx);
1250
1251 FQ_POLY_TEMPLATES_INLINE
TEMPLATE(T,mat_charpoly)1252 void TEMPLATE(T, mat_charpoly)(TEMPLATE(T, poly_t) p,
1253 const TEMPLATE(T, mat_t) M, const TEMPLATE(T, ctx_t) ctx)
1254 {
1255 TEMPLATE(T, mat_t) A;
1256
1257 TEMPLATE(T, mat_init) (A, M->r, M->c, ctx);
1258 TEMPLATE(T, mat_set) (A, M, ctx);
1259
1260 if (A->r != A->c)
1261 {
1262 flint_printf("Exception (fq_mat_charpoly). Non-square matrix.\n");
1263 flint_abort();
1264 }
1265
1266 TEMPLATE(T, mat_charpoly_danilevsky) (p, A, ctx);
1267
1268 TEMPLATE(T, mat_clear) (A, ctx);
1269 }
1270
1271 /* Minimal polynomial ************************************************/
1272
1273 FLINT_DLL
1274 void TEMPLATE(T, mat_minpoly) (TEMPLATE(T, poly_t) p,
1275 const TEMPLATE(T, mat_t) X, const TEMPLATE(T, ctx_t) ctx);
1276
1277 #ifdef __cplusplus
1278 }
1279 #endif
1280
1281 #endif
1282