include/flint/acb_poly.h

0001 /*
0002     Copyright (C) 2012 Fredrik Johansson
0003
0004     This file is part of FLINT.
0005
0006     FLINT is free software: you can redistribute it and/or modify it under
0007     the terms of the GNU Lesser General Public License (LGPL) as published
0008     by the Free Software Foundation; either version 3 of the License, or
0009     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0010 */
0011
0012 #ifndef ACB_POLY_H
0013 #define ACB_POLY_H
0014
0015 #ifdef ACB_POLY_INLINES_C
0016 #define ACB_POLY_INLINE
0017 #else
0018 #define ACB_POLY_INLINE static inline
0019 #endif
0020
0021 #include "fmpq_types.h"
0022 #include "acb.h"
0023
0024 #ifdef __cplusplus
0025 extern "C" {
0026 #endif
0027
0028 /* Memory management */
0029
0030 void acb_poly_init(acb_poly_t poly);
0031
0032 void acb_poly_init2(acb_poly_t poly, slong len);
0033
0034 void acb_poly_clear(acb_poly_t poly);
0035
0036 void acb_poly_fit_length(acb_poly_t poly, slong len);
0037
0038 void _acb_poly_set_length(acb_poly_t poly, slong len);
0039
0040 void _acb_poly_normalise(acb_poly_t poly);
0041
0042 ACB_POLY_INLINE void
0043 acb_poly_swap(acb_poly_t poly1, acb_poly_t poly2)
0044 {
0045     FLINT_SWAP(acb_poly_struct, *poly1, *poly2);
0046 }
0047
0048 ACB_POLY_INLINE slong acb_poly_length(const acb_poly_t poly)
0049 {
0050     return poly->length;
0051 }
0052
0053 ACB_POLY_INLINE slong acb_poly_degree(const acb_poly_t poly)
0054 {
0055     return poly->length - 1;
0056 }
0057
0058 slong acb_poly_valuation(const acb_poly_t poly);
0059
0060 ACB_POLY_INLINE int
0061 acb_poly_is_zero(const acb_poly_t z)
0062 {
0063     return acb_poly_length(z) == 0;
0064 }
0065
0066 ACB_POLY_INLINE int
0067 acb_poly_is_one(const acb_poly_t z)
0068 {
0069     return (acb_poly_length(z) == 1) && acb_is_one(z->coeffs);
0070 }
0071
0072 ACB_POLY_INLINE int
0073 acb_poly_is_x(const acb_poly_t z)
0074 {
0075     return (acb_poly_length(z) == 2) && acb_is_zero(z->coeffs)
0076         && acb_is_one(z->coeffs + 1);
0077 }
0078
0079 ACB_POLY_INLINE void acb_poly_zero(acb_poly_t poly)
0080 {
0081     poly->length = 0;
0082 }
0083
0084 ACB_POLY_INLINE void
0085 acb_poly_one(acb_poly_t poly)
0086 {
0087     acb_poly_fit_length(poly, 1);
0088     acb_one(poly->coeffs);
0089     _acb_poly_set_length(poly, 1);
0090 }
0091
0092 void acb_poly_set_coeff_si(acb_poly_t poly, slong n, slong x);
0093
0094 void acb_poly_set_coeff_acb(acb_poly_t poly, slong n, const acb_t x);
0095
0096 void acb_poly_get_coeff_acb(acb_t x, const acb_poly_t poly, slong n);
0097
0098 #define acb_poly_get_coeff_ptr(poly, n) \
0099     ((n) < (poly)->length ? (poly)->coeffs + (n) : NULL)
0100
0101 void _acb_poly_shift_right(acb_ptr res, acb_srcptr poly, slong len, slong n);
0102
0103 void acb_poly_shift_right(acb_poly_t res, const acb_poly_t poly, slong n);
0104
0105 void _acb_poly_shift_left(acb_ptr res, acb_srcptr poly, slong len, slong n);
0106
0107 void acb_poly_shift_left(acb_poly_t res, const acb_poly_t poly, slong n);
0108
0109 ACB_POLY_INLINE void
0110 acb_poly_truncate(acb_poly_t poly, slong newlen)
0111 {
0112     if (poly->length > newlen)
0113     {
0114         slong i;
0115         for (i = newlen; i < poly->length; i++)
0116             acb_zero(poly->coeffs + i);
0117         poly->length = newlen;
0118         _acb_poly_normalise(poly);
0119     }
0120 }
0121
0122 void _acb_poly_majorant(arb_ptr res, acb_srcptr vec, slong len, slong prec);
0123
0124 void acb_poly_majorant(arb_poly_t res, const acb_poly_t poly, slong prec);
0125
0126 #ifdef FLINT_HAVE_FILE
0127 void acb_poly_fprintd(FILE * file, const acb_poly_t poly, slong digits);
0128 #endif
0129
0130 void acb_poly_printd(const acb_poly_t poly, slong digits);
0131
0132 void _acb_poly_evaluate_horner(acb_t res, acb_srcptr f, slong len, const acb_t a, slong prec);
0133 void acb_poly_evaluate_horner(acb_t res, const acb_poly_t f, const acb_t a, slong prec);
0134
0135 void _acb_poly_evaluate_rectangular(acb_t y, acb_srcptr poly, slong len, const acb_t x, slong prec);
0136 void acb_poly_evaluate_rectangular(acb_t res, const acb_poly_t f, const acb_t a, slong prec);
0137
0138 void _acb_poly_evaluate(acb_t res, acb_srcptr f, slong len, const acb_t a, slong prec);
0139 void acb_poly_evaluate(acb_t res, const acb_poly_t f, const acb_t a, slong prec);
0140
0141 void _acb_poly_evaluate2_horner(acb_t y, acb_t z, acb_srcptr f, slong len, const acb_t x, slong prec);
0142 void acb_poly_evaluate2_horner(acb_t y, acb_t z, const acb_poly_t f, const acb_t x, slong prec);
0143
0144 void _acb_poly_evaluate2_rectangular(acb_t y, acb_t z, acb_srcptr f, slong len, const acb_t x, slong prec);
0145 void acb_poly_evaluate2_rectangular(acb_t y, acb_t z, const acb_poly_t f, const acb_t x, slong prec);
0146
0147 void _acb_poly_evaluate2(acb_t y, acb_t z, acb_srcptr f, slong len, const acb_t x, slong prec);
0148 void acb_poly_evaluate2(acb_t y, acb_t z, const acb_poly_t f, const acb_t x, slong prec);
0149
0150 void _acb_poly_derivative(acb_ptr res, acb_srcptr poly, slong len, slong prec);
0151
0152 void acb_poly_derivative(acb_poly_t res, const acb_poly_t poly, slong prec);
0153
0154 void _acb_poly_nth_derivative(acb_ptr res, acb_srcptr poly, ulong n, slong len, slong prec);
0155
0156 void acb_poly_nth_derivative(acb_poly_t res, const acb_poly_t poly, ulong n, slong prec);
0157
0158 void _acb_poly_integral(acb_ptr res, acb_srcptr poly, slong len, slong prec);
0159
0160 void acb_poly_integral(acb_poly_t res, const acb_poly_t poly, slong prec);
0161
0162 /* Transforms */
0163
0164 void acb_poly_borel_transform(acb_poly_t res, const acb_poly_t poly, slong prec);
0165
0166 void _acb_poly_borel_transform(acb_ptr res, acb_srcptr poly, slong len, slong prec);
0167
0168 void acb_poly_inv_borel_transform(acb_poly_t res, const acb_poly_t poly, slong prec);
0169
0170 void _acb_poly_inv_borel_transform(acb_ptr res, acb_srcptr poly, slong len, slong prec);
0171
0172 void _acb_poly_binomial_transform_basecase(acb_ptr b, acb_srcptr a, slong alen, slong len, slong prec);
0173
0174 void acb_poly_binomial_transform_basecase(acb_poly_t b, const acb_poly_t a, slong len, slong prec);
0175
0176 void _acb_poly_binomial_transform_convolution(acb_ptr b, acb_srcptr a, slong alen, slong len, slong prec);
0177
0178 void acb_poly_binomial_transform_convolution(acb_poly_t b, const acb_poly_t a, slong len, slong prec);
0179
0180 void _acb_poly_binomial_transform(acb_ptr b, acb_srcptr a, slong alen, slong len, slong prec);
0181
0182 void acb_poly_binomial_transform(acb_poly_t b, const acb_poly_t a, slong len, slong prec);
0183
0184 void _acb_poly_graeffe_transform(acb_ptr b, acb_srcptr a, slong len, slong prec);
0185
0186 void acb_poly_graeffe_transform(acb_poly_t b, const acb_poly_t a, slong prec);
0187
0188
0189
0190 void acb_poly_set(acb_poly_t dest, const acb_poly_t src);
0191
0192 void acb_poly_set_round(acb_poly_t dest, const acb_poly_t src, slong prec);
0193
0194 void acb_poly_set_trunc(acb_poly_t res, const acb_poly_t poly, slong n);
0195
0196 void acb_poly_set_trunc_round(acb_poly_t res, const acb_poly_t poly, slong n, slong prec);
0197
0198 void acb_poly_set_arb_poly(acb_poly_t poly, const arb_poly_t re);
0199
0200 void acb_poly_set2_arb_poly(acb_poly_t poly, const arb_poly_t re, const arb_poly_t im);
0201
0202 void acb_poly_set_fmpq_poly(acb_poly_t poly, const fmpq_poly_t re, slong prec);
0203
0204 void acb_poly_set2_fmpq_poly(acb_poly_t poly, const fmpq_poly_t re, const fmpq_poly_t im, slong prec);
0205
0206 void acb_poly_set_fmpz_poly(acb_poly_t poly, const fmpz_poly_t src, slong prec);
0207
0208 void acb_poly_set2_fmpz_poly(acb_poly_t poly, const fmpz_poly_t re, const fmpz_poly_t im, slong prec);
0209
0210 int acb_poly_get_unique_fmpz_poly(fmpz_poly_t res, const acb_poly_t src);
0211
0212 ACB_POLY_INLINE void
0213 acb_poly_set_acb(acb_poly_t poly, const acb_t c)
0214 {
0215     acb_poly_fit_length(poly, 1);
0216     acb_set(poly->coeffs, c);
0217     _acb_poly_set_length(poly, !acb_is_zero(poly->coeffs));
0218 }
0219
0220 void acb_poly_set_si(acb_poly_t poly, slong c);
0221
0222 void acb_poly_randtest(acb_poly_t poly, flint_rand_t state, slong len, slong prec, slong mag_bits);
0223
0224 int acb_poly_equal(const acb_poly_t A, const acb_poly_t B);
0225
0226 int acb_poly_contains_fmpz_poly(const acb_poly_t poly1, const fmpz_poly_t poly2);
0227
0228 int acb_poly_contains_fmpq_poly(const acb_poly_t poly1, const fmpq_poly_t poly2);
0229
0230 int _acb_poly_overlaps(acb_srcptr poly1, slong len1,
0231         acb_srcptr poly2, slong len2);
0232
0233 int acb_poly_overlaps(const acb_poly_t poly1, const acb_poly_t poly2);
0234
0235 int acb_poly_contains(const acb_poly_t poly1, const acb_poly_t poly2);
0236
0237 ACB_POLY_INLINE int
0238 acb_poly_is_real(const acb_poly_t poly)
0239 {
0240     return _acb_vec_is_real(poly->coeffs, poly->length);
0241 }
0242
0243 void _acb_poly_add(acb_ptr res, acb_srcptr poly1, slong len1,
0244     acb_srcptr poly2, slong len2, slong prec);
0245
0246 void acb_poly_add(acb_poly_t res, const acb_poly_t poly1,
0247               const acb_poly_t poly2, slong prec);
0248
0249 void acb_poly_add_si(acb_poly_t res, const acb_poly_t poly, slong c, slong prec);
0250
0251 void _acb_poly_sub(acb_ptr res, acb_srcptr poly1, slong len1,
0252     acb_srcptr poly2, slong len2, slong prec);
0253
0254 void acb_poly_sub(acb_poly_t res, const acb_poly_t poly1,
0255               const acb_poly_t poly2, slong prec);
0256
0257 void acb_poly_add_series(acb_poly_t res, const acb_poly_t poly1,
0258               const acb_poly_t poly2, slong len, slong prec);
0259
0260 void acb_poly_sub_series(acb_poly_t res, const acb_poly_t poly1,
0261               const acb_poly_t poly2, slong len, slong prec);
0262
0263 ACB_POLY_INLINE void
0264 acb_poly_neg(acb_poly_t res, const acb_poly_t poly)
0265 {
0266     acb_poly_fit_length(res, poly->length);
0267     _acb_vec_neg(res->coeffs, poly->coeffs, poly->length);
0268     _acb_poly_set_length(res, poly->length);
0269 }
0270
0271 ACB_POLY_INLINE void
0272 acb_poly_scalar_mul_2exp_si(acb_poly_t res, const acb_poly_t poly, slong c)
0273 {
0274     acb_poly_fit_length(res, poly->length);
0275     _acb_vec_scalar_mul_2exp_si(res->coeffs, poly->coeffs, poly->length, c);
0276     _acb_poly_set_length(res, poly->length);
0277 }
0278
0279 ACB_POLY_INLINE void
0280 acb_poly_scalar_mul(acb_poly_t res, const acb_poly_t poly, const acb_t c, slong prec)
0281 {
0282     acb_poly_fit_length(res, poly->length);
0283     _acb_vec_scalar_mul(res->coeffs, poly->coeffs, poly->length, c, prec);
0284     _acb_poly_set_length(res, poly->length);
0285     _acb_poly_normalise(res);
0286 }
0287
0288 ACB_POLY_INLINE void
0289 acb_poly_scalar_mul_si(acb_poly_t res, const acb_poly_t poly, slong c, slong prec)
0290 {
0291     acb_poly_fit_length(res, poly->length);
0292     _acb_vec_scalar_mul_si(res->coeffs, poly->coeffs, poly->length, c, prec);
0293     _acb_poly_set_length(res, poly->length);
0294     _acb_poly_normalise(res);
0295 }
0296
0297 ACB_POLY_INLINE void
0298 acb_poly_scalar_div(acb_poly_t res, const acb_poly_t poly, const acb_t c, slong prec)
0299 {
0300     acb_poly_fit_length(res, poly->length);
0301     _acb_vec_scalar_div(res->coeffs, poly->coeffs, poly->length, c, prec);
0302     _acb_poly_set_length(res, poly->length);
0303     _acb_poly_normalise(res);
0304 }
0305
0306 void acb_poly_mullow_classical(acb_poly_t res, const acb_poly_t poly1,
0307                                             const acb_poly_t poly2,
0308                                                 slong n, slong prec);
0309
0310 void _acb_poly_mullow_classical(acb_ptr res,
0311     acb_srcptr poly1, slong len1,
0312     acb_srcptr poly2, slong len2, slong n, slong prec);
0313
0314 void _acb_poly_mullow_transpose(acb_ptr res,
0315     acb_srcptr poly1, slong len1,
0316     acb_srcptr poly2, slong len2, slong n, slong prec);
0317
0318 void acb_poly_mullow_transpose(acb_poly_t res, const acb_poly_t poly1,
0319                                             const acb_poly_t poly2,
0320                                                 slong n, slong prec);
0321
0322 void _acb_poly_mullow_transpose_gauss(acb_ptr res,
0323     acb_srcptr poly1, slong len1,
0324     acb_srcptr poly2, slong len2, slong n, slong prec);
0325
0326 void acb_poly_mullow_transpose_gauss(acb_poly_t res, const acb_poly_t poly1,
0327                                             const acb_poly_t poly2,
0328                                                 slong n, slong prec);
0329
0330 void _acb_poly_mullow(acb_ptr res,
0331     acb_srcptr poly1, slong len1,
0332     acb_srcptr poly2, slong len2, slong n, slong prec);
0333
0334 void acb_poly_mullow(acb_poly_t res, const acb_poly_t poly1,
0335                                             const acb_poly_t poly2,
0336                                                 slong n, slong prec);
0337
0338 void _acb_poly_mul(acb_ptr C,
0339     acb_srcptr A, slong lenA,
0340     acb_srcptr B, slong lenB, slong prec);
0341
0342 void acb_poly_mul(acb_poly_t res, const acb_poly_t poly1,
0343               const acb_poly_t poly2, slong prec);
0344
0345 void _acb_poly_mulmid_transpose(acb_ptr z, acb_srcptr x, slong xlen, acb_srcptr y, slong ylen, slong nlo, slong nhi, slong prec);
0346 void acb_poly_mulmid_transpose(acb_poly_t res, const acb_poly_t poly1, const acb_poly_t poly2, slong nlo, slong nhi, slong prec);
0347 void _acb_poly_mulmid_classical(acb_ptr z, acb_srcptr x, slong xlen, acb_srcptr y, slong ylen, slong nlo, slong nhi, slong prec);
0348 void acb_poly_mulmid_classical(acb_poly_t res, const acb_poly_t poly1, const acb_poly_t poly2, slong nlo, slong nhi, slong prec);
0349 void _acb_poly_mulmid(acb_ptr z, acb_srcptr x, slong xlen, acb_srcptr y, slong ylen, slong nlo, slong nhi, slong prec);
0350 void acb_poly_mulmid(acb_poly_t res, const acb_poly_t poly1, const acb_poly_t poly2, slong nlo, slong nhi, slong prec);
0351
0352 ACB_POLY_INLINE void
0353 _acb_poly_mul_monic(acb_ptr res, acb_srcptr poly1, slong len1,
0354     acb_srcptr poly2, slong len2, slong prec)
0355 {
0356     if (len1 + len2 - 2 > 0)
0357         _acb_poly_mullow(res, poly1, len1, poly2, len2, len1 + len2 - 2, prec);
0358     acb_one(res + len1 + len2 - 2);
0359 }
0360
0361 void _acb_poly_inv_series(acb_ptr Qinv, acb_srcptr Q, slong Qlen, slong len, slong prec);
0362
0363 void acb_poly_inv_series(acb_poly_t Qinv, const acb_poly_t Q, slong n, slong prec);
0364
0365 void  _acb_poly_div_series(acb_ptr Q, acb_srcptr A, slong Alen,
0366     acb_srcptr B, slong Blen, slong n, slong prec);
0367
0368 void acb_poly_div_series(acb_poly_t Q, const acb_poly_t A, const acb_poly_t B, slong n, slong prec);
0369
0370 void _acb_poly_reverse(acb_ptr res, acb_srcptr poly, slong len, slong n);
0371
0372 void _acb_poly_div(acb_ptr Q,
0373     acb_srcptr A, slong lenA,
0374     acb_srcptr B, slong lenB, slong prec);
0375
0376 void _acb_poly_divrem(acb_ptr Q, acb_ptr R,
0377     acb_srcptr A, slong lenA,
0378     acb_srcptr B, slong lenB, slong prec);
0379
0380 void _acb_poly_rem(acb_ptr R,
0381     acb_srcptr A, slong lenA,
0382     acb_srcptr B, slong lenB, slong prec);
0383
0384 int acb_poly_divrem(acb_poly_t Q, acb_poly_t R,
0385                              const acb_poly_t A, const acb_poly_t B, slong prec);
0386
0387 void _acb_poly_div_root(acb_ptr Q, acb_t R, acb_srcptr A,
0388     slong len, const acb_t c, slong prec);
0389
0390 /* Composition */
0391
0392 void _acb_poly_taylor_shift(acb_ptr poly, const acb_t c, slong n, slong prec);
0393 void acb_poly_taylor_shift(acb_poly_t g, const acb_poly_t f, const acb_t c, slong prec);
0394 void _acb_poly_compose(acb_ptr res, acb_srcptr poly1, slong len1, acb_srcptr poly2, slong len2, slong prec);
0395 void acb_poly_compose(acb_poly_t res, const acb_poly_t poly1, const acb_poly_t poly2, slong prec);
0396
0397 void _acb_poly_compose_series(acb_ptr res, acb_srcptr poly1, slong len1,
0398                             acb_srcptr poly2, slong len2, slong n, slong prec);
0399
0400 void acb_poly_compose_series(acb_poly_t res,
0401                     const acb_poly_t poly1,
0402                     const acb_poly_t poly2, slong n, slong prec);
0403
0404 /* Reversion */
0405
0406 void _acb_poly_revert_series(acb_ptr Qinv, acb_srcptr Q, slong Qlen, slong n, slong prec);
0407 void acb_poly_revert_series(acb_poly_t Qinv, const acb_poly_t Q, slong n, slong prec);
0408
0409
0410
0411 void
0412 _acb_poly_evaluate_vec_fast_precomp(acb_ptr vs, acb_srcptr poly,
0413     slong plen, acb_ptr * tree, slong len, slong prec);
0414
0415 void _acb_poly_evaluate_vec_fast(acb_ptr ys, acb_srcptr poly, slong plen,
0416     acb_srcptr xs, slong n, slong prec);
0417
0418 void
0419 acb_poly_evaluate_vec_fast(acb_ptr ys,
0420         const acb_poly_t poly, acb_srcptr xs, slong n, slong prec);
0421
0422 void
0423 _acb_poly_evaluate_vec_iter(acb_ptr ys, acb_srcptr poly, slong plen,
0424     acb_srcptr xs, slong n, slong prec);
0425
0426 void
0427 acb_poly_evaluate_vec_iter(acb_ptr ys,
0428         const acb_poly_t poly, acb_srcptr xs, slong n, slong prec);
0429
0430 void
0431 _acb_poly_interpolate_barycentric(acb_ptr poly,
0432     acb_srcptr xs, acb_srcptr ys, slong n, slong prec);
0433
0434 void
0435 acb_poly_interpolate_barycentric(acb_poly_t poly,
0436     acb_srcptr xs, acb_srcptr ys, slong n, slong prec);
0437
0438 void
0439 _acb_poly_interpolation_weights(acb_ptr w,
0440     acb_ptr * tree, slong len, slong prec);
0441
0442 void
0443 _acb_poly_interpolate_fast_precomp(acb_ptr poly,
0444     acb_srcptr ys, acb_ptr * tree, acb_srcptr weights,
0445     slong len, slong prec);
0446
0447 void
0448 _acb_poly_interpolate_fast(acb_ptr poly,
0449     acb_srcptr xs, acb_srcptr ys, slong len, slong prec);
0450
0451 void
0452 acb_poly_interpolate_fast(acb_poly_t poly,
0453         acb_srcptr xs, acb_srcptr ys, slong n, slong prec);
0454
0455 void
0456 _acb_poly_interpolate_newton(acb_ptr poly, acb_srcptr xs,
0457     acb_srcptr ys, slong n, slong prec);
0458
0459 void
0460 acb_poly_interpolate_newton(acb_poly_t poly,
0461     acb_srcptr xs, acb_srcptr ys, slong n, slong prec);
0462
0463 void
0464 _acb_poly_product_roots(acb_ptr poly, acb_srcptr xs, slong n, slong prec);
0465
0466 void
0467 acb_poly_product_roots(acb_poly_t poly, acb_srcptr xs, slong n, slong prec);
0468
0469 acb_ptr * _acb_poly_tree_alloc(slong len);
0470
0471 void _acb_poly_tree_free(acb_ptr * tree, slong len);
0472
0473 void
0474 _acb_poly_tree_build(acb_ptr * tree, acb_srcptr roots, slong len, slong prec);
0475
0476
0477 void _acb_poly_root_inclusion(acb_t r, const acb_t m,
0478     acb_srcptr poly,
0479     acb_srcptr polyder, slong len, slong prec);
0480
0481 slong _acb_poly_validate_roots(acb_ptr roots,
0482         acb_srcptr poly, slong len, slong prec);
0483
0484 slong _acb_poly_find_roots(acb_ptr roots,
0485     acb_srcptr poly,
0486     acb_srcptr initial, slong len, slong maxiter, slong prec);
0487
0488 slong acb_poly_find_roots(acb_ptr roots,
0489     const acb_poly_t poly, acb_srcptr initial,
0490     slong maxiter, slong prec);
0491
0492 void _acb_poly_root_bound_fujiwara(mag_t bound, acb_srcptr poly, slong len);
0493
0494 void acb_poly_root_bound_fujiwara(mag_t bound, acb_poly_t poly);
0495
0496 int _acb_poly_validate_real_roots(acb_srcptr roots, acb_srcptr poly, slong len, slong prec);
0497
0498 int acb_poly_validate_real_roots(acb_srcptr roots, const acb_poly_t poly, slong prec);
0499
0500 /* Special functions */
0501
0502 void _acb_poly_pow_ui_trunc_binexp(acb_ptr res,
0503     acb_srcptr f, slong flen, ulong exp, slong len, slong prec);
0504
0505 void acb_poly_pow_ui_trunc_binexp(acb_poly_t res,
0506     const acb_poly_t poly, ulong exp, slong len, slong prec);
0507
0508 void _acb_poly_pow_ui(acb_ptr res, acb_srcptr f, slong flen, ulong exp, slong prec);
0509
0510 void acb_poly_pow_ui(acb_poly_t res, const acb_poly_t poly, ulong exp, slong prec);
0511
0512 void _acb_poly_rsqrt_series(acb_ptr g, acb_srcptr h, slong hlen, slong len, slong prec);
0513
0514 void acb_poly_rsqrt_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0515
0516 void _acb_poly_sqrt_series(acb_ptr g, acb_srcptr h, slong hlen, slong len, slong prec);
0517
0518 void acb_poly_sqrt_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0519
0520 void _acb_poly_log_series(acb_ptr res, acb_srcptr f, slong flen, slong n, slong prec);
0521 void acb_poly_log_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
0522
0523 void _acb_poly_log1p_series(acb_ptr res, acb_srcptr f, slong flen, slong n, slong prec);
0524 void acb_poly_log1p_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
0525
0526 void _acb_poly_atan_series(acb_ptr res, acb_srcptr f, slong flen, slong n, slong prec);
0527
0528 void acb_poly_atan_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
0529
0530 void _acb_poly_atanh_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0531 void acb_poly_atanh_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0532
0533 void _acb_poly_asin_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0534 void acb_poly_asin_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0535
0536 void _acb_poly_asinh_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0537 void acb_poly_asinh_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0538
0539 void _acb_poly_acos_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0540 void acb_poly_acos_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0541
0542 void _acb_poly_acosh_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0543 void acb_poly_acosh_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0544
0545 void _acb_poly_exp_series_basecase(acb_ptr f, acb_srcptr h, slong hlen, slong n, slong prec);
0546 void acb_poly_exp_series_basecase(acb_poly_t f, const acb_poly_t h, slong n, slong prec);
0547 void _acb_poly_exp_series(acb_ptr f, acb_srcptr h, slong hlen, slong n, slong prec);
0548 void acb_poly_exp_series(acb_poly_t f, const acb_poly_t h, slong n, slong prec);
0549
0550 void _acb_poly_exp_pi_i_series(acb_ptr f, acb_srcptr h, slong hlen, slong n, slong prec);
0551 void acb_poly_exp_pi_i_series(acb_poly_t f, const acb_poly_t h, slong n, slong prec);
0552
0553 void _acb_poly_sinh_cosh_series_basecase(acb_ptr s, acb_ptr c, acb_srcptr h, slong hlen, slong n, slong prec);
0554 void acb_poly_sinh_cosh_series_basecase(acb_poly_t s, acb_poly_t c, const acb_poly_t h, slong n, slong prec);
0555 void _acb_poly_sinh_cosh_series_exponential(acb_ptr s, acb_ptr c, acb_srcptr h, slong hlen, slong n, slong prec);
0556 void acb_poly_sinh_cosh_series_exponential(acb_poly_t s, acb_poly_t c, const acb_poly_t h, slong n, slong prec);
0557 void _acb_poly_sinh_cosh_series(acb_ptr s, acb_ptr c, acb_srcptr h, slong hlen, slong n, slong prec);
0558 void acb_poly_sinh_cosh_series(acb_poly_t s, acb_poly_t c, const acb_poly_t h, slong n, slong prec);
0559
0560 void _acb_poly_sinh_series(acb_ptr s, acb_srcptr h, slong hlen, slong n, slong prec);
0561 void acb_poly_sinh_series(acb_poly_t s, const acb_poly_t h, slong n, slong prec);
0562
0563 void _acb_poly_cosh_series(acb_ptr c, acb_srcptr h, slong hlen, slong n, slong prec);
0564 void acb_poly_cosh_series(acb_poly_t c, const acb_poly_t h, slong n, slong prec);
0565
0566 void _acb_poly_tanh_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0567 void acb_poly_tanh_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0568
0569 void _acb_poly_sin_cos_series(acb_ptr s, acb_ptr c, acb_srcptr h, slong hlen, slong len, slong prec);
0570 void acb_poly_sin_cos_series(acb_poly_t s, acb_poly_t c, const acb_poly_t h, slong n, slong prec);
0571
0572 void _acb_poly_sin_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0573
0574 void acb_poly_sin_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0575
0576 void _acb_poly_cos_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0577
0578 void acb_poly_cos_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0579
0580 void _acb_poly_sin_cos_pi_series(acb_ptr s, acb_ptr c, acb_srcptr h, slong hlen, slong len, slong prec);
0581 void acb_poly_sin_cos_pi_series(acb_poly_t s, acb_poly_t c, const acb_poly_t h, slong n, slong prec);
0582
0583 void _acb_poly_sin_pi_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0584
0585 void acb_poly_sin_pi_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0586
0587 void _acb_poly_cos_pi_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0588
0589 void acb_poly_cos_pi_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0590
0591 void _acb_poly_cot_pi_series(acb_ptr g, acb_srcptr h, slong hlen, slong len, slong prec);
0592
0593 void acb_poly_cot_pi_series(acb_poly_t res, const acb_poly_t f, slong len, slong prec);
0594
0595 void _acb_poly_cot_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0596 void acb_poly_cot_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0597
0598 void _acb_poly_coth_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0599 void acb_poly_coth_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0600
0601 void _acb_poly_tan_series(acb_ptr g, acb_srcptr h, slong hlen, slong len, slong prec);
0602
0603 void acb_poly_tan_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0604
0605 void _acb_poly_tan_pi_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0606 void acb_poly_tan_pi_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0607
0608 void _acb_poly_sinc_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0609 void acb_poly_sinc_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0610 void _acb_poly_sinc_pi_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0611 void acb_poly_sinc_pi_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0612
0613 void _acb_poly_lambertw_series(acb_ptr res, acb_srcptr z, slong zlen, const fmpz_t k, int flags, slong len, slong prec);
0614 void acb_poly_lambertw_series(acb_poly_t res, const acb_poly_t z, const fmpz_t k, int flags, slong len, slong prec);
0615
0616 void _acb_poly_gamma_series(acb_ptr res, acb_srcptr h, slong hlen, slong len, slong prec);
0617
0618 void acb_poly_gamma_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
0619
0620 void _acb_poly_rgamma_series(acb_ptr res, acb_srcptr h, slong hlen, slong len, slong prec);
0621
0622 void acb_poly_rgamma_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
0623
0624 void _acb_poly_lgamma_series(acb_ptr res, acb_srcptr h, slong hlen, slong len, slong prec);
0625
0626 void acb_poly_lgamma_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
0627
0628 void _acb_poly_digamma_series(acb_ptr res, acb_srcptr h, slong hlen, slong len, slong prec);
0629
0630 void acb_poly_digamma_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
0631
0632 void _acb_poly_rising_ui_series(acb_ptr res, acb_srcptr f, slong flen, ulong r, slong trunc, slong prec);
0633
0634 void acb_poly_rising_ui_series(acb_poly_t res, const acb_poly_t f, ulong r, slong trunc, slong prec);
0635
0636 void _acb_poly_pow_acb_series(acb_ptr h,
0637     acb_srcptr f, slong flen, const acb_t g, slong len, slong prec);
0638
0639 void acb_poly_pow_acb_series(acb_poly_t h,
0640     const acb_poly_t f, const acb_t g, slong len, slong prec);
0641
0642 void _acb_poly_pow_series(acb_ptr h,
0643     acb_srcptr f, slong flen,
0644     acb_srcptr g, slong glen, slong len, slong prec);
0645
0646 void acb_poly_pow_series(acb_poly_t h,
0647     const acb_poly_t f, const acb_poly_t g, slong len, slong prec);
0648
0649 void
0650 _acb_poly_binomial_pow_acb_series(acb_ptr h, acb_srcptr f, slong flen,
0651     const acb_t g, slong len, slong prec);
0652
0653 /* TODO: document */
0654 ACB_POLY_INLINE void
0655 _acb_poly_acb_pow_cpx(acb_ptr w, const acb_t a, const acb_t b, slong len, slong prec)
0656 {
0657     if (len == 1)
0658     {
0659         acb_pow(w, a, b, prec);
0660     }
0661     else
0662     {
0663         acb_t log_a;
0664         slong k;
0665
0666         acb_init(log_a);
0667
0668         acb_log(log_a, a, prec);
0669         acb_mul(w, log_a, b, prec);
0670         acb_exp(w, w, prec);
0671
0672         for (k = 1; k < len; k++)
0673         {
0674             acb_mul(w + k, w + k - 1, log_a, prec);
0675             acb_div_ui(w + k, w + k, k, prec);
0676         }
0677
0678         acb_clear(log_a);
0679     }
0680 }
0681
0682 #define _acb_poly_pow_cpx _acb_poly_acb_pow_cpx
0683
0684 /* TODO: document */
0685 void _acb_poly_acb_invpow_cpx(acb_ptr res, const acb_t N, const acb_t c, slong trunc, slong prec);
0686 /* TODO: document */
0687 void _acb_poly_mullow_cpx(acb_ptr res, acb_srcptr src, slong len, const acb_t c, slong trunc, slong prec);
0688
0689 void _acb_poly_powsum_series_naive(acb_ptr z, const acb_t s, const acb_t a, const acb_t q, slong n, slong len, slong prec);
0690 void _acb_poly_powsum_series_naive_threaded(acb_ptr z, const acb_t s, const acb_t a, const acb_t q, slong n, slong len, slong prec);
0691 void _acb_poly_powsum_one_series_sieved(acb_ptr z, const acb_t s, slong n, slong len, slong prec);
0692
0693 void _acb_poly_zeta_em_sum(acb_ptr z, const acb_t s, const acb_t a, int deflate, ulong N, ulong M, slong d, slong prec);
0694 void _acb_poly_zeta_em_choose_param(mag_t bound, ulong * N, ulong * M, const acb_t s, const acb_t a, slong d, slong target, slong prec);
0695 void _acb_poly_zeta_em_bound1(mag_t bound, const acb_t s, const acb_t a, slong N, slong M, slong d, slong wp);
0696 void _acb_poly_zeta_em_bound(arb_ptr vec, const acb_t s, const acb_t a, ulong N, ulong M, slong d, slong wp);
0697
0698 void _acb_poly_zeta_em_tail_naive(acb_ptr sum, const acb_t s, const acb_t Na, acb_srcptr Nasx, slong M, slong len, slong prec);
0699 void _acb_poly_zeta_em_tail_bsplit(acb_ptr z, const acb_t s, const acb_t Na, acb_srcptr Nasx, slong M, slong len, slong prec);
0700
0701 void _acb_poly_zeta_cpx_series(acb_ptr z, const acb_t s, const acb_t a, int deflate, slong d, slong prec);
0702
0703 void _acb_poly_zeta_series(acb_ptr res, acb_srcptr h, slong hlen, const acb_t a, int deflate, slong len, slong prec);
0704
0705 void acb_poly_zeta_series(acb_poly_t res, const acb_poly_t f, const acb_t a, int deflate, slong n, slong prec);
0706
0707 void _acb_poly_polylog_cpx_zeta(acb_ptr w, const acb_t s, const acb_t z, slong len, slong prec);
0708 void _acb_poly_polylog_cpx_small(acb_ptr w, const acb_t s, const acb_t z, slong len, slong prec);
0709 void _acb_poly_polylog_cpx(acb_ptr w, const acb_t s, const acb_t z, slong len, slong prec);
0710
0711 void _acb_poly_polylog_series(acb_ptr res, acb_srcptr s, slong slen, const acb_t z, slong len, slong prec);
0712 void acb_poly_polylog_series(acb_poly_t res, const acb_poly_t s, const acb_t z, slong n, slong prec);
0713
0714 void _acb_poly_agm1_series(acb_ptr res, acb_srcptr z, slong zlen, slong len, slong prec);
0715 void acb_poly_agm1_series(acb_poly_t res, const acb_poly_t z, slong n, slong prec);
0716 void _acb_poly_elliptic_k_series(acb_ptr res, acb_srcptr z, slong zlen, slong len, slong prec);
0717 void acb_poly_elliptic_k_series(acb_poly_t res, const acb_poly_t z, slong n, slong prec);
0718 void _acb_poly_elliptic_p_series(acb_ptr res, acb_srcptr z, slong zlen, const acb_t tau, slong len, slong prec);
0719 void acb_poly_elliptic_p_series(acb_poly_t res, const acb_poly_t z, const acb_t tau, slong n, slong prec);
0720
0721 void _acb_poly_erf_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
0722 void acb_poly_erf_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
0723
0724 ACB_POLY_INLINE slong
0725 acb_poly_allocated_bytes(const acb_poly_t x)
0726 {
0727     return _acb_vec_allocated_bytes(x->coeffs, x->alloc);
0728 }
0729
0730 /* Functions related to root finder using Weierstrass-Durand-Kerner algorithm with complex double arithmetic */
0731 void cd_poly_roots_initial_values(double * z_r, double * z_i,
0732                                   const double * p_r, const double * p_i, slong n,
0733                                   const double * z0, slong d);
0734 void cd_poly_weierstrass(double* results_r, double* results_i,
0735                          double lc_r, double lc_i,
0736                          const double* values_r, const double* values_i,
0737                          slong n_start, slong n_end, slong d);
0738 void cd_poly_weierstrass_distinct_orders(double* results_r, double* results_i,
0739                               double lc_r, double lc_i,
0740                               const double* col_values_r, const double* col_values_i, slong d,
0741                               const double* row_values_r, const double* row_values_i, slong n_start, slong n_end);
0742 double cd_poly_wdk_update(double* z_r, double* z_i,
0743                              const double* vp_r, const double* vp_i,
0744                              const double* wdk_r, const double* wdk_i,
0745                              slong n_start, slong n_end, double stepsize_bound);
0746 double cd_poly_refine_roots(double * z, const double * p, slong n, double stepsize_bound);
0747 double cd_poly_refine_roots_with_pivot(double * z, const double * p, slong n, double stepsize_bound);
0748 /* Main high-level function for evaluating and finding roots in machine precision */
0749 void cd_poly_horner(double* results_r, double* results_i,
0750                     const double* values_r, const double* values_i, slong n_start, slong n_end,
0751                     const double* coefficients_r, const double* coefficients_i, slong n);
0752 double cd_poly_find_roots(double * z, const double * p, const double * z0, slong n, slong num_iter, double reltol);
0753 double _acb_poly_find_roots_double(acb_ptr roots, acb_srcptr poly, acb_srcptr initial, slong len, slong maxiter, slong prec);
0754
0755
0756 #ifdef __cplusplus
0757 }
0758 #endif
0759
0760 #endif