include/flint/fmpz_poly.h

0001 /*
0002     Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013 William Hart
0003     Copyright (C) 2009, 2011 Andy Novocin
0004     Copyright (C) 2010 Sebastian Pancratz
0005     Copyright (C) 2011 Fredrik Johansson
0006
0007     This file is part of FLINT.
0008
0009     FLINT is free software: you can redistribute it and/or modify it under
0010     the terms of the GNU Lesser General Public License (LGPL) as published
0011     by the Free Software Foundation; either version 3 of the License, or
0012     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0013 */
0014
0015 #ifndef FMPZ_POLY_H
0016 #define FMPZ_POLY_H
0017
0018 #ifdef FMPZ_POLY_INLINES_C
0019 #define FMPZ_POLY_INLINE
0020 #else
0021 #define FMPZ_POLY_INLINE static inline
0022 #endif
0023
0024 #include "fmpz_types.h"
0025 #include "nmod_types.h"
0026
0027 #ifdef __cplusplus
0028 extern "C" {
0029 #endif
0030
0031 #define FMPZ_POLY_INV_NEWTON_CUTOFF 32
0032 #define FMPZ_POLY_SQRT_DIVCONQUER_CUTOFF 16
0033 #define FMPZ_POLY_SQRTREM_DIVCONQUER_CUTOFF 16
0034
0035 /*  Type definitions *********************************************************/
0036
0037 typedef struct
0038 {
0039    fmpz ** powers;
0040    slong len;
0041 } fmpz_poly_powers_precomp_struct;
0042
0043 typedef fmpz_poly_powers_precomp_struct fmpz_poly_powers_precomp_t[1];
0044
0045 typedef struct
0046 {
0047    ulong ** jj; /* used by fft_convolution_precache */
0048    slong n;
0049    slong len2;
0050    slong loglen;
0051    slong bits2;
0052    slong limbs;
0053    fmpz_poly_t poly2;
0054 } fmpz_poly_mul_precache_struct;
0055
0056 typedef fmpz_poly_mul_precache_struct fmpz_poly_mul_precache_t[1];
0057
0058 /*  Memory management ********************************************************/
0059
0060 void fmpz_poly_init(fmpz_poly_t poly);
0061
0062 void fmpz_poly_init2(fmpz_poly_t poly, slong alloc);
0063
0064 void fmpz_poly_realloc(fmpz_poly_t poly, slong alloc);
0065
0066 void fmpz_poly_fit_length(fmpz_poly_t poly, slong len);
0067
0068 void fmpz_poly_clear(fmpz_poly_t poly);
0069
0070 void _fmpz_poly_normalise(fmpz_poly_t poly);
0071
0072 void _fmpz_poly_set_length(fmpz_poly_t poly, slong newlen);
0073
0074 FMPZ_POLY_INLINE
0075 void fmpz_poly_attach_truncate(fmpz_poly_t trunc,
0076                                                const fmpz_poly_t poly, slong n)
0077 {
0078    trunc->coeffs = poly->coeffs;
0079    trunc->alloc = poly->alloc;
0080    trunc->length = FLINT_MIN(poly->length, n);
0081 }
0082
0083 FMPZ_POLY_INLINE
0084 void fmpz_poly_attach_shift(fmpz_poly_t trunc, const fmpz_poly_t poly, slong n)
0085 {
0086    trunc->coeffs = poly->coeffs + n;
0087    trunc->alloc = poly->alloc - n;
0088    trunc->length = FLINT_MAX(poly->length - n, 0);
0089 }
0090
0091 /*  Polynomial parameters  ***************************************************/
0092
0093 FMPZ_POLY_INLINE
0094 slong fmpz_poly_length(const fmpz_poly_t poly)
0095 {
0096     return poly->length;
0097 }
0098
0099 FMPZ_POLY_INLINE
0100 slong fmpz_poly_degree(const fmpz_poly_t poly)
0101 {
0102     return poly->length - 1;
0103 }
0104
0105 /*  Assignment and basic manipulation  ***************************************/
0106
0107 void fmpz_poly_set(fmpz_poly_t poly1, const fmpz_poly_t poly2);
0108
0109 void fmpz_poly_set_ui(fmpz_poly_t poly, ulong c);
0110
0111 void fmpz_poly_set_si(fmpz_poly_t poly, slong c);
0112
0113 void fmpz_poly_set_fmpz(fmpz_poly_t poly, const fmpz_t c);
0114
0115 int _fmpz_poly_set_str(fmpz * poly, const char * str);
0116
0117 int fmpz_poly_set_str(fmpz_poly_t poly, const char * str);
0118
0119 char * _fmpz_poly_get_str(const fmpz * poly, slong len);
0120
0121 char * fmpz_poly_get_str(const fmpz_poly_t poly);
0122
0123 char * _fmpz_poly_get_str_pretty(const fmpz * poly, slong len, const char * x);
0124
0125 char * fmpz_poly_get_str_pretty(const fmpz_poly_t poly, const char * x);
0126
0127 FMPZ_POLY_INLINE
0128 void fmpz_poly_zero(fmpz_poly_t poly)
0129 {
0130    _fmpz_poly_set_length(poly, 0);
0131 }
0132
0133 FMPZ_POLY_INLINE
0134 void fmpz_poly_one(fmpz_poly_t poly)
0135 {
0136     fmpz_poly_set_ui(poly, UWORD(1));
0137 }
0138
0139 void fmpz_poly_zero_coeffs(fmpz_poly_t poly, slong i, slong j);
0140
0141 void fmpz_poly_swap(fmpz_poly_t poly1, fmpz_poly_t poly2);
0142
0143 void _fmpz_poly_reverse(fmpz * res, const fmpz * poly, slong len, slong n);
0144
0145 void fmpz_poly_reverse(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
0146
0147 ulong _fmpz_poly_deflation(const fmpz* a, slong len);
0148
0149 FMPZ_POLY_INLINE
0150 ulong fmpz_poly_deflation(const fmpz_poly_t input)
0151 {
0152     return _fmpz_poly_deflation(input->coeffs, input->length);
0153 }
0154
0155 void fmpz_poly_deflate(fmpz_poly_t result, const fmpz_poly_t input,
0156                                                               ulong deflation);
0157
0158 void fmpz_poly_inflate(fmpz_poly_t result, const fmpz_poly_t input,
0159                                                               ulong inflation);
0160
0161 void fmpz_poly_truncate(fmpz_poly_t poly, slong newlen);
0162
0163 void fmpz_poly_set_trunc(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
0164
0165 /*  Randomisation  ***********************************************************/
0166
0167 void fmpz_poly_randtest(fmpz_poly_t f, flint_rand_t state,
0168                                                 slong len, flint_bitcnt_t bits);
0169
0170 void fmpz_poly_randtest_unsigned(fmpz_poly_t f, flint_rand_t state,
0171                                                 slong len, flint_bitcnt_t bits);
0172
0173 void fmpz_poly_randtest_not_zero(fmpz_poly_t f, flint_rand_t state,
0174                                                 slong len, flint_bitcnt_t bits);
0175
0176 void fmpz_poly_randtest_no_real_root(fmpz_poly_t p, flint_rand_t state,
0177                                                 slong len, flint_bitcnt_t bits);
0178
0179 void fmpz_poly_randtest_irreducible1(fmpz_poly_t pol, flint_rand_t state, slong len, flint_bitcnt_t bits);
0180 void fmpz_poly_randtest_irreducible2(fmpz_poly_t pol, flint_rand_t state, slong len, flint_bitcnt_t bits);
0181 void fmpz_poly_randtest_irreducible(fmpz_poly_t pol, flint_rand_t state, slong len, flint_bitcnt_t bits);
0182
0183 /*  Getting and setting coefficients  ****************************************/
0184
0185 slong fmpz_poly_get_coeff_si(const fmpz_poly_t poly, slong n);
0186
0187 void fmpz_poly_set_coeff_si(fmpz_poly_t poly, slong n, slong x);
0188
0189 ulong fmpz_poly_get_coeff_ui(const fmpz_poly_t poly, slong n);
0190
0191 void fmpz_poly_set_coeff_ui(fmpz_poly_t poly, slong n, ulong x);
0192
0193 void fmpz_poly_set_coeff_fmpz(fmpz_poly_t poly, slong n, const fmpz_t x);
0194
0195 void fmpz_poly_get_coeff_fmpz(fmpz_t x, const fmpz_poly_t poly, slong n);
0196
0197 #define fmpz_poly_get_coeff_ptr(poly, n) \
0198     ((n) < (poly)->length ? (poly)->coeffs + (n) : NULL)
0199
0200 #define fmpz_poly_lead(poly) \
0201     ((poly)->length ? (poly)->coeffs + (poly)->length - 1 : NULL)
0202
0203 /*  Comparison  **************************************************************/
0204
0205 int fmpz_poly_equal(const fmpz_poly_t poly1, const fmpz_poly_t poly2);
0206
0207 int fmpz_poly_equal_trunc(const fmpz_poly_t poly1,
0208                                              const fmpz_poly_t poly2, slong n);
0209
0210 #define fmpz_poly_is_zero(poly) \
0211     ((poly)->length == 0)
0212
0213 int _fmpz_poly_is_one(const fmpz *poly, slong len);
0214
0215 FMPZ_POLY_INLINE
0216 int fmpz_poly_is_one(const fmpz_poly_t op)
0217 {
0218     return (op->length) == 1 && (*(op->coeffs) == WORD(1));
0219 }
0220
0221 FMPZ_POLY_INLINE
0222 int fmpz_poly_is_unit(const fmpz_poly_t op)
0223 {
0224     return (op->length == 1) && (*(op->coeffs) == WORD(1) || *(op->coeffs) == WORD(-1));
0225 }
0226
0227 FMPZ_POLY_INLINE
0228 int fmpz_poly_is_gen(const fmpz_poly_t op)
0229 {
0230     return (op->length) == 2 && (*(op->coeffs + 1) == WORD(1)) && (*(op->coeffs + 0) == WORD(0));
0231 }
0232
0233 int fmpz_poly_equal_fmpz(const fmpz_poly_t poly, const fmpz_t c);
0234
0235 /*  Addition and subtraction  ************************************************/
0236
0237 void _fmpz_poly_add(fmpz * res, const fmpz * poly1, slong len1,
0238                                                const fmpz * poly2, slong len2);
0239
0240 void fmpz_poly_add(fmpz_poly_t res, const fmpz_poly_t poly1,
0241                                                       const fmpz_poly_t poly2);
0242
0243 void fmpz_poly_add_series(fmpz_poly_t res, const fmpz_poly_t poly1,
0244                                              const fmpz_poly_t poly2, slong n);
0245
0246 void _fmpz_poly_sub(fmpz * res, const fmpz * poly1, slong len1,
0247                                                const fmpz * poly2, slong len2);
0248
0249 void fmpz_poly_sub(fmpz_poly_t res, const fmpz_poly_t poly1,
0250                                                       const fmpz_poly_t poly2);
0251
0252 void fmpz_poly_sub_series(fmpz_poly_t res, const fmpz_poly_t poly1,
0253                                              const fmpz_poly_t poly2, slong n);
0254
0255 void fmpz_poly_neg(fmpz_poly_t res, const fmpz_poly_t poly);
0256
0257 void fmpz_poly_add_si(fmpz_poly_t res, const fmpz_poly_t poly, slong c);
0258 void fmpz_poly_sub_si(fmpz_poly_t res, const fmpz_poly_t poly, slong c);
0259 void fmpz_poly_si_sub(fmpz_poly_t res, slong c, const fmpz_poly_t poly);
0260 void fmpz_poly_add_fmpz(fmpz_poly_t res, const fmpz_poly_t poly, fmpz_t c);
0261 void fmpz_poly_sub_fmpz(fmpz_poly_t res, const fmpz_poly_t poly, fmpz_t c);
0262 void fmpz_poly_fmpz_sub(fmpz_poly_t res, fmpz_t c, const fmpz_poly_t poly);
0263
0264 /*  Scalar absolute value multiplication and division  ***********************/
0265
0266 void fmpz_poly_scalar_abs(fmpz_poly_t res, const fmpz_poly_t poly);
0267
0268 void fmpz_poly_scalar_mul_ui(fmpz_poly_t poly1,
0269                              const fmpz_poly_t poly2, ulong x);
0270
0271 void fmpz_poly_scalar_mul_si(fmpz_poly_t poly1,
0272                              const fmpz_poly_t poly2, slong x);
0273
0274 void fmpz_poly_scalar_mul_fmpz(fmpz_poly_t poly1,
0275                                const fmpz_poly_t poly2, const fmpz_t x);
0276
0277 void fmpz_poly_scalar_addmul_fmpz(fmpz_poly_t poly1,
0278                                    const fmpz_poly_t poly2, const fmpz_t x);
0279
0280 void fmpz_poly_scalar_addmul_si(fmpz_poly_t poly1,
0281                                    const fmpz_poly_t poly2, slong x);
0282
0283 void fmpz_poly_scalar_addmul_ui(fmpz_poly_t poly1,
0284                                    const fmpz_poly_t poly2, ulong x);
0285
0286 void fmpz_poly_scalar_submul_fmpz(fmpz_poly_t poly1,
0287                                    const fmpz_poly_t poly2, const fmpz_t x);
0288
0289 void fmpz_poly_scalar_fdiv_ui(fmpz_poly_t poly1,
0290                               const fmpz_poly_t poly2, ulong x);
0291
0292 void fmpz_poly_scalar_fdiv_si(fmpz_poly_t poly1,
0293                               const fmpz_poly_t poly2, slong x);
0294
0295 void fmpz_poly_scalar_fdiv_fmpz(fmpz_poly_t poly1,
0296                                 const fmpz_poly_t poly2, const fmpz_t x);
0297
0298 void fmpz_poly_scalar_tdiv_ui(fmpz_poly_t poly1,
0299                               const fmpz_poly_t poly2, ulong x);
0300
0301 void fmpz_poly_scalar_tdiv_si(fmpz_poly_t poly1,
0302                               const fmpz_poly_t poly2, slong x);
0303
0304 void fmpz_poly_scalar_tdiv_fmpz(fmpz_poly_t poly1,
0305                                 const fmpz_poly_t poly2, const fmpz_t x);
0306
0307 void fmpz_poly_scalar_divexact_ui(fmpz_poly_t poly1,
0308                                   const fmpz_poly_t poly2, ulong x);
0309
0310 void fmpz_poly_scalar_divexact_si(fmpz_poly_t poly1,
0311                                   const fmpz_poly_t poly2, slong x);
0312
0313 void fmpz_poly_scalar_divexact_fmpz(fmpz_poly_t poly1,
0314                                     const fmpz_poly_t poly2, const fmpz_t x);
0315
0316 void fmpz_poly_scalar_fdiv_2exp(fmpz_poly_t poly1, const fmpz_poly_t poly2,
0317                            ulong exp);
0318
0319 void fmpz_poly_scalar_tdiv_2exp(fmpz_poly_t poly1, const fmpz_poly_t poly2,
0320                            ulong exp);
0321
0322 void fmpz_poly_scalar_mul_2exp(fmpz_poly_t poly1, const fmpz_poly_t poly2,
0323                            ulong exp);
0324
0325 void fmpz_poly_scalar_mod_fmpz(fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t x);
0326 void fmpz_poly_scalar_smod_fmpz(fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t x);
0327
0328 slong _fmpz_poly_remove_content_2exp(fmpz * pol, slong len);
0329
0330 void _fmpz_poly_scale_2exp(fmpz * pol, slong len, slong k);
0331
0332 /*  Bit packing  *************************************************************/
0333
0334 void _fmpz_poly_bit_pack(nn_ptr arr, const fmpz * poly, slong len, flint_bitcnt_t bit_size, int negate);
0335 void fmpz_poly_bit_pack(fmpz_t f, const fmpz_poly_t poly, flint_bitcnt_t bit_size);
0336
0337 int _fmpz_poly_bit_unpack(fmpz * poly, slong nlo, slong nhi, nn_srcptr arr, flint_bitcnt_t bit_size, int negate);
0338 void _fmpz_poly_bit_unpack_unsigned(fmpz * poly, slong nlo, slong nhi, nn_srcptr arr, flint_bitcnt_t bit_size);
0339 void fmpz_poly_bit_unpack(fmpz_poly_t poly, const fmpz_t f, flint_bitcnt_t bit_size);
0340 void fmpz_poly_bit_unpack_unsigned(fmpz_poly_t poly, const fmpz_t f, flint_bitcnt_t bit_size);
0341
0342
0343 /*  Multiplication  **********************************************************/
0344
0345 void _fmpz_poly_mul_classical(fmpz * res, const fmpz * poly1, slong len1,
0346                                              const fmpz * poly2, slong len2);
0347
0348 void fmpz_poly_mul_classical(fmpz_poly_t res,
0349                           const fmpz_poly_t poly1, const fmpz_poly_t poly2);
0350
0351 void _fmpz_poly_mullow_classical(fmpz * res, const fmpz * poly1, slong len1,
0352                                      const fmpz * poly2, slong len2, slong n);
0353
0354 void fmpz_poly_mullow_classical(fmpz_poly_t res, const fmpz_poly_t poly1,
0355                                            const fmpz_poly_t poly2, slong n);
0356
0357 void _fmpz_poly_mulhigh_classical(fmpz * res, const fmpz * poly1,
0358                       slong len1, const fmpz * poly2, slong len2, slong start);
0359
0360 void fmpz_poly_mulhigh_classical(fmpz_poly_t res,
0361               const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong start);
0362
0363 void _fmpz_poly_mulmid_classical(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2, slong nlo, slong nhi);
0364 void fmpz_poly_mulmid_classical(fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong nlo, slong nhi);
0365 void _fmpz_poly_mulmid_SS(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2, slong nlo, slong nhi);
0366 void fmpz_poly_mulmid_SS(fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong nlo, slong nhi);
0367 void _fmpz_poly_mulmid_KS(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2, slong nlo, slong nhi);
0368 void fmpz_poly_mulmid_KS(fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong nlo, slong nhi);
0369 void _fmpz_poly_mulmid(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2, slong nlo, slong nhi);
0370 void fmpz_poly_mulmid(fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong nlo, slong nhi);
0371
0372 void fmpz_poly_mul_karatsuba(fmpz_poly_t res,
0373                           const fmpz_poly_t poly1, const fmpz_poly_t poly2);
0374
0375 void _fmpz_poly_mul_karatsuba(fmpz * res, const fmpz * poly1,
0376                                   slong len1, const fmpz * poly2, slong len2);
0377
0378 void _fmpz_poly_mullow_karatsuba_n(fmpz * res, const fmpz * poly1,
0379                                                 const fmpz * poly2, slong n);
0380
0381 void _fmpz_poly_mullow_karatsuba(fmpz * res, const fmpz * poly1, slong len1,
0382                               const fmpz * poly2, slong len2, slong n);
0383
0384 void fmpz_poly_mullow_karatsuba_n(fmpz_poly_t res,
0385                   const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
0386
0387 void _fmpz_poly_mulhigh_karatsuba_n(fmpz * res, const fmpz * poly1,
0388                                               const fmpz * poly2, slong len);
0389
0390 void fmpz_poly_mulhigh_karatsuba_n(fmpz_poly_t res,
0391              const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong length);
0392
0393 void _fmpz_poly_mul_KS(fmpz * res, const fmpz * poly1, slong len1,
0394                                              const fmpz * poly2, slong len2);
0395
0396 void fmpz_poly_mul_KS(fmpz_poly_t res,
0397                           const fmpz_poly_t poly1, const fmpz_poly_t poly2);
0398
0399 void _fmpz_poly_mullow_KS(fmpz * res, const fmpz * poly1, slong len1,
0400                                      const fmpz * poly2, slong len2, slong n);
0401
0402 void fmpz_poly_mullow_KS(fmpz_poly_t res, const fmpz_poly_t poly1,
0403                                            const fmpz_poly_t poly2, slong n);
0404
0405 void _fmpz_poly_mul_SS(fmpz * res, const fmpz * poly1, slong len1,
0406                                          const fmpz * poly2, slong len2);
0407
0408 void fmpz_poly_mul_SS(fmpz_poly_t res,
0409                           const fmpz_poly_t poly1, const fmpz_poly_t poly2);
0410
0411 void _fmpz_poly_mullow_SS(fmpz * res, const fmpz * poly1, slong len1,
0412                                      const fmpz * poly2, slong len2, slong n);
0413
0414 void fmpz_poly_mullow_SS(fmpz_poly_t res,
0415                   const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
0416
0417 void _fmpz_poly_mul(fmpz * res, const fmpz * poly1,
0418                                   slong len1, const fmpz * poly2, slong len2);
0419
0420 void fmpz_poly_mul(fmpz_poly_t res,
0421                           const fmpz_poly_t poly1, const fmpz_poly_t poly2);
0422
0423 void _fmpz_poly_mullow(fmpz * res, const fmpz * poly1, slong len1,
0424                                      const fmpz * poly2, slong len2, slong n);
0425
0426 void fmpz_poly_mullow(fmpz_poly_t res,
0427                   const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
0428
0429 void fmpz_poly_mulhigh_n(fmpz_poly_t res,
0430                   const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
0431
0432 void _fmpz_poly_mulhigh(fmpz * res,
0433                           const fmpz * poly1, slong len1,
0434                                    const fmpz * poly2, slong len2, slong start);
0435
0436 /* FFT precached multiplication **********************************************/
0437
0438 void fmpz_poly_mul_SS_precache_init(fmpz_poly_mul_precache_t pre,
0439                              slong len1, slong bits1, const fmpz_poly_t poly2);
0440
0441 void fmpz_poly_mul_precache_clear(fmpz_poly_mul_precache_t pre);
0442
0443 void _fmpz_poly_mullow_SS_precache(fmpz * output,
0444    const fmpz * input1, slong len1, fmpz_poly_mul_precache_t pre, slong trunc);
0445
0446 void fmpz_poly_mullow_SS_precache(fmpz_poly_t res,
0447                const fmpz_poly_t poly1, fmpz_poly_mul_precache_t pre, slong n);
0448
0449 FMPZ_POLY_INLINE void fmpz_poly_mul_SS_precache(fmpz_poly_t res,
0450                          const fmpz_poly_t poly1, fmpz_poly_mul_precache_t pre)
0451 {
0452     fmpz_poly_mullow_SS_precache(res, poly1, pre,
0453                           FLINT_MAX(poly1->length + pre->len2 - 1, 0));
0454 }
0455
0456 /* Squaring ******************************************************************/
0457
0458 void _fmpz_poly_sqr_KS(fmpz * rop, const fmpz * op, slong len);
0459
0460 void fmpz_poly_sqr_KS(fmpz_poly_t rop, const fmpz_poly_t op);
0461
0462 void fmpz_poly_sqr_karatsuba(fmpz_poly_t rop, const fmpz_poly_t op);
0463
0464 void _fmpz_poly_sqr_karatsuba(fmpz * rop, const fmpz * op, slong len);
0465
0466 void _fmpz_poly_sqr_classical(fmpz * rop, const fmpz * op, slong len);
0467
0468 void fmpz_poly_sqr_classical(fmpz_poly_t rop, const fmpz_poly_t op);
0469
0470 void _fmpz_poly_sqr(fmpz * rop, const fmpz * op, slong len);
0471
0472 void fmpz_poly_sqr(fmpz_poly_t rop, const fmpz_poly_t op);
0473
0474 void _fmpz_poly_sqrlow_KS(fmpz * res, const fmpz * poly, slong len, slong n);
0475
0476 void fmpz_poly_sqrlow_KS(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
0477
0478 void _fmpz_poly_sqrlow_karatsuba_n(fmpz * res, const fmpz * poly, slong n);
0479
0480 void _fmpz_poly_sqrlow_karatsuba(fmpz * res, const fmpz * poly, slong len, slong n);
0481
0482 void fmpz_poly_sqrlow_karatsuba_n(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
0483
0484 void _fmpz_poly_sqrlow_classical(fmpz * res, const fmpz * poly, slong len, slong n);
0485
0486 void fmpz_poly_sqrlow_classical(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
0487
0488 void _fmpz_poly_sqrlow(fmpz * res, const fmpz * poly, slong len, slong n);
0489
0490 void fmpz_poly_sqrlow(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
0491
0492 /*  Powering  ****************************************************************/
0493
0494 void _fmpz_poly_pow_multinomial(fmpz * res, const fmpz * poly, slong len, ulong e);
0495
0496 void fmpz_poly_pow_multinomial(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
0497
0498 void _fmpz_poly_pow_binomial(fmpz * res, const fmpz * poly, ulong e);
0499
0500 void fmpz_poly_pow_binomial(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
0501
0502 void _fmpz_poly_pow_binexp(fmpz * res, const fmpz * poly, slong len, ulong e);
0503
0504 void fmpz_poly_pow_binexp(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
0505
0506 void _fmpz_poly_pow_addchains(fmpz * res, const fmpz * poly, slong len, const int * a, int n);
0507
0508 void fmpz_poly_pow_addchains(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
0509
0510 void _fmpz_poly_pow_small(fmpz * res, const fmpz * poly, slong len, ulong e);
0511
0512 void _fmpz_poly_pow(fmpz * res, const fmpz * poly, slong len, ulong e);
0513
0514 void fmpz_poly_pow(fmpz_poly_t res, const fmpz_poly_t poly, ulong e);
0515
0516 void _fmpz_poly_pow_trunc(fmpz * res, const fmpz * poly, ulong e, slong n);
0517
0518 void
0519 fmpz_poly_pow_trunc(fmpz_poly_t res, const fmpz_poly_t poly, ulong e, slong n);
0520
0521 /*  Shifting  ****************************************************************/
0522
0523 void _fmpz_poly_shift_left(fmpz * res, const fmpz * poly, slong len, slong n);
0524
0525 void _fmpz_poly_shift_right(fmpz * res, const fmpz * poly, slong len, slong n);
0526
0527 void fmpz_poly_shift_left(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
0528
0529 void fmpz_poly_shift_right(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
0530
0531 /*  Norms  *******************************************************************/
0532
0533 void _fmpz_poly_2norm(fmpz_t res, const fmpz * poly, slong len);
0534
0535 void fmpz_poly_2norm(fmpz_t res, const fmpz_poly_t poly);
0536
0537 flint_bitcnt_t _fmpz_poly_2norm_normalised_bits(const fmpz * poly, slong len);
0538
0539 ulong fmpz_poly_max_limbs(const fmpz_poly_t poly);
0540 slong fmpz_poly_max_bits(const fmpz_poly_t poly);
0541 void fmpz_poly_height(fmpz_t res, const fmpz_poly_t poly);
0542 slong _fmpz_poly_hamming_weight(const fmpz * a, slong len);
0543
0544 /*  Greatest common divisor  *************************************************/
0545
0546 void _fmpz_poly_gcd_subresultant(fmpz * res, const fmpz * poly1, slong len1,
0547                                               const fmpz * poly2, slong len2);
0548
0549 void fmpz_poly_gcd_subresultant(fmpz_poly_t res, const fmpz_poly_t poly1,
0550                                                     const fmpz_poly_t poly2);
0551
0552 int _fmpz_poly_gcd_heuristic(fmpz * res, const fmpz * poly1, slong len1,
0553                                               const fmpz * poly2, slong len2);
0554
0555 int fmpz_poly_gcd_heuristic(fmpz_poly_t res,
0556                            const fmpz_poly_t poly1, const fmpz_poly_t poly2);
0557
0558 void _fmpz_poly_gcd_modular(fmpz * res, const fmpz * poly1, slong len1,
0559                                               const fmpz * poly2, slong len2);
0560
0561 void fmpz_poly_gcd_modular(fmpz_poly_t res,
0562                            const fmpz_poly_t poly1, const fmpz_poly_t poly2);
0563
0564 void _fmpz_poly_gcd(fmpz * res, const fmpz * poly1, slong len1,
0565                                                const fmpz * poly2, slong len2);
0566
0567 void fmpz_poly_gcd(fmpz_poly_t res, const fmpz_poly_t poly1,
0568                                                       const fmpz_poly_t poly2);
0569
0570 void _fmpz_poly_lcm(fmpz * res, const fmpz * poly1, slong len1,
0571                                                const fmpz * poly2, slong len2);
0572
0573 void fmpz_poly_lcm(fmpz_poly_t res, const fmpz_poly_t poly1,
0574                                                       const fmpz_poly_t poly2);
0575
0576 void _fmpz_poly_resultant_euclidean(fmpz_t res, const fmpz * poly1, slong len1,
0577                                                const fmpz * poly2, slong len2);
0578
0579 void fmpz_poly_resultant_euclidean(fmpz_t res, const fmpz_poly_t poly1,
0580                                                       const fmpz_poly_t poly2);
0581
0582 void _fmpz_poly_resultant_modular(fmpz_t res, const fmpz * poly1, slong len1,
0583                                                const fmpz * poly2, slong len2);
0584
0585 void fmpz_poly_resultant_modular(fmpz_t res, const fmpz_poly_t poly1,
0586                                                       const fmpz_poly_t poly2);
0587
0588 void _fmpz_poly_resultant(fmpz_t res, const fmpz * poly1, slong len1,
0589                                                const fmpz * poly2, slong len2);
0590
0591 void fmpz_poly_resultant(fmpz_t res, const fmpz_poly_t poly1,
0592                                                       const fmpz_poly_t poly2);
0593
0594 void _fmpz_poly_resultant_modular_div(fmpz_t res,
0595        const fmpz * poly1, slong len1,
0596        const fmpz * poly2, slong len2, const fmpz_t divisor, slong nbits);
0597
0598 void fmpz_poly_resultant_modular_div(fmpz_t res,
0599                const fmpz_poly_t poly1, const fmpz_poly_t poly2,
0600                const fmpz_t divisor, slong nbits);
0601
0602 void _fmpz_poly_xgcd_modular(fmpz_t r, fmpz * s, fmpz * t,
0603                const fmpz * poly1, slong len1, const fmpz * poly2, slong len2);
0604
0605 void fmpz_poly_xgcd_modular(fmpz_t r, fmpz_poly_t s, fmpz_poly_t t,
0606                              const fmpz_poly_t poly1, const fmpz_poly_t poly2);
0607
0608 FMPZ_POLY_INLINE
0609 void _fmpz_poly_xgcd(fmpz_t r, fmpz * s, fmpz * t,
0610                 const fmpz * poly1, slong len1, const fmpz * poly2, slong len2)
0611 {
0612     _fmpz_poly_xgcd_modular(r, s, t, poly1, len1, poly2, len2);
0613 }
0614
0615 FMPZ_POLY_INLINE
0616 void fmpz_poly_xgcd(fmpz_t r, fmpz_poly_t s, fmpz_poly_t t,
0617                             const fmpz_poly_t poly1, const fmpz_poly_t poly2)
0618 {
0619     fmpz_poly_xgcd_modular(r, s, t, poly1, poly2);
0620 }
0621
0622 void fmpz_poly_squarefree_part(fmpz_poly_t res, const fmpz_poly_t poly);
0623
0624 /*  Discriminant  ********************************************************/
0625
0626 void _fmpz_poly_discriminant(fmpz_t res, const fmpz * poly, slong len);
0627
0628 void fmpz_poly_discriminant(fmpz_t res, const fmpz_poly_t poly);
0629
0630 /*  Gaussian content  ********************************************************/
0631
0632 void _fmpz_poly_content(fmpz_t res, const fmpz * poly, slong len);
0633
0634 void fmpz_poly_content(fmpz_t res, const fmpz_poly_t poly);
0635
0636 void _fmpz_poly_primitive_part(fmpz * res, const fmpz * poly, slong len);
0637
0638 void fmpz_poly_primitive_part(fmpz_poly_t res, const fmpz_poly_t poly);
0639
0640 /*  Square-free  *************************************************************/
0641
0642 int _fmpz_poly_is_squarefree(const fmpz * poly, slong len);
0643
0644 int fmpz_poly_is_squarefree(const fmpz_poly_t poly);
0645
0646 /*  Euclidean division  ******************************************************/
0647
0648 int _fmpz_poly_divrem_basecase(fmpz * Q, fmpz * R, const fmpz * A,
0649                             slong lenA, const fmpz * B, slong lenB, int exact);
0650
0651 void fmpz_poly_divrem_basecase(fmpz_poly_t Q, fmpz_poly_t R,
0652                                    const fmpz_poly_t A, const fmpz_poly_t B);
0653
0654 int _fmpz_poly_divrem_divconquer_recursive(fmpz * Q, fmpz * BQ,
0655               fmpz * W, const fmpz * A, const fmpz * B, slong lenB, int exact);
0656
0657 int _fmpz_poly_divrem_divconquer(fmpz * Q, fmpz * R,
0658             const fmpz * A, slong lenA, const fmpz * B, slong lenB, int exact);
0659
0660 void fmpz_poly_divrem_divconquer(fmpz_poly_t Q, fmpz_poly_t R,
0661                                      const fmpz_poly_t A, const fmpz_poly_t B);
0662
0663 int _fmpz_poly_divrem(fmpz * Q, fmpz * R, const fmpz * A, slong lenA,
0664                                         const fmpz * B, slong lenB, int exact);
0665
0666 void fmpz_poly_divrem(fmpz_poly_t Q, fmpz_poly_t R,
0667                                      const fmpz_poly_t A, const fmpz_poly_t B);
0668
0669 int _fmpz_poly_div_basecase(fmpz * Q, fmpz * R, const fmpz * A,
0670                             slong lenA, const fmpz * B, slong lenB, int exact);
0671
0672 void fmpz_poly_div_basecase(fmpz_poly_t Q,
0673                                      const fmpz_poly_t A, const fmpz_poly_t B);
0674
0675 int _fmpz_poly_divremlow_divconquer_recursive(fmpz * Q, fmpz * QB,
0676                         const fmpz * A, const fmpz * B, slong lenB, int exact);
0677
0678 int _fmpz_poly_div_divconquer_recursive(fmpz * Q, fmpz * temp,
0679                         const fmpz * A, const fmpz * B, slong lenB, int exact);
0680
0681 int _fmpz_poly_div_divconquer(fmpz * Q, const fmpz * A, slong lenA,
0682                                         const fmpz * B, slong lenB, int exact);
0683
0684 void fmpz_poly_div_divconquer(fmpz_poly_t Q,
0685                                      const fmpz_poly_t A, const fmpz_poly_t B);
0686
0687 int _fmpz_poly_div(fmpz * Q, const fmpz * A, slong lenA,
0688                                         const fmpz * B, slong lenB, int exact);
0689
0690 void fmpz_poly_div(fmpz_poly_t Q, const fmpz_poly_t A,
0691                                                           const fmpz_poly_t B);
0692
0693 void _fmpz_poly_preinvert(fmpz * B_inv, const fmpz * B, slong n);
0694
0695 void fmpz_poly_preinvert(fmpz_poly_t B_inv, const fmpz_poly_t B);
0696
0697 void _fmpz_poly_div_preinv(fmpz * Q, const fmpz * A, slong len1,
0698                                const fmpz * B, const fmpz * B_inv, slong len2);
0699
0700 void fmpz_poly_div_preinv(fmpz_poly_t Q, const fmpz_poly_t A,
0701                                  const fmpz_poly_t B, const fmpz_poly_t B_inv);
0702
0703 void _fmpz_poly_divrem_preinv(fmpz * Q, fmpz * A, slong len1,
0704                                const fmpz * B, const fmpz * B_inv, slong len2);
0705
0706 void fmpz_poly_divrem_preinv(fmpz_poly_t Q, fmpz_poly_t R,
0707             const fmpz_poly_t A, const fmpz_poly_t B, const fmpz_poly_t B_inv);
0708
0709 void _fmpz_poly_divexact(fmpz * Q, const fmpz * A, slong lenA, const fmpz * B, slong lenB);
0710 void fmpz_poly_divexact(fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B);
0711
0712 fmpz ** _fmpz_poly_powers_precompute(const fmpz * B, slong len);
0713
0714 void fmpz_poly_powers_precompute(fmpz_poly_powers_precomp_t pinv,
0715                                                              fmpz_poly_t poly);
0716
0717 void _fmpz_poly_powers_clear(fmpz ** powers, slong len);
0718
0719 void fmpz_poly_powers_clear(fmpz_poly_powers_precomp_t pinv);
0720
0721 void _fmpz_poly_rem_powers_precomp(fmpz * A, slong m,
0722                                 const fmpz * B, slong n, fmpz ** const powers);
0723
0724 void fmpz_poly_rem_powers_precomp(fmpz_poly_t R,
0725                              const fmpz_poly_t A, const fmpz_poly_t B,
0726                                        const fmpz_poly_powers_precomp_t B_inv);
0727
0728 void _fmpz_poly_rem_basecase(fmpz * Q, const fmpz * A, slong lenA,
0729                                                    const fmpz * B, slong lenB);
0730
0731 void fmpz_poly_rem_basecase(fmpz_poly_t R,
0732                                      const fmpz_poly_t A, const fmpz_poly_t B);
0733
0734 void _fmpz_poly_rem(fmpz * R, const fmpz * A, slong lenA,
0735                               const fmpz * B, slong lenB);
0736
0737 void fmpz_poly_rem(fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B);
0738
0739 void fmpz_poly_div_root_fmpz(fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_t c);
0740
0741 void _fmpz_poly_div_root_fmpz(fmpz * Q, const fmpz * A, slong len, const fmpz_t c);
0742
0743 void fmpz_poly_divexact_root_fmpq(fmpz_poly_t Q, const fmpz_poly_t A, const fmpq_t c);
0744
0745 void _fmpz_poly_divexact_root_fmpq(fmpz * Q, const fmpz * A, slong len, const fmpq_t x);
0746
0747 /*  Power series division  ***************************************************/
0748
0749 void _fmpz_poly_inv_series_basecase(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
0750
0751 void fmpz_poly_inv_series_basecase(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
0752
0753 void _fmpz_poly_inv_series_newton(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
0754
0755 void fmpz_poly_inv_series_newton(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
0756
0757 void _fmpz_poly_inv_series(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
0758
0759 void fmpz_poly_inv_series(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
0760
0761 void _fmpz_poly_div_series_basecase(fmpz * Q, const fmpz * A, slong Alen,
0762     const fmpz * B, slong Blen, slong n);
0763
0764 void _fmpz_poly_div_series_divconquer(fmpz * Q, const fmpz * A, slong Alen,
0765     const fmpz * B, slong Blen, slong n);
0766
0767 void _fmpz_poly_div_series(fmpz * Q, const fmpz * A, slong Alen,
0768     const fmpz * B, slong Blen, slong n);
0769
0770 void fmpz_poly_div_series_basecase(fmpz_poly_t Q,
0771             const fmpz_poly_t A, const fmpz_poly_t B, slong n);
0772
0773 void fmpz_poly_div_series_divconquer(fmpz_poly_t Q,
0774             const fmpz_poly_t A, const fmpz_poly_t B, slong n);
0775
0776 void fmpz_poly_div_series(fmpz_poly_t Q, const fmpz_poly_t A,
0777                                          const fmpz_poly_t B, slong n);
0778
0779 /*  Divisibility testing  ***************************************************/
0780
0781 int _fmpz_poly_divides(fmpz * q, const fmpz * a,
0782                                        slong len1, const fmpz * b, slong len2);
0783
0784 int fmpz_poly_divides(fmpz_poly_t q,
0785                              const fmpz_poly_t a, const fmpz_poly_t b);
0786
0787 slong fmpz_poly_remove(fmpz_poly_t res, const fmpz_poly_t poly1,
0788                                               const fmpz_poly_t poly2);
0789
0790 /*  Pseudo division  *********************************************************/
0791
0792 #ifdef FMPZ_H
0793 void _fmpz_poly_pseudo_divrem_basecase(fmpz * Q, fmpz * R,
0794                    ulong * d, const fmpz * A, slong A_len,
0795                         const fmpz * B, slong B_len, const fmpz_preinvn_t inv);
0796
0797 void _fmpz_poly_pseudo_divrem_divconquer(fmpz * Q, fmpz * R,
0798                     ulong * d, const fmpz * A, slong lenA,
0799                          const fmpz * B, slong lenB, const fmpz_preinvn_t inv);
0800
0801 FMPZ_POLY_INLINE
0802 void _fmpz_poly_pseudo_divrem(fmpz * Q, fmpz * R,
0803                     ulong * d, const fmpz * A, slong A_len,
0804                          const fmpz * B, slong B_len, const fmpz_preinvn_t inv)
0805 {
0806     _fmpz_poly_pseudo_divrem_divconquer(Q, R, d, A, A_len, B, B_len, inv);
0807 }
0808
0809 void _fmpz_poly_pseudo_div(fmpz * Q, ulong * d, const fmpz * A,
0810              slong lenA, const fmpz * B, slong lenB, const fmpz_preinvn_t inv);
0811
0812 void _fmpz_poly_pseudo_rem(fmpz * R, ulong * d, const fmpz * A,
0813              slong lenA, const fmpz * B, slong lenB, const fmpz_preinvn_t inv);
0814 #endif
0815
0816 void fmpz_poly_pseudo_divrem_basecase(fmpz_poly_t Q, fmpz_poly_t R,
0817                           ulong * d, const fmpz_poly_t A, const fmpz_poly_t B);
0818
0819 void fmpz_poly_pseudo_divrem_divconquer(fmpz_poly_t Q, fmpz_poly_t R,
0820                           ulong * d, const fmpz_poly_t A, const fmpz_poly_t B);
0821
0822 void _fmpz_poly_pseudo_divrem_cohen(fmpz * Q, fmpz * R, const fmpz * A,
0823                                        slong lenA, const fmpz * B, slong lenB);
0824
0825 void fmpz_poly_pseudo_divrem_cohen(fmpz_poly_t Q, fmpz_poly_t R,
0826                                      const fmpz_poly_t A, const fmpz_poly_t B);
0827
0828 void _fmpz_poly_pseudo_rem_cohen(fmpz * R, const fmpz * A, slong lenA,
0829                                                    const fmpz * B, slong lenB);
0830
0831 void fmpz_poly_pseudo_rem_cohen(fmpz_poly_t R, const fmpz_poly_t A,
0832                                                           const fmpz_poly_t B);
0833
0834 FMPZ_POLY_INLINE
0835 void fmpz_poly_pseudo_divrem(fmpz_poly_t Q, fmpz_poly_t R,
0836                            ulong * d, const fmpz_poly_t A, const fmpz_poly_t B)
0837 {
0838     fmpz_poly_pseudo_divrem_divconquer(Q, R, d, A, B);
0839 }
0840
0841 void fmpz_poly_pseudo_div(fmpz_poly_t Q, ulong * d,
0842                                      const fmpz_poly_t A, const fmpz_poly_t B);
0843
0844 void fmpz_poly_pseudo_rem(fmpz_poly_t R, ulong * d,
0845                                      const fmpz_poly_t A, const fmpz_poly_t B);
0846
0847 void fmpz_poly_divlow_smodp(fmpz * res,
0848             const fmpz_poly_t f, const fmpz_poly_t g, const fmpz_t p, slong n);
0849
0850 void fmpz_poly_divhigh_smodp(fmpz * res,
0851             const fmpz_poly_t f, const fmpz_poly_t g, const fmpz_t p, slong n);
0852
0853 /*  Derivative  **************************************************************/
0854
0855 void _fmpz_poly_derivative(fmpz * rpoly, const fmpz * poly, slong len);
0856
0857 void fmpz_poly_derivative(fmpz_poly_t res, const fmpz_poly_t poly);
0858
0859 void _fmpz_poly_nth_derivative(fmpz * rpoly, const fmpz * poly, ulong n, slong len);
0860
0861 void fmpz_poly_nth_derivative(fmpz_poly_t res, const fmpz_poly_t poly, ulong n);
0862
0863 /*  Evaluation  **************************************************************/
0864
0865 void
0866 _fmpz_poly_evaluate_divconquer_fmpz(fmpz_t res, const fmpz * poly, slong len,
0867                                                 const fmpz_t a);
0868
0869 void fmpz_poly_evaluate_divconquer_fmpz(fmpz_t res, const fmpz_poly_t poly,
0870                                         const fmpz_t a);
0871
0872 void _fmpz_poly_evaluate_horner_fmpz(fmpz_t res, const fmpz * f, slong len,
0873                                                                const fmpz_t a);
0874
0875 void fmpz_poly_evaluate_horner_fmpz(fmpz_t res, const fmpz_poly_t f,
0876                                                                const fmpz_t a);
0877
0878 void _fmpz_poly_evaluate_fmpz(fmpz_t res, const fmpz * f, slong len, const fmpz_t a);
0879
0880 void fmpz_poly_evaluate_fmpz(fmpz_t res, const fmpz_poly_t f, const fmpz_t a);
0881
0882 void _fmpz_poly_evaluate_horner_fmpq(fmpz_t rnum, fmpz_t rden,
0883                                     const fmpz * f, slong len,
0884                                     const fmpz_t anum, const fmpz_t aden);
0885
0886 void fmpz_poly_evaluate_horner_fmpq(fmpq_t res, const fmpz_poly_t f,
0887                                                                const fmpq_t a);
0888
0889 void _fmpz_poly_evaluate_divconquer_fmpq(fmpz_t rnum, fmpz_t rden,
0890                                     const fmpz * f, slong len,
0891                                     const fmpz_t anum, const fmpz_t aden);
0892
0893 void fmpz_poly_evaluate_divconquer_fmpq(fmpq_t res,
0894                                           const fmpz_poly_t f, const fmpq_t a);
0895
0896 void _fmpz_poly_evaluate_fmpq(fmpz_t rnum, fmpz_t rden,
0897                                     const fmpz * f, slong len,
0898                                     const fmpz_t anum, const fmpz_t aden);
0899
0900 void fmpz_poly_evaluate_fmpq(fmpq_t res,
0901                                           const fmpz_poly_t f, const fmpq_t a);
0902
0903 ulong _fmpz_poly_evaluate_mod(const fmpz * poly, slong len,
0904                                      ulong a, ulong n, ulong ninv);
0905
0906 ulong fmpz_poly_evaluate_mod(const fmpz_poly_t poly, ulong a,
0907                                  ulong n);
0908
0909 double _fmpz_poly_evaluate_horner_d(const fmpz * poly, slong n,
0910                                                                      double d);
0911
0912 double fmpz_poly_evaluate_horner_d(const fmpz_poly_t poly, double d);
0913
0914 double _fmpz_poly_evaluate_horner_d_2exp(slong * exp,
0915                                          const fmpz * poly, slong n, double d);
0916
0917 double fmpz_poly_evaluate_horner_d_2exp(slong * exp,
0918                                              const fmpz_poly_t poly, double d);
0919
0920 double _fmpz_poly_evaluate_horner_d_2exp2(slong * exp, const fmpz * poly,
0921                                       slong n, double d, slong dexp);
0922
0923 double fmpz_poly_evaluate_horner_d_2exp2(slong * exp,
0924              const fmpz_poly_t poly, double d, slong dexp);
0925
0926 /*  Composition  *************************************************************/
0927
0928 void _fmpz_poly_compose_horner(fmpz * res, const fmpz * poly1, slong len1,
0929                                                 const fmpz * poly2, slong len2);
0930
0931 void fmpz_poly_compose_horner(fmpz_poly_t res, const fmpz_poly_t poly1,
0932                                                       const fmpz_poly_t poly2);
0933
0934 void _fmpz_poly_compose_divconquer(fmpz * res, const fmpz * poly1, slong len1,
0935                                                 const fmpz * poly2, slong len2);
0936
0937 void fmpz_poly_compose_divconquer(fmpz_poly_t res, const fmpz_poly_t poly1,
0938                                                       const fmpz_poly_t poly2);
0939
0940 void _fmpz_poly_compose(fmpz * res, const fmpz * poly1, slong len1,
0941                                                 const fmpz * poly2, slong len2);
0942
0943 void fmpz_poly_compose(fmpz_poly_t res, const fmpz_poly_t poly1,
0944                                                       const fmpz_poly_t poly2);
0945
0946 /*  Taylor shift  ************************************************************/
0947
0948 void _fmpz_poly_taylor_shift_horner(fmpz * poly, const fmpz_t c, slong n);
0949
0950 void fmpz_poly_taylor_shift_horner(fmpz_poly_t g, const fmpz_poly_t f,
0951     const fmpz_t c);
0952
0953 void _fmpz_poly_taylor_shift_divconquer(fmpz * poly, const fmpz_t c, slong n);
0954
0955 void fmpz_poly_taylor_shift_divconquer(fmpz_poly_t g, const fmpz_poly_t f,
0956     const fmpz_t c);
0957
0958 void _fmpz_poly_taylor_shift_multi_mod(fmpz * poly, const fmpz_t c, slong n);
0959
0960 FMPZ_POLY_INLINE
0961 void fmpz_poly_taylor_shift_multi_mod(fmpz_poly_t g, const fmpz_poly_t f, const fmpz_t c)
0962 {
0963     if (f != g)
0964         fmpz_poly_set(g, f);
0965     _fmpz_poly_taylor_shift_multi_mod(g->coeffs, c, g->length);
0966 }
0967
0968 void _fmpz_poly_taylor_shift(fmpz * poly, const fmpz_t c, slong n);
0969
0970 void fmpz_poly_taylor_shift(fmpz_poly_t g, const fmpz_poly_t f, const fmpz_t c);
0971
0972 /*  Power series composition and compositional inverse  **********************/
0973
0974 void _fmpz_poly_compose_series_brent_kung(fmpz * res, const fmpz * poly1, slong len1,
0975                                       const fmpz * poly2, slong len2, slong n);
0976
0977 void fmpz_poly_compose_series_brent_kung(fmpz_poly_t res,
0978                     const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
0979
0980 void _fmpz_poly_compose_series_horner(fmpz * res, const fmpz * poly1, slong len1,
0981                                       const fmpz * poly2, slong len2, slong n);
0982
0983 void fmpz_poly_compose_series_horner(fmpz_poly_t res,
0984                     const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
0985
0986 void _fmpz_poly_compose_series(fmpz * res, const fmpz * poly1, slong len1,
0987                                       const fmpz * poly2, slong len2, slong n);
0988
0989 void fmpz_poly_compose_series(fmpz_poly_t res,
0990                     const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n);
0991
0992 void _fmpz_poly_revert_series(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n);
0993 void fmpz_poly_revert_series(fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n);
0994
0995 /*  Square root  *************************************************************/
0996
0997 int _fmpz_poly_sqrtrem_classical(fmpz * res, fmpz * r,
0998                                                  const fmpz * poly, slong len);
0999
1000 int fmpz_poly_sqrtrem_classical(fmpz_poly_t b,
1001                                            fmpz_poly_t r, const fmpz_poly_t a);
1002
1003 int _fmpz_poly_sqrtrem_divconquer(fmpz * res, fmpz * r,
1004                                     const fmpz * poly, slong len, fmpz * temp);
1005
1006 int fmpz_poly_sqrtrem_divconquer(fmpz_poly_t b,
1007                                            fmpz_poly_t r, const fmpz_poly_t a);
1008
1009 int _fmpz_poly_sqrt_classical(fmpz * res, const fmpz * poly,
1010                                                          slong len, int exact);
1011
1012 int fmpz_poly_sqrt_classical(fmpz_poly_t b, const fmpz_poly_t a);
1013
1014 int _fmpz_poly_sqrt_divconquer(fmpz * res, const fmpz * poly,
1015                                                          slong len, int exact);
1016
1017 int fmpz_poly_sqrt_divconquer(fmpz_poly_t b, const fmpz_poly_t a);
1018
1019 int _fmpz_poly_sqrt_KS(fmpz *rop, const fmpz *op, slong len);
1020
1021 int fmpz_poly_sqrt_KS(fmpz_poly_t b, const fmpz_poly_t a);
1022
1023 int _fmpz_poly_sqrt(fmpz * res, const fmpz * poly, slong len);
1024
1025 int fmpz_poly_sqrt(fmpz_poly_t b, const fmpz_poly_t a);
1026
1027 int _fmpz_poly_sqrt_series(fmpz * res,
1028                                         const fmpz * poly, slong len, slong n);
1029
1030 int fmpz_poly_sqrt_series(fmpz_poly_t b,
1031                                                  const fmpz_poly_t a, slong n);
1032
1033 /* Power sums ****************************************************************/
1034
1035 void _fmpz_poly_power_sums_naive(fmpz * res, const fmpz * poly, slong len, slong n);
1036
1037 void fmpz_poly_power_sums_naive(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
1038
1039 void fmpz_poly_power_sums(fmpz_poly_t res, const fmpz_poly_t poly, slong n);
1040
1041 void _fmpz_poly_power_sums_to_poly(fmpz * res, const fmpz * poly, slong len);
1042
1043 void fmpz_poly_power_sums_to_poly(fmpz_poly_t res, const fmpz_poly_t Q);
1044
1045 /*  Signature  ***************************************************************/
1046
1047 void _fmpz_poly_signature(slong * r1, slong * r2, const fmpz * poly, slong len);
1048
1049 void fmpz_poly_signature(slong * r1, slong * r2, const fmpz_poly_t poly);
1050
1051 /*  Input and output  ********************************************************/
1052
1053 #ifdef FLINT_HAVE_FILE
1054 int _fmpz_poly_fprint(FILE * file, const fmpz * poly, slong len);
1055 int fmpz_poly_fprint(FILE * file, const fmpz_poly_t poly);
1056
1057 int _fmpz_poly_fprint_pretty(FILE * file, const fmpz * poly, slong len, const char * x);
1058 int fmpz_poly_fprint_pretty(FILE * file, const fmpz_poly_t poly, const char * x);
1059
1060 int fmpz_poly_fread(FILE * file, fmpz_poly_t poly);
1061
1062 int fmpz_poly_fread_pretty(FILE *file, fmpz_poly_t poly, char **x);
1063 #endif
1064
1065 int _fmpz_poly_print_pretty(const fmpz * poly, slong len, const char * x);
1066 int fmpz_poly_print_pretty(const fmpz_poly_t poly, const char * x);
1067 int _fmpz_poly_print(const fmpz * poly, slong n);
1068 int fmpz_poly_print(const fmpz_poly_t poly);
1069
1070 int fmpz_poly_read(fmpz_poly_t poly);
1071 int fmpz_poly_read_pretty(fmpz_poly_t poly, char **x);
1072
1073 void fmpz_poly_debug(const fmpz_poly_t poly);
1074
1075 /*  CRT  ********************************************************************/
1076
1077 void fmpz_poly_get_nmod_poly(nmod_poly_t res, const fmpz_poly_t poly);
1078
1079 void fmpz_poly_set_nmod_poly(fmpz_poly_t res, const nmod_poly_t poly);
1080
1081 void fmpz_poly_set_nmod_poly_unsigned(fmpz_poly_t res, const nmod_poly_t poly);
1082
1083 void
1084 _fmpz_poly_CRT_ui_precomp(fmpz * res, const fmpz * poly1, slong len1,
1085                const fmpz_t m1, nn_srcptr poly2, slong len2, ulong m2,
1086                 ulong m2inv, fmpz_t m1m2, ulong c, int sign);
1087
1088 void _fmpz_poly_CRT_ui(fmpz * res, const fmpz * poly1, slong len1,
1089                const fmpz_t m1, nn_srcptr poly2, slong len2, ulong m2,
1090                                                     ulong m2inv, int sign);
1091
1092 void fmpz_poly_CRT_ui(fmpz_poly_t res, const fmpz_poly_t poly1,
1093                                      const fmpz_t m1, const nmod_poly_t poly2,
1094                                         int sign);
1095
1096
1097 /* Products *****************************************************************/
1098
1099 void _fmpz_poly_product_roots_fmpz_vec(fmpz * poly,
1100                                         const fmpz * xs, slong n);
1101
1102 void fmpz_poly_product_roots_fmpz_vec(fmpz_poly_t poly,
1103                                         const fmpz * xs, slong n);
1104
1105 void _fmpz_poly_product_roots_fmpq_vec(fmpz * poly,
1106                                         const fmpq * xs, slong n);
1107
1108 void fmpz_poly_product_roots_fmpq_vec(fmpz_poly_t poly,
1109                                         const fmpq * xs, slong n);
1110
1111 fmpz ** _fmpz_poly_tree_alloc(slong len);
1112
1113 void _fmpz_poly_tree_free(fmpz ** tree, slong len);
1114
1115 void _fmpz_poly_tree_build_fmpq_vec(fmpz ** tree, const fmpq * roots, slong len);
1116
1117 /* Newton basis *************************************************************/
1118
1119 void _fmpz_poly_monomial_to_newton(fmpz * poly, const fmpz * roots, slong n);
1120
1121 void _fmpz_poly_newton_to_monomial(fmpz * poly, const fmpz * roots, slong n);
1122
1123 /* Subproduct trees *********************************************************/
1124
1125 fmpz ** _fmpz_poly_tree_alloc(slong len);
1126
1127 void _fmpz_poly_tree_free(fmpz ** tree, slong len);
1128
1129 void _fmpz_poly_tree_build_fmpq_vec(fmpz ** tree, const fmpq * roots, slong len);
1130
1131 /* Multipoint evaluation and interpolation *********************************/
1132
1133 void fmpz_poly_evaluate_fmpz_vec(fmpz * res, const fmpz_poly_t f,
1134                                 const fmpz * a, slong n);
1135
1136 void fmpz_poly_interpolate_fmpz_vec(fmpz_poly_t poly,
1137                                     const fmpz * xs, const fmpz * ys, slong n);
1138
1139 int _fmpz_poly_interpolate_newton(fmpz * poly, const fmpz * xs, const fmpz * ys, slong n);
1140 int fmpz_poly_interpolate_newton(fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n);
1141 int _fmpz_poly_interpolate_multi_mod(fmpz * poly, const fmpz * xs, const fmpz * ys, slong n);
1142 int fmpz_poly_interpolate_multi_mod(fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n);
1143 int _fmpz_poly_interpolate(fmpz * poly, const fmpz * xs, const fmpz * ys, slong n);
1144 int fmpz_poly_interpolate(fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n);
1145
1146 void _fmpz_poly_interpolate_exact_newton(fmpz * poly, const fmpz * xs, const fmpz * ys, slong n);
1147 void fmpz_poly_interpolate_exact_newton(fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n);
1148 void _fmpz_poly_interpolate_exact(fmpz * poly, const fmpz * xs, const fmpz * ys, slong n);
1149 void fmpz_poly_interpolate_exact(fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n);
1150
1151 /* Hensel lifting ************************************************************/
1152
1153 void fmpz_poly_hensel_build_tree(slong * link, fmpz_poly_t *v, fmpz_poly_t *w,
1154                                  const nmod_poly_factor_t fac);
1155
1156 void fmpz_poly_hensel_lift(fmpz_poly_t Gout, fmpz_poly_t Hout,
1157     fmpz_poly_t Aout, fmpz_poly_t Bout,
1158     const fmpz_poly_t f,
1159     const fmpz_poly_t g, const fmpz_poly_t h,
1160     const fmpz_poly_t a, const fmpz_poly_t b,
1161     const fmpz_t p, const fmpz_t p1);
1162
1163 void _fmpz_poly_hensel_lift_without_inverse(fmpz *G, fmpz *H,
1164     const fmpz *f, slong lenF,
1165     const fmpz *g, slong lenG, const fmpz *h, slong lenH,
1166     const fmpz *a, slong lenA, const fmpz *b, slong lenB,
1167     const fmpz_t p, const fmpz_t p1);
1168
1169 void fmpz_poly_hensel_lift_without_inverse(fmpz_poly_t Gout, fmpz_poly_t Hout,
1170     const fmpz_poly_t f, const fmpz_poly_t g, const fmpz_poly_t h,
1171     const fmpz_poly_t a, const fmpz_poly_t b,
1172     const fmpz_t p, const fmpz_t p1);
1173
1174 void _fmpz_poly_hensel_lift_only_inverse(fmpz *A, fmpz *B,
1175     const fmpz *G, slong lenG, const fmpz *H, slong lenH,
1176     const fmpz *a, slong lenA, const fmpz *b, slong lenB,
1177     const fmpz_t p, const fmpz_t p1);
1178
1179 void fmpz_poly_hensel_lift_only_inverse(fmpz_poly_t Aout, fmpz_poly_t Bout,
1180     const fmpz_poly_t G, const fmpz_poly_t H,
1181     const fmpz_poly_t a, const fmpz_poly_t b,
1182     const fmpz_t p, const fmpz_t p1);
1183
1184 void fmpz_poly_hensel_lift_tree_recursive(slong *link,
1185     fmpz_poly_t *v, fmpz_poly_t *w, fmpz_poly_t f, slong j, slong inv,
1186     const fmpz_t p0, const fmpz_t p1);
1187
1188 void fmpz_poly_hensel_lift_tree(slong *link, fmpz_poly_t *v, fmpz_poly_t *w,
1189     fmpz_poly_t f, slong r, const fmpz_t p, slong e0, slong e1, slong inv);
1190
1191 slong _fmpz_poly_hensel_start_lift(fmpz_poly_factor_t lifted_fac, slong *link,
1192     fmpz_poly_t *v, fmpz_poly_t *w, const fmpz_poly_t f,
1193     const nmod_poly_factor_t local_fac, slong target_exp);
1194
1195 slong _fmpz_poly_hensel_continue_lift(fmpz_poly_factor_t lifted_fac,
1196     slong *link, fmpz_poly_t *v, fmpz_poly_t *w, const fmpz_poly_t f,
1197     slong prev, slong curr, slong N, const fmpz_t p);
1198
1199 void fmpz_poly_hensel_lift_once(fmpz_poly_factor_t lifted_fac,
1200                                 const fmpz_poly_t f,
1201                                 const nmod_poly_factor_t local_fac, slong N);
1202
1203 /* Roots */
1204
1205 void _fmpz_poly_bound_roots(fmpz_t bound, const fmpz * poly, slong len);
1206 void fmpz_poly_bound_roots(fmpz_t bound, const fmpz_poly_t poly);
1207
1208 void _fmpz_poly_num_real_roots_sturm(slong * n_neg, slong * n_pos, const fmpz * pol, slong len);
1209 slong fmpz_poly_num_real_roots_sturm(const fmpz_poly_t poly);
1210 slong _fmpz_poly_num_real_roots_vca(const fmpz * pol, slong len);
1211 slong fmpz_poly_num_real_roots_vca(const fmpz_poly_t pol);
1212 slong _fmpz_poly_num_real_roots(const fmpz * pol, slong len);
1213 slong fmpz_poly_num_real_roots(const fmpz_poly_t poly);
1214
1215 slong fmpz_poly_num_real_roots_upper_bound(const fmpz_poly_t pol);
1216 slong _fmpz_poly_descartes_bound_0_1(const fmpz * p, slong len, slong bound);
1217
1218 int _fmpz_poly_has_real_root(const fmpz * p, slong len);
1219 int fmpz_poly_has_real_root(const fmpz_poly_t pol);
1220
1221 slong fmpz_poly_num_real_roots_0_1_sturm(const fmpz_poly_t pol);
1222 slong fmpz_poly_num_real_roots_0_1_vca(const fmpz_poly_t pol);
1223 slong fmpz_poly_num_real_roots_0_1(const fmpz_poly_t pol);
1224
1225 slong _fmpz_poly_positive_root_upper_bound_2exp_local_max(const fmpz * pol, slong len);
1226 slong _fmpz_poly_positive_root_upper_bound_2exp(const fmpz * pol, slong len);
1227 slong fmpz_poly_positive_root_upper_bound_2exp(const fmpz_poly_t pol);
1228
1229 void _fmpz_poly_isolate_real_roots_0_1_vca(fmpq * exact_roots, slong * n_exact,
1230         fmpz * c_array, slong * k_array, slong * n_intervals,
1231         const fmpz * pol, slong len);
1232 void fmpz_poly_isolate_real_roots(fmpq * exact_roots, slong * n_exact,
1233     fmpz * c_array, slong * k_array, slong * n_interval, const fmpz_poly_t pol);
1234 void fmpz_poly_isolate_positive_roots(fmpq * exact_roots, slong * n_exact,
1235     fmpz * c_array, slong * k_array, slong * n_interval, const fmpz_poly_t pol);
1236
1237 /* CLD bounds */
1238
1239 void fmpz_poly_CLD_bound(fmpz_t res, const fmpz_poly_t f, slong n);
1240
1241 /* Special polynomials */
1242
1243 void _fmpz_poly_cyclotomic(fmpz * a, ulong n, nn_ptr factors,
1244                                         slong num_factors, ulong phi);
1245 void fmpz_poly_cyclotomic(fmpz_poly_t poly, ulong n);
1246
1247 ulong _fmpz_poly_is_cyclotomic(const fmpz * poly, slong len);
1248
1249 ulong fmpz_poly_is_cyclotomic(const fmpz_poly_t poly);
1250
1251 void _fmpz_poly_cos_minpoly(fmpz * f, ulong n);
1252
1253 void fmpz_poly_cos_minpoly(fmpz_poly_t f, ulong n);
1254
1255 void _fmpz_poly_swinnerton_dyer(fmpz * T, ulong n);
1256
1257 void fmpz_poly_swinnerton_dyer(fmpz_poly_t poly, ulong n);
1258
1259 void _fmpz_poly_chebyshev_t(fmpz * coeffs, ulong n);
1260
1261 void fmpz_poly_chebyshev_t(fmpz_poly_t poly, ulong n);
1262
1263 void _fmpz_poly_chebyshev_u(fmpz * coeffs, ulong n);
1264
1265 void fmpz_poly_chebyshev_u(fmpz_poly_t poly, ulong n);
1266
1267 void _fmpz_poly_legendre_pt(fmpz * coeffs, ulong n);
1268
1269 void fmpz_poly_legendre_pt(fmpz_poly_t poly, ulong n);
1270
1271 void _fmpz_poly_hermite_h(fmpz * coeffs, ulong n);
1272
1273 void fmpz_poly_hermite_h(fmpz_poly_t poly, ulong n);
1274
1275 void _fmpz_poly_hermite_he(fmpz * coeffs, ulong n);
1276
1277 void fmpz_poly_hermite_he(fmpz_poly_t poly, ulong n);
1278
1279 void _fmpz_poly_fibonacci(fmpz * coeffs, ulong n);
1280
1281 void fmpz_poly_fibonacci(fmpz_poly_t poly, ulong n);
1282
1283 void _fmpz_poly_eta_qexp(fmpz * f, slong e, slong n);
1284
1285 void fmpz_poly_eta_qexp(fmpz_poly_t f, slong e, slong n);
1286
1287 void _fmpz_poly_theta_qexp(fmpz * f, slong e, slong n);
1288
1289 void fmpz_poly_theta_qexp(fmpz_poly_t f, slong e, slong n);
1290
1291 void fmpz_poly_eulerian_polynomial(fmpz_poly_t poly, ulong n);
1292
1293 /* Declare some old functions dead */
1294
1295 #define fmpz_poly_scalar_mul_mpz _Pragma("GCC error \"'fmpz_poly_scalar_mul_mpz' is deprecated. Use 'fmpz_poly_scalar_mul_fmpz' instead.\"")
1296 #define fmpz_poly_scalar_divexact_mpz _Pragma("GCC error \"'fmpz_poly_scalar_divexact_mpz' is deprecated. Use 'fmpz_poly_scalar_divexact_fmpz' instead.\"")
1297 #define fmpz_poly_scalar_fdiv_mpz _Pragma("GCC error \"'fmpz_poly_scalar_fdiv_mpz' is deprecated. Use 'fmpz_poly_scalar_fdiv_fmpz' instead.\"")
1298 #define fmpz_poly_set_coeff_mpz _Pragma("GCC error \"'fmpz_poly_set_coeff_mpz' is deprecated. Use 'fmpz_poly_set_coeff_fmpz' instead.\"")
1299 #define fmpz_poly_get_coeff_mpz _Pragma("GCC error \"'fmpz_poly_get_coeff_mpz' is deprecated. Use 'fmpz_poly_get_coeff_fmpz' instead.\"")
1300 #define fmpz_poly_set_mpz _Pragma("GCC error \"'fmpz_poly_set_mpz' is deprecated. Use 'fmpz_poly_set_fmpz' instead.\"")
1301 #define fmpz_poly_evaluate_mpq _Pragma("GCC error \"'fmpz_poly_evaluate_mpq' is deprecated. Use 'fmpz_poly_evaluate_fmpq' instead.\"")
1302
1303 #ifdef __cplusplus
1304 }
1305 #endif
1306
1307 #endif