1 /*
2     Copyright (C) 2012 Fredrik Johansson
3 
4     This file is part of Arb.
5 
6     Arb is free software: you can redistribute it and/or modify it under
7     the terms of the GNU Lesser General Public License (LGPL) as published
8     by the Free Software Foundation; either version 2.1 of the License, or
9     (at your option) any later version.  See <http://www.gnu.org/licenses/>.
10 */
11 
12 #ifndef ACB_POLY_H
13 #define ACB_POLY_H
14 
15 #ifdef ACB_POLY_INLINES_C
16 #define ACB_POLY_INLINE
17 #else
18 #define ACB_POLY_INLINE static __inline__
19 #endif
20 
21 #include <stdio.h>
22 #include "acb.h"
23 #include "arb_poly.h"
24 
25 #ifdef __cplusplus
26 extern "C" {
27 #endif
28 
29 typedef struct
30 {
31     acb_ptr coeffs;
32     slong length;
33     slong alloc;
34 }
35 acb_poly_struct;
36 
37 typedef acb_poly_struct acb_poly_t[1];
38 
39 
40 /* Memory management */
41 
42 void acb_poly_init(acb_poly_t poly);
43 
44 void acb_poly_init2(acb_poly_t poly, slong len);
45 
46 void acb_poly_clear(acb_poly_t poly);
47 
48 void acb_poly_fit_length(acb_poly_t poly, slong len);
49 
50 void _acb_poly_set_length(acb_poly_t poly, slong len);
51 
52 void _acb_poly_normalise(acb_poly_t poly);
53 
54 ACB_POLY_INLINE void
acb_poly_swap(acb_poly_t poly1,acb_poly_t poly2)55 acb_poly_swap(acb_poly_t poly1, acb_poly_t poly2)
56 {
57     acb_poly_struct t = *poly1;
58     *poly1 = *poly2;
59     *poly2 = t;
60 }
61 
acb_poly_length(const acb_poly_t poly)62 ACB_POLY_INLINE slong acb_poly_length(const acb_poly_t poly)
63 {
64     return poly->length;
65 }
66 
acb_poly_degree(const acb_poly_t poly)67 ACB_POLY_INLINE slong acb_poly_degree(const acb_poly_t poly)
68 {
69     return poly->length - 1;
70 }
71 
72 slong acb_poly_valuation(const acb_poly_t poly);
73 
74 ACB_POLY_INLINE int
acb_poly_is_zero(const acb_poly_t z)75 acb_poly_is_zero(const acb_poly_t z)
76 {
77     return acb_poly_length(z) == 0;
78 }
79 
80 ACB_POLY_INLINE int
acb_poly_is_one(const acb_poly_t z)81 acb_poly_is_one(const acb_poly_t z)
82 {
83     return (acb_poly_length(z) == 1) && acb_is_one(z->coeffs);
84 }
85 
86 ACB_POLY_INLINE int
acb_poly_is_x(const acb_poly_t z)87 acb_poly_is_x(const acb_poly_t z)
88 {
89     return (acb_poly_length(z) == 2) && acb_is_zero(z->coeffs)
90         && acb_is_one(z->coeffs + 1);
91 }
92 
acb_poly_zero(acb_poly_t poly)93 ACB_POLY_INLINE void acb_poly_zero(acb_poly_t poly)
94 {
95     poly->length = 0;
96 }
97 
98 ACB_POLY_INLINE void
acb_poly_one(acb_poly_t poly)99 acb_poly_one(acb_poly_t poly)
100 {
101     acb_poly_fit_length(poly, 1);
102     acb_one(poly->coeffs);
103     _acb_poly_set_length(poly, 1);
104 }
105 
106 void acb_poly_set_coeff_si(acb_poly_t poly, slong n, slong x);
107 
108 void acb_poly_set_coeff_acb(acb_poly_t poly, slong n, const acb_t x);
109 
110 void acb_poly_get_coeff_acb(acb_t x, const acb_poly_t poly, slong n);
111 
112 #define acb_poly_get_coeff_ptr(poly, n) \
113     ((n) < (poly)->length ? (poly)->coeffs + (n) : NULL)
114 
115 void _acb_poly_shift_right(acb_ptr res, acb_srcptr poly, slong len, slong n);
116 
117 void acb_poly_shift_right(acb_poly_t res, const acb_poly_t poly, slong n);
118 
119 void _acb_poly_shift_left(acb_ptr res, acb_srcptr poly, slong len, slong n);
120 
121 void acb_poly_shift_left(acb_poly_t res, const acb_poly_t poly, slong n);
122 
123 ACB_POLY_INLINE void
acb_poly_truncate(acb_poly_t poly,slong newlen)124 acb_poly_truncate(acb_poly_t poly, slong newlen)
125 {
126     if (poly->length > newlen)
127     {
128         slong i;
129         for (i = newlen; i < poly->length; i++)
130             acb_zero(poly->coeffs + i);
131         poly->length = newlen;
132         _acb_poly_normalise(poly);
133     }
134 }
135 
136 void _acb_poly_majorant(arb_ptr res, acb_srcptr vec, slong len, slong prec);
137 
138 void acb_poly_majorant(arb_poly_t res, const acb_poly_t poly, slong prec);
139 
140 void acb_poly_fprintd(FILE * file, const acb_poly_t poly, slong digits);
141 
142 ACB_POLY_INLINE void
acb_poly_printd(const acb_poly_t poly,slong digits)143 acb_poly_printd(const acb_poly_t poly, slong digits)
144 {
145     acb_poly_fprintd(stdout, poly, digits);
146 }
147 
148 void _acb_poly_evaluate_horner(acb_t res, acb_srcptr f, slong len, const acb_t a, slong prec);
149 void acb_poly_evaluate_horner(acb_t res, const acb_poly_t f, const acb_t a, slong prec);
150 
151 void _acb_poly_evaluate_rectangular(acb_t y, acb_srcptr poly, slong len, const acb_t x, slong prec);
152 void acb_poly_evaluate_rectangular(acb_t res, const acb_poly_t f, const acb_t a, slong prec);
153 
154 void _acb_poly_evaluate(acb_t res, acb_srcptr f, slong len, const acb_t a, slong prec);
155 void acb_poly_evaluate(acb_t res, const acb_poly_t f, const acb_t a, slong prec);
156 
157 void _acb_poly_evaluate2_horner(acb_t y, acb_t z, acb_srcptr f, slong len, const acb_t x, slong prec);
158 void acb_poly_evaluate2_horner(acb_t y, acb_t z, const acb_poly_t f, const acb_t x, slong prec);
159 
160 void _acb_poly_evaluate2_rectangular(acb_t y, acb_t z, acb_srcptr f, slong len, const acb_t x, slong prec);
161 void acb_poly_evaluate2_rectangular(acb_t y, acb_t z, const acb_poly_t f, const acb_t x, slong prec);
162 
163 void _acb_poly_evaluate2(acb_t y, acb_t z, acb_srcptr f, slong len, const acb_t x, slong prec);
164 void acb_poly_evaluate2(acb_t y, acb_t z, const acb_poly_t f, const acb_t x, slong prec);
165 
166 void _acb_poly_derivative(acb_ptr res, acb_srcptr poly, slong len, slong prec);
167 
168 void acb_poly_derivative(acb_poly_t res, const acb_poly_t poly, slong prec);
169 
170 void _acb_poly_integral(acb_ptr res, acb_srcptr poly, slong len, slong prec);
171 
172 void acb_poly_integral(acb_poly_t res, const acb_poly_t poly, slong prec);
173 
174 /* Transforms */
175 
176 void acb_poly_borel_transform(acb_poly_t res, const acb_poly_t poly, slong prec);
177 
178 void _acb_poly_borel_transform(acb_ptr res, acb_srcptr poly, slong len, slong prec);
179 
180 void acb_poly_inv_borel_transform(acb_poly_t res, const acb_poly_t poly, slong prec);
181 
182 void _acb_poly_inv_borel_transform(acb_ptr res, acb_srcptr poly, slong len, slong prec);
183 
184 void _acb_poly_binomial_transform_basecase(acb_ptr b, acb_srcptr a, slong alen, slong len, slong prec);
185 
186 void acb_poly_binomial_transform_basecase(acb_poly_t b, const acb_poly_t a, slong len, slong prec);
187 
188 void _acb_poly_binomial_transform_convolution(acb_ptr b, acb_srcptr a, slong alen, slong len, slong prec);
189 
190 void acb_poly_binomial_transform_convolution(acb_poly_t b, const acb_poly_t a, slong len, slong prec);
191 
192 void _acb_poly_binomial_transform(acb_ptr b, acb_srcptr a, slong alen, slong len, slong prec);
193 
194 void acb_poly_binomial_transform(acb_poly_t b, const acb_poly_t a, slong len, slong prec);
195 
196 void _acb_poly_graeffe_transform(acb_ptr b, acb_srcptr a, slong len, slong prec);
197 
198 void acb_poly_graeffe_transform(acb_poly_t b, const acb_poly_t a, slong prec);
199 
200 
201 
202 void acb_poly_set(acb_poly_t dest, const acb_poly_t src);
203 
204 void acb_poly_set_round(acb_poly_t dest, const acb_poly_t src, slong prec);
205 
206 void acb_poly_set_trunc(acb_poly_t res, const acb_poly_t poly, slong n);
207 
208 void acb_poly_set_trunc_round(acb_poly_t res, const acb_poly_t poly, slong n, slong prec);
209 
210 void acb_poly_set_arb_poly(acb_poly_t poly, const arb_poly_t re);
211 
212 void acb_poly_set2_arb_poly(acb_poly_t poly, const arb_poly_t re, const arb_poly_t im);
213 
214 void acb_poly_set_fmpq_poly(acb_poly_t poly, const fmpq_poly_t re, slong prec);
215 
216 void acb_poly_set2_fmpq_poly(acb_poly_t poly, const fmpq_poly_t re, const fmpq_poly_t im, slong prec);
217 
218 void acb_poly_set_fmpz_poly(acb_poly_t poly, const fmpz_poly_t src, slong prec);
219 
220 void acb_poly_set2_fmpz_poly(acb_poly_t poly, const fmpz_poly_t re, const fmpz_poly_t im, slong prec);
221 
222 int acb_poly_get_unique_fmpz_poly(fmpz_poly_t res, const acb_poly_t src);
223 
224 ACB_POLY_INLINE void
acb_poly_set_acb(acb_poly_t poly,const acb_t c)225 acb_poly_set_acb(acb_poly_t poly, const acb_t c)
226 {
227     acb_poly_fit_length(poly, 1);
228     acb_set(poly->coeffs, c);
229     _acb_poly_set_length(poly, !acb_is_zero(poly->coeffs));
230 }
231 
232 void acb_poly_set_si(acb_poly_t poly, slong c);
233 
234 void acb_poly_randtest(acb_poly_t poly, flint_rand_t state, slong len, slong prec, slong mag_bits);
235 
236 int acb_poly_equal(const acb_poly_t A, const acb_poly_t B);
237 
238 int acb_poly_contains_fmpz_poly(const acb_poly_t poly1, const fmpz_poly_t poly2);
239 
240 int acb_poly_contains_fmpq_poly(const acb_poly_t poly1, const fmpq_poly_t poly2);
241 
242 int _acb_poly_overlaps(acb_srcptr poly1, slong len1,
243         acb_srcptr poly2, slong len2);
244 
245 int acb_poly_overlaps(const acb_poly_t poly1, const acb_poly_t poly2);
246 
247 int acb_poly_contains(const acb_poly_t poly1, const acb_poly_t poly2);
248 
249 ACB_POLY_INLINE int
acb_poly_is_real(const acb_poly_t poly)250 acb_poly_is_real(const acb_poly_t poly)
251 {
252     return _acb_vec_is_real(poly->coeffs, poly->length);
253 }
254 
255 void _acb_poly_add(acb_ptr res, acb_srcptr poly1, slong len1,
256     acb_srcptr poly2, slong len2, slong prec);
257 
258 void acb_poly_add(acb_poly_t res, const acb_poly_t poly1,
259               const acb_poly_t poly2, slong prec);
260 
261 void acb_poly_add_si(acb_poly_t res, const acb_poly_t poly, slong c, slong prec);
262 
263 void _acb_poly_sub(acb_ptr res, acb_srcptr poly1, slong len1,
264     acb_srcptr poly2, slong len2, slong prec);
265 
266 void acb_poly_sub(acb_poly_t res, const acb_poly_t poly1,
267               const acb_poly_t poly2, slong prec);
268 
269 void acb_poly_add_series(acb_poly_t res, const acb_poly_t poly1,
270               const acb_poly_t poly2, slong len, slong prec);
271 
272 void acb_poly_sub_series(acb_poly_t res, const acb_poly_t poly1,
273               const acb_poly_t poly2, slong len, slong prec);
274 
275 ACB_POLY_INLINE void
acb_poly_neg(acb_poly_t res,const acb_poly_t poly)276 acb_poly_neg(acb_poly_t res, const acb_poly_t poly)
277 {
278     acb_poly_fit_length(res, poly->length);
279     _acb_vec_neg(res->coeffs, poly->coeffs, poly->length);
280     _acb_poly_set_length(res, poly->length);
281 }
282 
283 ACB_POLY_INLINE void
acb_poly_scalar_mul_2exp_si(acb_poly_t res,const acb_poly_t poly,slong c)284 acb_poly_scalar_mul_2exp_si(acb_poly_t res, const acb_poly_t poly, slong c)
285 {
286     acb_poly_fit_length(res, poly->length);
287     _acb_vec_scalar_mul_2exp_si(res->coeffs, poly->coeffs, poly->length, c);
288     _acb_poly_set_length(res, poly->length);
289 }
290 
291 ACB_POLY_INLINE void
acb_poly_scalar_mul(acb_poly_t res,const acb_poly_t poly,const acb_t c,slong prec)292 acb_poly_scalar_mul(acb_poly_t res, const acb_poly_t poly, const acb_t c, slong prec)
293 {
294     acb_poly_fit_length(res, poly->length);
295     _acb_vec_scalar_mul(res->coeffs, poly->coeffs, poly->length, c, prec);
296     _acb_poly_set_length(res, poly->length);
297     _acb_poly_normalise(res);
298 }
299 
300 ACB_POLY_INLINE void
acb_poly_scalar_div(acb_poly_t res,const acb_poly_t poly,const acb_t c,slong prec)301 acb_poly_scalar_div(acb_poly_t res, const acb_poly_t poly, const acb_t c, slong prec)
302 {
303     acb_poly_fit_length(res, poly->length);
304     _acb_vec_scalar_div(res->coeffs, poly->coeffs, poly->length, c, prec);
305     _acb_poly_set_length(res, poly->length);
306     _acb_poly_normalise(res);
307 }
308 
309 void acb_poly_mullow_classical(acb_poly_t res, const acb_poly_t poly1,
310                                             const acb_poly_t poly2,
311                                                 slong n, slong prec);
312 
313 void _acb_poly_mullow_classical(acb_ptr res,
314     acb_srcptr poly1, slong len1,
315     acb_srcptr poly2, slong len2, slong n, slong prec);
316 
317 void _acb_poly_mullow_transpose(acb_ptr res,
318     acb_srcptr poly1, slong len1,
319     acb_srcptr poly2, slong len2, slong n, slong prec);
320 
321 void acb_poly_mullow_transpose(acb_poly_t res, const acb_poly_t poly1,
322                                             const acb_poly_t poly2,
323                                                 slong n, slong prec);
324 
325 void _acb_poly_mullow_transpose_gauss(acb_ptr res,
326     acb_srcptr poly1, slong len1,
327     acb_srcptr poly2, slong len2, slong n, slong prec);
328 
329 void acb_poly_mullow_transpose_gauss(acb_poly_t res, const acb_poly_t poly1,
330                                             const acb_poly_t poly2,
331                                                 slong n, slong prec);
332 
333 void _acb_poly_mullow(acb_ptr res,
334     acb_srcptr poly1, slong len1,
335     acb_srcptr poly2, slong len2, slong n, slong prec);
336 
337 void acb_poly_mullow(acb_poly_t res, const acb_poly_t poly1,
338                                             const acb_poly_t poly2,
339                                                 slong n, slong prec);
340 
341 void _acb_poly_mul(acb_ptr C,
342     acb_srcptr A, slong lenA,
343     acb_srcptr B, slong lenB, slong prec);
344 
345 void acb_poly_mul(acb_poly_t res, const acb_poly_t poly1,
346               const acb_poly_t poly2, slong prec);
347 
348 ACB_POLY_INLINE void
_acb_poly_mul_monic(acb_ptr res,acb_srcptr poly1,slong len1,acb_srcptr poly2,slong len2,slong prec)349 _acb_poly_mul_monic(acb_ptr res, acb_srcptr poly1, slong len1,
350     acb_srcptr poly2, slong len2, slong prec)
351 {
352     if (len1 + len2 - 2 > 0)
353         _acb_poly_mullow(res, poly1, len1, poly2, len2, len1 + len2 - 2, prec);
354     acb_one(res + len1 + len2 - 2);
355 }
356 
357 void _acb_poly_inv_series(acb_ptr Qinv, acb_srcptr Q, slong Qlen, slong len, slong prec);
358 
359 void acb_poly_inv_series(acb_poly_t Qinv, const acb_poly_t Q, slong n, slong prec);
360 
361 void  _acb_poly_div_series(acb_ptr Q, acb_srcptr A, slong Alen,
362     acb_srcptr B, slong Blen, slong n, slong prec);
363 
364 void acb_poly_div_series(acb_poly_t Q, const acb_poly_t A, const acb_poly_t B, slong n, slong prec);
365 
366 void _acb_poly_reverse(acb_ptr res, acb_srcptr poly, slong len, slong n);
367 
368 void _acb_poly_div(acb_ptr Q,
369     acb_srcptr A, slong lenA,
370     acb_srcptr B, slong lenB, slong prec);
371 
372 void _acb_poly_divrem(acb_ptr Q, acb_ptr R,
373     acb_srcptr A, slong lenA,
374     acb_srcptr B, slong lenB, slong prec);
375 
376 void _acb_poly_rem(acb_ptr R,
377     acb_srcptr A, slong lenA,
378     acb_srcptr B, slong lenB, slong prec);
379 
380 int acb_poly_divrem(acb_poly_t Q, acb_poly_t R,
381                              const acb_poly_t A, const acb_poly_t B, slong prec);
382 
383 void _acb_poly_div_root(acb_ptr Q, acb_t R, acb_srcptr A,
384     slong len, const acb_t c, slong prec);
385 
386 /* Composition */
387 
388 void _acb_poly_taylor_shift_horner(acb_ptr poly, const acb_t c, slong n, slong prec);
389 
390 void acb_poly_taylor_shift_horner(acb_poly_t g, const acb_poly_t f, const acb_t c, slong prec);
391 
392 void _acb_poly_taylor_shift_divconquer(acb_ptr poly, const acb_t c, slong n, slong prec);
393 
394 void acb_poly_taylor_shift_divconquer(acb_poly_t g, const acb_poly_t f, const acb_t c, slong prec);
395 
396 void _acb_poly_taylor_shift_convolution(acb_ptr poly, const acb_t c, slong n, slong prec);
397 
398 void acb_poly_taylor_shift_convolution(acb_poly_t g, const acb_poly_t f, const acb_t c, slong prec);
399 
400 void _acb_poly_taylor_shift(acb_ptr poly, const acb_t c, slong n, slong prec);
401 
402 void acb_poly_taylor_shift(acb_poly_t g, const acb_poly_t f, const acb_t c, slong prec);
403 
404 void _acb_poly_compose(acb_ptr res,
405     acb_srcptr poly1, slong len1,
406     acb_srcptr poly2, slong len2, slong prec);
407 
408 void acb_poly_compose(acb_poly_t res,
409               const acb_poly_t poly1, const acb_poly_t poly2, slong prec);
410 
411 void _acb_poly_compose_horner(acb_ptr res,
412     acb_srcptr poly1, slong len1,
413     acb_srcptr poly2, slong len2, slong prec);
414 
415 void acb_poly_compose_horner(acb_poly_t res,
416               const acb_poly_t poly1, const acb_poly_t poly2, slong prec);
417 
418 void _acb_poly_compose_divconquer(acb_ptr res,
419     acb_srcptr poly1, slong len1,
420     acb_srcptr poly2, slong len2, slong prec);
421 
422 void acb_poly_compose_divconquer(acb_poly_t res,
423               const acb_poly_t poly1, const acb_poly_t poly2, slong prec);
424 
425 void _acb_poly_compose_series_horner(acb_ptr res, acb_srcptr poly1, slong len1,
426                             acb_srcptr poly2, slong len2, slong n, slong prec);
427 
428 void acb_poly_compose_series_horner(acb_poly_t res,
429                     const acb_poly_t poly1,
430                     const acb_poly_t poly2, slong n, slong prec);
431 
432 void _acb_poly_compose_series_brent_kung(acb_ptr res, acb_srcptr poly1, slong len1,
433                             acb_srcptr poly2, slong len2, slong n, slong prec);
434 
435 void acb_poly_compose_series_brent_kung(acb_poly_t res,
436                     const acb_poly_t poly1,
437                     const acb_poly_t poly2, slong n, slong prec);
438 
439 void _acb_poly_compose_series(acb_ptr res, acb_srcptr poly1, slong len1,
440                             acb_srcptr poly2, slong len2, slong n, slong prec);
441 
442 void acb_poly_compose_series(acb_poly_t res,
443                     const acb_poly_t poly1,
444                     const acb_poly_t poly2, slong n, slong prec);
445 
446 /* Reversion */
447 
448 void _acb_poly_revert_series_lagrange(acb_ptr Qinv, acb_srcptr Q, slong Qlen, slong n, slong prec);
449 void acb_poly_revert_series_lagrange(acb_poly_t Qinv, const acb_poly_t Q, slong n, slong prec);
450 
451 void _acb_poly_revert_series_newton(acb_ptr Qinv, acb_srcptr Q, slong Qlen, slong n, slong prec);
452 void acb_poly_revert_series_newton(acb_poly_t Qinv, const acb_poly_t Q, slong n, slong prec);
453 
454 void _acb_poly_revert_series_lagrange_fast(acb_ptr Qinv, acb_srcptr Q, slong Qlen, slong n, slong prec);
455 void acb_poly_revert_series_lagrange_fast(acb_poly_t Qinv, const acb_poly_t Q, slong n, slong prec);
456 
457 void _acb_poly_revert_series(acb_ptr Qinv, acb_srcptr Q, slong Qlen, slong n, slong prec);
458 void acb_poly_revert_series(acb_poly_t Qinv, const acb_poly_t Q, slong n, slong prec);
459 
460 
461 
462 void
463 _acb_poly_evaluate_vec_fast_precomp(acb_ptr vs, acb_srcptr poly,
464     slong plen, acb_ptr * tree, slong len, slong prec);
465 
466 void _acb_poly_evaluate_vec_fast(acb_ptr ys, acb_srcptr poly, slong plen,
467     acb_srcptr xs, slong n, slong prec);
468 
469 void
470 acb_poly_evaluate_vec_fast(acb_ptr ys,
471         const acb_poly_t poly, acb_srcptr xs, slong n, slong prec);
472 
473 void
474 _acb_poly_evaluate_vec_iter(acb_ptr ys, acb_srcptr poly, slong plen,
475     acb_srcptr xs, slong n, slong prec);
476 
477 void
478 acb_poly_evaluate_vec_iter(acb_ptr ys,
479         const acb_poly_t poly, acb_srcptr xs, slong n, slong prec);
480 
481 void
482 _acb_poly_interpolate_barycentric(acb_ptr poly,
483     acb_srcptr xs, acb_srcptr ys, slong n, slong prec);
484 
485 void
486 acb_poly_interpolate_barycentric(acb_poly_t poly,
487     acb_srcptr xs, acb_srcptr ys, slong n, slong prec);
488 
489 void
490 _acb_poly_interpolation_weights(acb_ptr w,
491     acb_ptr * tree, slong len, slong prec);
492 
493 void
494 _acb_poly_interpolate_fast_precomp(acb_ptr poly,
495     acb_srcptr ys, acb_ptr * tree, acb_srcptr weights,
496     slong len, slong prec);
497 
498 void
499 _acb_poly_interpolate_fast(acb_ptr poly,
500     acb_srcptr xs, acb_srcptr ys, slong len, slong prec);
501 
502 void
503 acb_poly_interpolate_fast(acb_poly_t poly,
504         acb_srcptr xs, acb_srcptr ys, slong n, slong prec);
505 
506 void
507 _acb_poly_interpolate_newton(acb_ptr poly, acb_srcptr xs,
508     acb_srcptr ys, slong n, slong prec);
509 
510 void
511 acb_poly_interpolate_newton(acb_poly_t poly,
512     acb_srcptr xs, acb_srcptr ys, slong n, slong prec);
513 
514 void
515 _acb_poly_product_roots(acb_ptr poly, acb_srcptr xs, slong n, slong prec);
516 
517 void
518 acb_poly_product_roots(acb_poly_t poly, acb_srcptr xs, slong n, slong prec);
519 
520 acb_ptr * _acb_poly_tree_alloc(slong len);
521 
522 void _acb_poly_tree_free(acb_ptr * tree, slong len);
523 
524 void
525 _acb_poly_tree_build(acb_ptr * tree, acb_srcptr roots, slong len, slong prec);
526 
527 
528 void _acb_poly_root_inclusion(acb_t r, const acb_t m,
529     acb_srcptr poly,
530     acb_srcptr polyder, slong len, slong prec);
531 
532 slong _acb_poly_validate_roots(acb_ptr roots,
533         acb_srcptr poly, slong len, slong prec);
534 
535 void _acb_poly_refine_roots_durand_kerner(acb_ptr roots,
536         acb_srcptr poly, slong len, slong prec);
537 
538 slong _acb_poly_find_roots(acb_ptr roots,
539     acb_srcptr poly,
540     acb_srcptr initial, slong len, slong maxiter, slong prec);
541 
542 slong acb_poly_find_roots(acb_ptr roots,
543     const acb_poly_t poly, acb_srcptr initial,
544     slong maxiter, slong prec);
545 
546 void _acb_poly_root_bound_fujiwara(mag_t bound, acb_srcptr poly, slong len);
547 
548 void acb_poly_root_bound_fujiwara(mag_t bound, acb_poly_t poly);
549 
550 int _acb_poly_validate_real_roots(acb_srcptr roots, acb_srcptr poly, slong len, slong prec);
551 
552 int acb_poly_validate_real_roots(acb_srcptr roots, const acb_poly_t poly, slong prec);
553 
554 /* Special functions */
555 
556 void _acb_poly_pow_ui_trunc_binexp(acb_ptr res,
557     acb_srcptr f, slong flen, ulong exp, slong len, slong prec);
558 
559 void acb_poly_pow_ui_trunc_binexp(acb_poly_t res,
560     const acb_poly_t poly, ulong exp, slong len, slong prec);
561 
562 void _acb_poly_pow_ui(acb_ptr res, acb_srcptr f, slong flen, ulong exp, slong prec);
563 
564 void acb_poly_pow_ui(acb_poly_t res, const acb_poly_t poly, ulong exp, slong prec);
565 
566 void _acb_poly_rsqrt_series(acb_ptr g, acb_srcptr h, slong hlen, slong len, slong prec);
567 
568 void acb_poly_rsqrt_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
569 
570 void _acb_poly_sqrt_series(acb_ptr g, acb_srcptr h, slong hlen, slong len, slong prec);
571 
572 void acb_poly_sqrt_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
573 
574 void _acb_poly_log_series(acb_ptr res, acb_srcptr f, slong flen, slong n, slong prec);
575 void acb_poly_log_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
576 
577 void _acb_poly_log1p_series(acb_ptr res, acb_srcptr f, slong flen, slong n, slong prec);
578 void acb_poly_log1p_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
579 
580 void _acb_poly_atan_series(acb_ptr res, acb_srcptr f, slong flen, slong n, slong prec);
581 
582 void acb_poly_atan_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
583 
584 void _acb_poly_exp_series_basecase(acb_ptr f, acb_srcptr h, slong hlen, slong n, slong prec);
585 void acb_poly_exp_series_basecase(acb_poly_t f, const acb_poly_t h, slong n, slong prec);
586 void _acb_poly_exp_series(acb_ptr f, acb_srcptr h, slong hlen, slong n, slong prec);
587 void acb_poly_exp_series(acb_poly_t f, const acb_poly_t h, slong n, slong prec);
588 
589 void _acb_poly_exp_pi_i_series(acb_ptr f, acb_srcptr h, slong hlen, slong n, slong prec);
590 void acb_poly_exp_pi_i_series(acb_poly_t f, const acb_poly_t h, slong n, slong prec);
591 
592 void _acb_poly_sinh_cosh_series_basecase(acb_ptr s, acb_ptr c, const acb_srcptr h, slong hlen, slong n, slong prec);
593 void acb_poly_sinh_cosh_series_basecase(acb_poly_t s, acb_poly_t c, const acb_poly_t h, slong n, slong prec);
594 void _acb_poly_sinh_cosh_series_exponential(acb_ptr s, acb_ptr c, const acb_srcptr h, slong hlen, slong n, slong prec);
595 void acb_poly_sinh_cosh_series_exponential(acb_poly_t s, acb_poly_t c, const acb_poly_t h, slong n, slong prec);
596 void _acb_poly_sinh_cosh_series(acb_ptr s, acb_ptr c, const acb_srcptr h, slong hlen, slong n, slong prec);
597 void acb_poly_sinh_cosh_series(acb_poly_t s, acb_poly_t c, const acb_poly_t h, slong n, slong prec);
598 
599 void _acb_poly_sinh_series(acb_ptr s, acb_srcptr h, slong hlen, slong n, slong prec);
600 void acb_poly_sinh_series(acb_poly_t s, const acb_poly_t h, slong n, slong prec);
601 
602 void _acb_poly_cosh_series(acb_ptr c, acb_srcptr h, slong hlen, slong n, slong prec);
603 void acb_poly_cosh_series(acb_poly_t c, const acb_poly_t h, slong n, slong prec);
604 
605 
606 void _acb_poly_sin_cos_series_basecase(acb_ptr s,
607                                     acb_ptr c, acb_srcptr h, slong hlen, slong n, slong prec, int times_pi);
608 
609 void acb_poly_sin_cos_series_basecase(acb_poly_t s, acb_poly_t c,
610         const acb_poly_t h, slong n, slong prec, int times_pi);
611 
612 void _acb_poly_sin_cos_series_tangent(acb_ptr s, acb_ptr c,
613                         const acb_srcptr h, slong hlen, slong len, slong prec, int times_pi);
614 
615 void acb_poly_sin_cos_series_tangent(acb_poly_t s, acb_poly_t c,
616                                     const acb_poly_t h, slong n, slong prec, int times_pi);
617 
618 void _acb_poly_sin_cos_series(acb_ptr s, acb_ptr c,
619                         const acb_srcptr h, slong hlen, slong len, slong prec);
620 
621 void acb_poly_sin_cos_series(acb_poly_t s, acb_poly_t c,
622                                     const acb_poly_t h, slong n, slong prec);
623 
624 void _acb_poly_sin_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
625 
626 void acb_poly_sin_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
627 
628 void _acb_poly_cos_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
629 
630 void acb_poly_cos_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
631 
632 void _acb_poly_sin_cos_pi_series(acb_ptr s, acb_ptr c,
633                         const acb_srcptr h, slong hlen, slong len, slong prec);
634 
635 void acb_poly_sin_cos_pi_series(acb_poly_t s, acb_poly_t c,
636                                     const acb_poly_t h, slong n, slong prec);
637 
638 void _acb_poly_sin_pi_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
639 
640 void acb_poly_sin_pi_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
641 
642 void _acb_poly_cos_pi_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
643 
644 void acb_poly_cos_pi_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
645 
646 void _acb_poly_cot_pi_series(acb_ptr g, acb_srcptr h, slong hlen, slong len, slong prec);
647 
648 void acb_poly_cot_pi_series(acb_poly_t res, const acb_poly_t f, slong len, slong prec);
649 
650 void _acb_poly_tan_series(acb_ptr g, acb_srcptr h, slong hlen, slong len, slong prec);
651 
652 void acb_poly_tan_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
653 
654 void _acb_poly_sinc_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
655 void acb_poly_sinc_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
656 
657 void _acb_poly_lambertw_series(acb_ptr res, acb_srcptr z, slong zlen, const fmpz_t k, int flags, slong len, slong prec);
658 void acb_poly_lambertw_series(acb_poly_t res, const acb_poly_t z, const fmpz_t k, int flags, slong len, slong prec);
659 
660 void _acb_poly_gamma_series(acb_ptr res, acb_srcptr h, slong hlen, slong len, slong prec);
661 
662 void acb_poly_gamma_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
663 
664 void _acb_poly_rgamma_series(acb_ptr res, acb_srcptr h, slong hlen, slong len, slong prec);
665 
666 void acb_poly_rgamma_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
667 
668 void _acb_poly_lgamma_series(acb_ptr res, acb_srcptr h, slong hlen, slong len, slong prec);
669 
670 void acb_poly_lgamma_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
671 
672 void _acb_poly_digamma_series(acb_ptr res, acb_srcptr h, slong hlen, slong len, slong prec);
673 
674 void acb_poly_digamma_series(acb_poly_t res, const acb_poly_t f, slong n, slong prec);
675 
676 void _acb_poly_rising_ui_series(acb_ptr res, acb_srcptr f, slong flen, ulong r, slong trunc, slong prec);
677 
678 void acb_poly_rising_ui_series(acb_poly_t res, const acb_poly_t f, ulong r, slong trunc, slong prec);
679 
680 void _acb_poly_pow_acb_series(acb_ptr h,
681     acb_srcptr f, slong flen, const acb_t g, slong len, slong prec);
682 
683 void acb_poly_pow_acb_series(acb_poly_t h,
684     const acb_poly_t f, const acb_t g, slong len, slong prec);
685 
686 void _acb_poly_pow_series(acb_ptr h,
687     acb_srcptr f, slong flen,
688     acb_srcptr g, slong glen, slong len, slong prec);
689 
690 void acb_poly_pow_series(acb_poly_t h,
691     const acb_poly_t f, const acb_poly_t g, slong len, slong prec);
692 
693 void
694 _acb_poly_binomial_pow_acb_series(acb_ptr h, acb_srcptr f, slong flen,
695     const acb_t g, slong len, slong prec);
696 
697 /* TODO: document */
698 ACB_POLY_INLINE void
_acb_poly_acb_pow_cpx(acb_ptr w,const acb_t a,const acb_t b,slong len,slong prec)699 _acb_poly_acb_pow_cpx(acb_ptr w, const acb_t a, const acb_t b, slong len, slong prec)
700 {
701     if (len == 1)
702     {
703         acb_pow(w, a, b, prec);
704     }
705     else
706     {
707         acb_t log_a;
708         slong k;
709 
710         acb_init(log_a);
711 
712         acb_log(log_a, a, prec);
713         acb_mul(w, log_a, b, prec);
714         acb_exp(w, w, prec);
715 
716         for (k = 1; k < len; k++)
717         {
718             acb_mul(w + k, w + k - 1, log_a, prec);
719             acb_div_ui(w + k, w + k, k, prec);
720         }
721 
722         acb_clear(log_a);
723     }
724 }
725 
726 #define _acb_poly_pow_cpx _acb_poly_acb_pow_cpx
727 
728 /* TODO: document */
729 void _acb_poly_acb_invpow_cpx(acb_ptr res, const acb_t N, const acb_t c, slong trunc, slong prec);
730 /* TODO: document */
731 void _acb_poly_mullow_cpx(acb_ptr res, acb_srcptr src, slong len, const acb_t c, slong trunc, slong prec);
732 
733 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);
734 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);
735 void _acb_poly_powsum_one_series_sieved(acb_ptr z, const acb_t s, slong n, slong len, slong prec);
736 
737 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);
738 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);
739 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);
740 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);
741 
742 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);
743 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);
744 
745 void _acb_poly_zeta_cpx_series(acb_ptr z, const acb_t s, const acb_t a, int deflate, slong d, slong prec);
746 
747 void _acb_poly_zeta_series(acb_ptr res, acb_srcptr h, slong hlen, const acb_t a, int deflate, slong len, slong prec);
748 
749 void acb_poly_zeta_series(acb_poly_t res, const acb_poly_t f, const acb_t a, int deflate, slong n, slong prec);
750 
751 void _acb_poly_polylog_cpx_zeta(acb_ptr w, const acb_t s, const acb_t z, slong len, slong prec);
752 void _acb_poly_polylog_cpx_small(acb_ptr w, const acb_t s, const acb_t z, slong len, slong prec);
753 void _acb_poly_polylog_cpx(acb_ptr w, const acb_t s, const acb_t z, slong len, slong prec);
754 
755 void _acb_poly_polylog_series(acb_ptr res, acb_srcptr s, slong slen, const acb_t z, slong len, slong prec);
756 void acb_poly_polylog_series(acb_poly_t res, const acb_poly_t s, const acb_t z, slong n, slong prec);
757 
758 void _acb_poly_agm1_series(acb_ptr res, acb_srcptr z, slong zlen, slong len, slong prec);
759 void acb_poly_agm1_series(acb_poly_t res, const acb_poly_t z, slong n, slong prec);
760 void _acb_poly_elliptic_k_series(acb_ptr res, acb_srcptr z, slong zlen, slong len, slong prec);
761 void acb_poly_elliptic_k_series(acb_poly_t res, const acb_poly_t z, slong n, slong prec);
762 void _acb_poly_elliptic_p_series(acb_ptr res, acb_srcptr z, slong zlen, const acb_t tau, slong len, slong prec);
763 void acb_poly_elliptic_p_series(acb_poly_t res, const acb_poly_t z, const acb_t tau, slong n, slong prec);
764 
765 void _acb_poly_erf_series(acb_ptr g, acb_srcptr h, slong hlen, slong n, slong prec);
766 void acb_poly_erf_series(acb_poly_t g, const acb_poly_t h, slong n, slong prec);
767 
768 ACB_POLY_INLINE slong
acb_poly_allocated_bytes(const acb_poly_t x)769 acb_poly_allocated_bytes(const acb_poly_t x)
770 {
771     return _acb_vec_allocated_bytes(x->coeffs, x->alloc);
772 }
773 
774 #ifdef __cplusplus
775 }
776 #endif
777 
778 #endif
779