include/flint/arb_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 ARB_POLY_H
0013 #define ARB_POLY_H
0014
0015 #ifdef ARB_POLY_INLINES_C
0016 #define ARB_POLY_INLINE
0017 #else
0018 #define ARB_POLY_INLINE static inline
0019 #endif
0020
0021 #include "fmpq_types.h"
0022 #include "arb.h"
0023 #include "acb_types.h"
0024
0025 #ifdef __cplusplus
0026 extern "C" {
0027 #endif
0028
0029 /* Memory management */
0030
0031 void arb_poly_init(arb_poly_t poly);
0032
0033 void arb_poly_init2(arb_poly_t poly, slong len);
0034
0035 void arb_poly_clear(arb_poly_t poly);
0036
0037 void arb_poly_fit_length(arb_poly_t poly, slong len);
0038
0039 void _arb_poly_set_length(arb_poly_t poly, slong len);
0040
0041 void _arb_poly_normalise(arb_poly_t poly);
0042
0043 ARB_POLY_INLINE void
0044 arb_poly_swap(arb_poly_t poly1, arb_poly_t poly2)
0045 {
0046     FLINT_SWAP(arb_poly_struct, *poly1, *poly2);
0047 }
0048
0049 void arb_poly_set(arb_poly_t poly, const arb_poly_t src);
0050
0051 void arb_poly_set_round(arb_poly_t poly, const arb_poly_t src, slong prec);
0052
0053 void arb_poly_set_trunc(arb_poly_t res, const arb_poly_t poly, slong n);
0054
0055 void arb_poly_set_trunc_round(arb_poly_t res, const arb_poly_t poly, slong n, slong prec);
0056
0057 /* Basic manipulation */
0058
0059 ARB_POLY_INLINE slong arb_poly_length(const arb_poly_t poly)
0060 {
0061     return poly->length;
0062 }
0063
0064 ARB_POLY_INLINE slong arb_poly_degree(const arb_poly_t poly)
0065 {
0066     return poly->length - 1;
0067 }
0068
0069 slong arb_poly_valuation(const arb_poly_t poly);
0070
0071 ARB_POLY_INLINE int
0072 arb_poly_is_zero(const arb_poly_t z)
0073 {
0074     return arb_poly_length(z) == 0;
0075 }
0076
0077 ARB_POLY_INLINE int
0078 arb_poly_is_one(const arb_poly_t z)
0079 {
0080     return (arb_poly_length(z) == 1) && arb_is_one(z->coeffs);
0081 }
0082
0083 ARB_POLY_INLINE int
0084 arb_poly_is_x(const arb_poly_t z)
0085 {
0086     return (arb_poly_length(z) == 2) && arb_is_zero(z->coeffs)
0087         && arb_is_one(z->coeffs + 1);
0088 }
0089
0090 ARB_POLY_INLINE void arb_poly_zero(arb_poly_t poly)
0091 {
0092     poly->length = 0;
0093 }
0094
0095 ARB_POLY_INLINE void
0096 arb_poly_one(arb_poly_t poly)
0097 {
0098     arb_poly_fit_length(poly, 1);
0099     arb_one(poly->coeffs);
0100     _arb_poly_set_length(poly, 1);
0101 }
0102
0103 void arb_poly_set_coeff_si(arb_poly_t poly, slong n, slong x);
0104
0105 void arb_poly_set_coeff_arb(arb_poly_t poly, slong n, const arb_t x);
0106
0107 void arb_poly_get_coeff_arb(arb_t x, const arb_poly_t poly, slong n);
0108
0109 #define arb_poly_get_coeff_ptr(poly, n) \
0110     ((n) < (poly)->length ? (poly)->coeffs + (n) : NULL)
0111
0112 void _arb_poly_reverse(arb_ptr res, arb_srcptr poly, slong len, slong n);
0113
0114 void _arb_poly_shift_right(arb_ptr res, arb_srcptr poly, slong len, slong n);
0115
0116 void arb_poly_shift_right(arb_poly_t res, const arb_poly_t poly, slong n);
0117
0118 void _arb_poly_shift_left(arb_ptr res, arb_srcptr poly, slong len, slong n);
0119
0120 void arb_poly_shift_left(arb_poly_t res, const arb_poly_t poly, slong n);
0121
0122 ARB_POLY_INLINE void
0123 arb_poly_truncate(arb_poly_t poly, slong newlen)
0124 {
0125     if (poly->length > newlen)
0126     {
0127         slong i;
0128         for (i = newlen; i < poly->length; i++)
0129             arb_zero(poly->coeffs + i);
0130         poly->length = newlen;
0131         _arb_poly_normalise(poly);
0132     }
0133 }
0134
0135 /* Conversions */
0136
0137 void arb_poly_set_fmpz_poly(arb_poly_t poly, const fmpz_poly_t src, slong prec);
0138
0139 void arb_poly_set_fmpq_poly(arb_poly_t poly, const fmpq_poly_t src, slong prec);
0140
0141 ARB_POLY_INLINE void
0142 arb_poly_set_arb(arb_poly_t poly, const arb_t c)
0143 {
0144     arb_poly_fit_length(poly, 1);
0145     arb_set(poly->coeffs, c);
0146     _arb_poly_set_length(poly, !arb_is_zero(poly->coeffs));
0147 }
0148
0149 void arb_poly_set_si(arb_poly_t poly, slong c);
0150
0151 int arb_poly_get_unique_fmpz_poly(fmpz_poly_t res, const arb_poly_t src);
0152
0153 /* Comparisons */
0154
0155 int arb_poly_contains(const arb_poly_t poly1, const arb_poly_t poly2);
0156
0157 int arb_poly_contains_fmpz_poly(const arb_poly_t poly1, const fmpz_poly_t poly2);
0158
0159 int arb_poly_contains_fmpq_poly(const arb_poly_t poly1, const fmpq_poly_t poly2);
0160
0161 int arb_poly_equal(const arb_poly_t A, const arb_poly_t B);
0162
0163 int _arb_poly_overlaps(arb_srcptr poly1, slong len1, arb_srcptr poly2, slong len2);
0164
0165 int arb_poly_overlaps(const arb_poly_t poly1, const arb_poly_t poly2);
0166
0167 /* Bounds */
0168
0169 void _arb_poly_majorant(arb_ptr res, arb_srcptr vec, slong len, slong prec);
0170
0171 void arb_poly_majorant(arb_poly_t res, const arb_poly_t poly, slong prec);
0172
0173 /* IO */
0174
0175 #ifdef FLINT_HAVE_FILE
0176 void arb_poly_fprintd(FILE * file, const arb_poly_t poly, slong digits);
0177 #endif
0178
0179 void arb_poly_printd(const arb_poly_t poly, slong digits);
0180
0181 /* Random generation */
0182
0183 void arb_poly_randtest(arb_poly_t poly, flint_rand_t state, slong len, slong prec, slong mag_bits);
0184
0185 /* Arithmetic */
0186
0187 void
0188 _arb_poly_add(arb_ptr res, arb_srcptr poly1, slong len1,
0189     arb_srcptr poly2, slong len2, slong prec);
0190
0191 void arb_poly_add(arb_poly_t res, const arb_poly_t poly1,
0192               const arb_poly_t poly2, slong prec);
0193
0194 void arb_poly_add_si(arb_poly_t res, const arb_poly_t poly, slong c, slong prec);
0195
0196 void _arb_poly_sub(arb_ptr res, arb_srcptr poly1, slong len1,
0197     arb_srcptr poly2, slong len2, slong prec);
0198
0199 void arb_poly_sub(arb_poly_t res, const arb_poly_t poly1,
0200               const arb_poly_t poly2, slong prec);
0201
0202 void arb_poly_add_series(arb_poly_t res, const arb_poly_t poly1,
0203               const arb_poly_t poly2, slong len, slong prec);
0204
0205 void arb_poly_sub_series(arb_poly_t res, const arb_poly_t poly1,
0206               const arb_poly_t poly2, slong len, slong prec);
0207
0208 ARB_POLY_INLINE void
0209 arb_poly_neg(arb_poly_t res, const arb_poly_t poly)
0210 {
0211     arb_poly_fit_length(res, poly->length);
0212     _arb_vec_neg(res->coeffs, poly->coeffs, poly->length);
0213     _arb_poly_set_length(res, poly->length);
0214 }
0215
0216 ARB_POLY_INLINE void
0217 arb_poly_scalar_mul_2exp_si(arb_poly_t res, const arb_poly_t poly, slong c)
0218 {
0219     arb_poly_fit_length(res, poly->length);
0220     _arb_vec_scalar_mul_2exp_si(res->coeffs, poly->coeffs, poly->length, c);
0221     _arb_poly_set_length(res, poly->length);
0222 }
0223
0224 ARB_POLY_INLINE void
0225 arb_poly_scalar_mul(arb_poly_t res, const arb_poly_t poly, const arb_t c, slong prec)
0226 {
0227     arb_poly_fit_length(res, poly->length);
0228     _arb_vec_scalar_mul(res->coeffs, poly->coeffs, poly->length, c, prec);
0229     _arb_poly_set_length(res, poly->length);
0230     _arb_poly_normalise(res);
0231 }
0232
0233 ARB_POLY_INLINE void
0234 arb_poly_scalar_mul_si(arb_poly_t res, const arb_poly_t poly, slong c, slong prec)
0235 {
0236     arb_poly_fit_length(res, poly->length);
0237     _arb_vec_scalar_mul_si(res->coeffs, poly->coeffs, poly->length, c, prec);
0238     _arb_poly_set_length(res, poly->length);
0239     _arb_poly_normalise(res);
0240 }
0241
0242 ARB_POLY_INLINE void
0243 arb_poly_scalar_div(arb_poly_t res, const arb_poly_t poly, const arb_t c, slong prec)
0244 {
0245     arb_poly_fit_length(res, poly->length);
0246     _arb_vec_scalar_div(res->coeffs, poly->coeffs, poly->length, c, prec);
0247     _arb_poly_set_length(res, poly->length);
0248     _arb_poly_normalise(res);
0249 }
0250
0251 void _arb_poly_mullow_classical(arb_ptr res,
0252     arb_srcptr poly1, slong len1,
0253     arb_srcptr poly2, slong len2, slong n, slong prec);
0254
0255 void arb_poly_mullow_classical(arb_poly_t res, const arb_poly_t poly1,
0256                                             const arb_poly_t poly2,
0257                                                 slong n, slong prec);
0258
0259 void _arb_poly_mullow_block(arb_ptr C,
0260     arb_srcptr A, slong lenA,
0261     arb_srcptr B, slong lenB, slong n, slong prec);
0262
0263 void arb_poly_mullow_block(arb_poly_t res, const arb_poly_t poly1,
0264               const arb_poly_t poly2, slong len, slong prec);
0265
0266 void _arb_poly_mullow(arb_ptr C,
0267     arb_srcptr A, slong lenA,
0268     arb_srcptr B, slong lenB, slong n, slong prec);
0269
0270 void arb_poly_mullow(arb_poly_t res, const arb_poly_t poly1,
0271               const arb_poly_t poly2, slong len, slong prec);
0272
0273 void _arb_poly_mulmid_block(arb_ptr z, arb_srcptr x, slong xlen, arb_srcptr y, slong ylen, slong nlo, slong nhi, slong prec);
0274 void arb_poly_mulmid_block(arb_poly_t res, const arb_poly_t poly1, const arb_poly_t poly2, slong nlo, slong nhi, slong prec);
0275 void _arb_poly_mulmid_classical(arb_ptr z, arb_srcptr x, slong xlen, arb_srcptr y, slong ylen, slong nlo, slong nhi, slong prec);
0276 void arb_poly_mulmid_classical(arb_poly_t res, const arb_poly_t poly1, const arb_poly_t poly2, slong nlo, slong nhi, slong prec);
0277 void _arb_poly_mulmid(arb_ptr z, arb_srcptr x, slong xlen, arb_srcptr y, slong ylen, slong nlo, slong nhi, slong prec);
0278 void arb_poly_mulmid(arb_poly_t res, const arb_poly_t poly1, const arb_poly_t poly2, slong nlo, slong nhi, slong prec);
0279
0280 void _arb_poly_mul(arb_ptr C,
0281     arb_srcptr A, slong lenA,
0282     arb_srcptr B, slong lenB, slong prec);
0283
0284 void arb_poly_mul(arb_poly_t res, const arb_poly_t poly1,
0285               const arb_poly_t poly2, slong prec);
0286
0287 ARB_POLY_INLINE void
0288 _arb_poly_mul_monic(arb_ptr res, arb_srcptr poly1, slong len1,
0289     arb_srcptr poly2, slong len2, slong prec)
0290 {
0291     if (len1 + len2 - 2 > 0)
0292         _arb_poly_mullow(res, poly1, len1, poly2, len2, len1 + len2 - 2, prec);
0293     arb_one(res + len1 + len2 - 2);
0294 }
0295
0296 void _arb_poly_inv_series(arb_ptr Qinv,
0297     arb_srcptr Q, slong Qlen, slong len, slong prec);
0298
0299 void arb_poly_inv_series(arb_poly_t Qinv, const arb_poly_t Q, slong n, slong prec);
0300
0301 void  _arb_poly_div_series(arb_ptr Q, arb_srcptr A, slong Alen,
0302     arb_srcptr B, slong Blen, slong n, slong prec);
0303
0304 void arb_poly_div_series(arb_poly_t Q, const arb_poly_t A, const arb_poly_t B, slong n, slong prec);
0305
0306 void
0307 _arb_poly_div(arb_ptr Q,
0308     arb_srcptr A, slong lenA,
0309     arb_srcptr B, slong lenB, slong prec);
0310
0311 void _arb_poly_divrem(arb_ptr Q, arb_ptr R,
0312     arb_srcptr A, slong lenA,
0313     arb_srcptr B, slong lenB, slong prec);
0314
0315 void _arb_poly_rem(arb_ptr R,
0316     arb_srcptr A, slong lenA,
0317     arb_srcptr B, slong lenB, slong prec);
0318
0319 int arb_poly_divrem(arb_poly_t Q, arb_poly_t R,
0320                              const arb_poly_t A, const arb_poly_t B, slong prec);
0321
0322 void _arb_poly_div_root(arb_ptr Q, arb_t R, arb_srcptr A,
0323     slong len, const arb_t c, slong prec);
0324
0325 /* Product trees */
0326
0327 void _arb_poly_product_roots(arb_ptr poly, arb_srcptr xs, slong n, slong prec);
0328
0329 void arb_poly_product_roots(arb_poly_t poly, arb_srcptr xs, slong n, slong prec);
0330
0331 void _arb_poly_product_roots_complex(arb_ptr poly, arb_srcptr r, slong rn,
0332     acb_srcptr c, slong cn, slong prec);
0333
0334 void arb_poly_product_roots_complex(arb_poly_t poly,
0335         arb_srcptr r, slong rn, acb_srcptr c, slong cn, slong prec);
0336
0337 arb_ptr * _arb_poly_tree_alloc(slong len);
0338
0339 void _arb_poly_tree_free(arb_ptr * tree, slong len);
0340
0341 void _arb_poly_tree_build(arb_ptr * tree, arb_srcptr roots, slong len, slong prec);
0342
0343 /* Composition */
0344
0345 void _arb_poly_taylor_shift(arb_ptr poly, const arb_t c, slong n, slong prec);
0346 void arb_poly_taylor_shift(arb_poly_t g, const arb_poly_t f, const arb_t c, slong prec);
0347 void _arb_poly_compose(arb_ptr res, arb_srcptr poly1, slong len1, arb_srcptr poly2, slong len2, slong prec);
0348 void arb_poly_compose(arb_poly_t res, const arb_poly_t poly1, const arb_poly_t poly2, slong prec);
0349
0350 void _arb_poly_compose_series(arb_ptr res, arb_srcptr poly1, slong len1,
0351                             arb_srcptr poly2, slong len2, slong n, slong prec);
0352
0353 void arb_poly_compose_series(arb_poly_t res,
0354                     const arb_poly_t poly1,
0355                     const arb_poly_t poly2, slong n, slong prec);
0356
0357 /* Reversion */
0358
0359 void _arb_poly_revert_series(arb_ptr Qinv, arb_srcptr Q, slong Qlen, slong n, slong prec);
0360 void arb_poly_revert_series(arb_poly_t Qinv, const arb_poly_t Q, slong n, slong prec);
0361
0362 /* Evaluation and interpolation */
0363
0364 void _arb_poly_evaluate_horner(arb_t res, arb_srcptr f, slong len, const arb_t a, slong prec);
0365 void arb_poly_evaluate_horner(arb_t res, const arb_poly_t f, const arb_t a, slong prec);
0366
0367 void _arb_poly_evaluate_rectangular(arb_t y, arb_srcptr poly, slong len, const arb_t x, slong prec);
0368 void arb_poly_evaluate_rectangular(arb_t res, const arb_poly_t f, const arb_t a, slong prec);
0369
0370 void _arb_poly_evaluate(arb_t res, arb_srcptr f, slong len, const arb_t a, slong prec);
0371 void arb_poly_evaluate(arb_t res, const arb_poly_t f, const arb_t a, slong prec);
0372
0373 void _arb_poly_evaluate2_horner(arb_t y, arb_t z, arb_srcptr f, slong len, const arb_t x, slong prec);
0374 void arb_poly_evaluate2_horner(arb_t y, arb_t z, const arb_poly_t f, const arb_t x, slong prec);
0375
0376 void _arb_poly_evaluate2_rectangular(arb_t y, arb_t z, arb_srcptr f, slong len, const arb_t x, slong prec);
0377 void arb_poly_evaluate2_rectangular(arb_t y, arb_t z, const arb_poly_t f, const arb_t x, slong prec);
0378
0379 void _arb_poly_evaluate2(arb_t y, arb_t z, arb_srcptr f, slong len, const arb_t x, slong prec);
0380 void arb_poly_evaluate2(arb_t y, arb_t z, const arb_poly_t f, const arb_t x, slong prec);
0381
0382
0383
0384
0385 void _arb_poly_evaluate_vec_iter(arb_ptr ys, arb_srcptr poly, slong plen,
0386     arb_srcptr xs, slong n, slong prec);
0387
0388 void arb_poly_evaluate_vec_iter(arb_ptr ys,
0389         const arb_poly_t poly, arb_srcptr xs, slong n, slong prec);
0390
0391 void _arb_poly_evaluate_vec_fast_precomp(arb_ptr vs, arb_srcptr poly,
0392     slong plen, arb_ptr * tree, slong len, slong prec);
0393
0394 void _arb_poly_evaluate_vec_fast(arb_ptr ys, arb_srcptr poly, slong plen,
0395     arb_srcptr xs, slong n, slong prec);
0396
0397 void arb_poly_evaluate_vec_fast(arb_ptr ys,
0398         const arb_poly_t poly, arb_srcptr xs, slong n, slong prec);
0399
0400 void _arb_poly_interpolate_newton(arb_ptr poly, arb_srcptr xs,
0401     arb_srcptr ys, slong n, slong prec);
0402
0403 void arb_poly_interpolate_newton(arb_poly_t poly,
0404     arb_srcptr xs, arb_srcptr ys, slong n, slong prec);
0405
0406 void
0407 _arb_poly_interpolate_barycentric(arb_ptr poly,
0408     arb_srcptr xs, arb_srcptr ys, slong n, slong prec);
0409
0410 void arb_poly_interpolate_barycentric(arb_poly_t poly,
0411     arb_srcptr xs, arb_srcptr ys, slong n, slong prec);
0412
0413 void _arb_poly_interpolation_weights(arb_ptr w,
0414     arb_ptr * tree, slong len, slong prec);
0415
0416 void _arb_poly_interpolate_fast_precomp(arb_ptr poly,
0417     arb_srcptr ys, arb_ptr * tree, arb_srcptr weights,
0418     slong len, slong prec);
0419
0420 void _arb_poly_interpolate_fast(arb_ptr poly,
0421     arb_srcptr xs, arb_srcptr ys, slong len, slong prec);
0422
0423 void arb_poly_interpolate_fast(arb_poly_t poly,
0424         arb_srcptr xs, arb_srcptr ys, slong n, slong prec);
0425
0426 /* Derivative and integral */
0427
0428 void _arb_poly_derivative(arb_ptr res, arb_srcptr poly, slong len, slong prec);
0429
0430 void arb_poly_derivative(arb_poly_t res, const arb_poly_t poly, slong prec);
0431
0432 void _arb_poly_nth_derivative(arb_ptr res, arb_srcptr poly, ulong n, slong len, slong prec);
0433
0434 void arb_poly_nth_derivative(arb_poly_t res, const arb_poly_t poly, ulong n, slong prec);
0435
0436 void _arb_poly_integral(arb_ptr res, arb_srcptr poly, slong len, slong prec);
0437
0438 void arb_poly_integral(arb_poly_t res, const arb_poly_t poly, slong prec);
0439
0440 /* Transforms */
0441
0442 void arb_poly_borel_transform(arb_poly_t res, const arb_poly_t poly, slong prec);
0443
0444 void _arb_poly_borel_transform(arb_ptr res, arb_srcptr poly, slong len, slong prec);
0445
0446 void arb_poly_inv_borel_transform(arb_poly_t res, const arb_poly_t poly, slong prec);
0447
0448 void _arb_poly_inv_borel_transform(arb_ptr res, arb_srcptr poly, slong len, slong prec);
0449
0450 void _arb_poly_binomial_transform_basecase(arb_ptr b, arb_srcptr a, slong alen, slong len, slong prec);
0451
0452 void arb_poly_binomial_transform_basecase(arb_poly_t b, const arb_poly_t a, slong len, slong prec);
0453
0454 void _arb_poly_binomial_transform_convolution(arb_ptr b, arb_srcptr a, slong alen, slong len, slong prec);
0455
0456 void arb_poly_binomial_transform_convolution(arb_poly_t b, const arb_poly_t a, slong len, slong prec);
0457
0458 void _arb_poly_binomial_transform(arb_ptr b, arb_srcptr a, slong alen, slong len, slong prec);
0459
0460 void arb_poly_binomial_transform(arb_poly_t b, const arb_poly_t a, slong len, slong prec);
0461
0462 void _arb_poly_graeffe_transform(arb_ptr b, arb_srcptr a, slong len, slong prec);
0463
0464 void arb_poly_graeffe_transform(arb_poly_t b, const arb_poly_t a, slong prec);
0465
0466 /* Special functions */
0467
0468 void _arb_poly_pow_ui_trunc_binexp(arb_ptr res,
0469     arb_srcptr f, slong flen, ulong exp, slong len, slong prec);
0470
0471 void arb_poly_pow_ui_trunc_binexp(arb_poly_t res,
0472     const arb_poly_t poly, ulong exp, slong len, slong prec);
0473
0474 void _arb_poly_pow_ui(arb_ptr res, arb_srcptr f, slong flen, ulong exp, slong prec);
0475
0476 void arb_poly_pow_ui(arb_poly_t res, const arb_poly_t poly, ulong exp, slong prec);
0477
0478 void _arb_poly_pow_series(arb_ptr h,
0479     arb_srcptr f, slong flen,
0480     arb_srcptr g, slong glen, slong len, slong prec);
0481
0482 void arb_poly_pow_series(arb_poly_t h,
0483     const arb_poly_t f, const arb_poly_t g, slong len, slong prec);
0484
0485 void _arb_poly_pow_arb_series(arb_ptr h,
0486     arb_srcptr f, slong flen, const arb_t g, slong len, slong prec);
0487
0488 void arb_poly_pow_arb_series(arb_poly_t h,
0489     const arb_poly_t f, const arb_t g, slong len, slong prec);
0490
0491 void _arb_poly_binomial_pow_arb_series(arb_ptr h, arb_srcptr f, slong flen, const arb_t g, slong len, slong prec);
0492
0493 void _arb_poly_rsqrt_series(arb_ptr g,
0494     arb_srcptr h, slong hlen, slong len, slong prec);
0495
0496 void arb_poly_rsqrt_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0497
0498 void _arb_poly_sqrt_series(arb_ptr g,
0499     arb_srcptr h, slong hlen, slong len, slong prec);
0500
0501 void arb_poly_sqrt_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0502
0503 void _arb_poly_log_series(arb_ptr res, arb_srcptr f, slong flen, slong n, slong prec);
0504 void arb_poly_log_series(arb_poly_t res, const arb_poly_t f, slong n, slong prec);
0505
0506 void _arb_poly_log1p_series(arb_ptr res, arb_srcptr f, slong flen, slong n, slong prec);
0507 void arb_poly_log1p_series(arb_poly_t res, const arb_poly_t f, slong n, slong prec);
0508
0509 void _arb_poly_atan_series(arb_ptr res, arb_srcptr f, slong flen, slong n, slong prec);
0510
0511 void arb_poly_atan_series(arb_poly_t res, const arb_poly_t f, slong n, slong prec);
0512
0513 void _arb_poly_atanh_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0514 void arb_poly_atanh_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0515
0516 void _arb_poly_asin_series(arb_ptr res, arb_srcptr f, slong flen, slong n, slong prec);
0517
0518 void arb_poly_asin_series(arb_poly_t res, const arb_poly_t f, slong n, slong prec);
0519
0520 void _arb_poly_asinh_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0521 void arb_poly_asinh_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0522
0523 void _arb_poly_acos_series(arb_ptr res, arb_srcptr f, slong flen, slong n, slong prec);
0524
0525 void arb_poly_acos_series(arb_poly_t res, const arb_poly_t f, slong n, slong prec);
0526
0527 void _arb_poly_acosh_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0528 void arb_poly_acosh_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0529
0530 void _arb_poly_exp_series_basecase(arb_ptr f, arb_srcptr h, slong hlen, slong n, slong prec);
0531 void arb_poly_exp_series_basecase(arb_poly_t f, const arb_poly_t h, slong n, slong prec);
0532 void _arb_poly_exp_series(arb_ptr f, arb_srcptr h, slong hlen, slong n, slong prec);
0533 void arb_poly_exp_series(arb_poly_t f, const arb_poly_t h, slong n, slong prec);
0534
0535 void _arb_poly_sinh_cosh_series_basecase(arb_ptr s, arb_ptr c, arb_srcptr h, slong hlen, slong n, slong prec);
0536 void arb_poly_sinh_cosh_series_basecase(arb_poly_t s, arb_poly_t c, const arb_poly_t h, slong n, slong prec);
0537 void _arb_poly_sinh_cosh_series_exponential(arb_ptr s, arb_ptr c, arb_srcptr h, slong hlen, slong n, slong prec);
0538 void arb_poly_sinh_cosh_series_exponential(arb_poly_t s, arb_poly_t c, const arb_poly_t h, slong n, slong prec);
0539 void _arb_poly_sinh_cosh_series(arb_ptr s, arb_ptr c, arb_srcptr h, slong hlen, slong n, slong prec);
0540 void arb_poly_sinh_cosh_series(arb_poly_t s, arb_poly_t c, const arb_poly_t h, slong n, slong prec);
0541
0542 void _arb_poly_sinh_series(arb_ptr s, arb_srcptr h, slong hlen, slong n, slong prec);
0543 void arb_poly_sinh_series(arb_poly_t s, const arb_poly_t h, slong n, slong prec);
0544
0545 void _arb_poly_cosh_series(arb_ptr c, arb_srcptr h, slong hlen, slong n, slong prec);
0546 void arb_poly_cosh_series(arb_poly_t c, const arb_poly_t h, slong n, slong prec);
0547
0548 void _arb_poly_tanh_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0549 void arb_poly_tanh_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0550
0551 void _arb_poly_sin_cos_series(arb_ptr s, arb_ptr c, arb_srcptr h, slong hlen, slong len, slong prec);
0552 void arb_poly_sin_cos_series(arb_poly_t s, arb_poly_t c, const arb_poly_t h, slong n, slong prec);
0553 void _arb_poly_sin_cos_pi_series(arb_ptr s, arb_ptr c, arb_srcptr h, slong hlen, slong len, slong prec);
0554 void arb_poly_sin_cos_pi_series(arb_poly_t s, arb_poly_t c, const arb_poly_t h, slong n, slong prec);
0555
0556 void _arb_poly_sin_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0557
0558 void arb_poly_sin_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0559
0560 void _arb_poly_cos_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0561
0562 void arb_poly_cos_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0563
0564 void _arb_poly_sin_pi_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0565
0566 void arb_poly_sin_pi_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0567
0568 void _arb_poly_cos_pi_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0569
0570 void arb_poly_cos_pi_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0571
0572 void _arb_poly_cot_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0573 void arb_poly_cot_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0574
0575 void _arb_poly_cot_pi_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0576
0577 void arb_poly_cot_pi_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0578
0579 void _arb_poly_coth_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0580 void arb_poly_coth_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0581
0582 void _arb_poly_tan_series(arb_ptr g, arb_srcptr h, slong hlen, slong len, slong prec);
0583
0584 void arb_poly_tan_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0585
0586 void _arb_poly_tan_pi_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0587 void arb_poly_tan_pi_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0588
0589 void _arb_poly_sinc_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0590 void arb_poly_sinc_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0591
0592 void _arb_poly_sinc_pi_series(arb_ptr g, arb_srcptr h, slong hlen, slong n, slong prec);
0593 void arb_poly_sinc_pi_series(arb_poly_t g, const arb_poly_t h, slong n, slong prec);
0594
0595 void _arb_poly_evaluate_acb_horner(acb_t res, arb_srcptr f, slong len, const acb_t x, slong prec);
0596 void arb_poly_evaluate_acb_horner(acb_t res, const arb_poly_t f, const acb_t a, slong prec);
0597
0598 void _arb_poly_evaluate_acb_rectangular(acb_t y, arb_srcptr poly, slong len, const acb_t x, slong prec);
0599 void arb_poly_evaluate_acb_rectangular(acb_t res, const arb_poly_t f, const acb_t a, slong prec);
0600
0601 void _arb_poly_evaluate_acb(acb_t res, arb_srcptr f, slong len, const acb_t x, slong prec);
0602 void arb_poly_evaluate_acb(acb_t res, const arb_poly_t f, const acb_t a, slong prec);
0603
0604 void _arb_poly_evaluate2_acb_horner(acb_t y, acb_t z, arb_srcptr f, slong len, const acb_t x, slong prec);
0605 void arb_poly_evaluate2_acb_horner(acb_t y, acb_t z, const arb_poly_t f, const acb_t x, slong prec);
0606
0607 void _arb_poly_evaluate2_acb_rectangular(acb_t y, acb_t z, arb_srcptr f, slong len, const acb_t x, slong prec);
0608 void arb_poly_evaluate2_acb_rectangular(acb_t y, acb_t z, const arb_poly_t f, const acb_t x, slong prec);
0609
0610 void _arb_poly_evaluate2_acb(acb_t y, acb_t z, arb_srcptr f, slong len, const acb_t x, slong prec);
0611 void arb_poly_evaluate2_acb(acb_t y, acb_t z, const arb_poly_t f, const acb_t x, slong prec);
0612
0613 void _arb_poly_lambertw_series(arb_ptr res, arb_srcptr z, slong zlen, int flags, slong len, slong prec);
0614 void arb_poly_lambertw_series(arb_poly_t res, const arb_poly_t z, int flags, slong len, slong prec);
0615
0616 void _arb_poly_gamma_series(arb_ptr res, arb_srcptr h, slong hlen, slong len, slong prec);
0617 void arb_poly_gamma_series(arb_poly_t res, const arb_poly_t f, slong n, slong prec);
0618
0619 void _arb_poly_rgamma_series(arb_ptr res, arb_srcptr h, slong hlen, slong len, slong prec);
0620 void arb_poly_rgamma_series(arb_poly_t res, const arb_poly_t f, slong n, slong prec);
0621
0622 void _arb_poly_lgamma_series(arb_ptr res, arb_srcptr h, slong hlen, slong len, slong prec);
0623 void arb_poly_lgamma_series(arb_poly_t res, const arb_poly_t f, slong n, slong prec);
0624
0625 void _arb_poly_digamma_series(arb_ptr res, arb_srcptr h, slong hlen, slong len, slong prec);
0626 void arb_poly_digamma_series(arb_poly_t res, const arb_poly_t f, slong n, slong prec);
0627
0628 void _arb_poly_rising_ui_series(arb_ptr res, arb_srcptr f, slong flen, ulong r, slong trunc, slong prec);
0629 void arb_poly_rising_ui_series(arb_poly_t res, const arb_poly_t f, ulong r, slong trunc, slong prec);
0630
0631 void _arb_poly_zeta_series(arb_ptr res, arb_srcptr h, slong hlen, const arb_t a, int deflate, slong len, slong prec);
0632 void arb_poly_zeta_series(arb_poly_t res, const arb_poly_t f, const arb_t a, int deflate, slong n, slong prec);
0633
0634 void _arb_poly_riemann_siegel_theta_series(arb_ptr res, arb_srcptr h, slong hlen, slong len, slong prec);
0635 void arb_poly_riemann_siegel_theta_series(arb_poly_t res, const arb_poly_t h, slong n, slong prec);
0636
0637 void _arb_poly_riemann_siegel_z_series(arb_ptr res, arb_srcptr h, slong hlen, slong len, slong prec);
0638 void arb_poly_riemann_siegel_z_series(arb_poly_t res, const arb_poly_t h, slong n, slong prec);
0639
0640 slong _arb_poly_swinnerton_dyer_ui_prec(ulong n);
0641 void _arb_poly_swinnerton_dyer_ui(arb_ptr T, ulong n, slong trunc, slong prec);
0642 void arb_poly_swinnerton_dyer_ui(arb_poly_t poly, ulong n, slong prec);
0643
0644 /* Root-finding */
0645
0646 void _arb_poly_newton_convergence_factor(arf_t convergence_factor,
0647     arb_srcptr poly, slong len,
0648     const arb_t convergence_interval, slong prec);
0649
0650 int _arb_poly_newton_step(arb_t xnew, arb_srcptr poly, slong len,
0651     const arb_t x,
0652     const arb_t convergence_interval,
0653     const arf_t convergence_factor, slong prec);
0654
0655 void _arb_poly_newton_refine_root(arb_t r, arb_srcptr poly,
0656     slong len, const arb_t start,
0657     const arb_t convergence_interval,
0658     const arf_t convergence_factor,
0659     slong eval_extra_prec,
0660     slong prec);
0661
0662 void _arb_poly_root_bound_fujiwara(mag_t bound, arb_srcptr poly, slong len);
0663
0664 void arb_poly_root_bound_fujiwara(mag_t bound, arb_poly_t poly);
0665
0666 ARB_POLY_INLINE slong
0667 arb_poly_allocated_bytes(const arb_poly_t x)
0668 {
0669     return _arb_vec_allocated_bytes(x->coeffs, x->alloc);
0670 }
0671
0672 /* Macros */
0673
0674
0675 /* counts zero bits in the binary representation of e */
0676 FLINT_FORCE_INLINE int
0677 n_zerobits(ulong e)
0678 {
0679 #if defined(__GNUC__)
0680 # if FLINT_LONG_LONG
0681     return FLINT_BIT_COUNT(e) - __builtin_popcountll(e);
0682 # else
0683     return FLINT_BIT_COUNT(e) - __builtin_popcountl(e);
0684 # endif
0685 #else
0686     int zeros = 0;
0687     while (e > 1)
0688     {
0689         zeros += !(e & 1);
0690         e >>= 1;
0691     }
0692     return zeros;
0693 #endif
0694 }
0695
0696 /* Computes the length of the result when raising a polynomial of
0697    length *len* to the power *exp* and truncating to length *trunc*,
0698    without overflow. Assumes poly_len >= 1. */
0699 FLINT_FORCE_INLINE slong
0700 poly_pow_length(slong poly_len, ulong exp, slong trunc)
0701 {
0702     ulong hi, lo;
0703     umul_ppmm(hi, lo, poly_len - 1, exp);
0704     add_ssaaaa(hi, lo, hi, lo, 0, 1);
0705     if (hi != 0 || lo > (ulong) WORD_MAX)
0706         return trunc;
0707     return FLINT_MIN((slong) lo, trunc);
0708 }
0709
0710 #ifndef NEWTON_INIT
0711
0712 #define NEWTON_INIT(from, to) \
0713     { \
0714         slong __steps[FLINT_BITS], __i, __from, __to; \
0715         __steps[__i = 0] = __to = (to); \
0716         __from = (from); \
0717         while (__to > __from) \
0718             __steps[++__i] = (__to = (__to + 1) / 2); \
0719
0720 #define NEWTON_BASECASE(bc_to) { slong bc_to = __to;
0721
0722 #define NEWTON_END_BASECASE }
0723
0724 #define NEWTON_LOOP(step_from, step_to) \
0725         { \
0726             for (__i--; __i >= 0; __i--) \
0727             { \
0728                 slong step_from = __steps[__i+1]; \
0729                 slong step_to = __steps[__i]; \
0730
0731 #define NEWTON_END_LOOP }}
0732
0733 #define NEWTON_END }
0734
0735 #endif
0736
0737 #ifdef __cplusplus
0738 }
0739 #endif
0740
0741 #endif