acb_poly.h

Initialise poly as the zero polynomial. acb_poly_init2 also allocates space for len coefficients.

Frees all coefficients and the coefficient array of poly.

Ensures that poly has at least len allocated and initialised coefficients. When it has to grow, the allocation is at least doubled. The length is not changed.

Sets the length of poly to len, which must not exceed the allocation. If the length decreases, the coefficients from len up to the old length are set to zero, so that unused coefficients are always zero.

Decreases the length of poly until the leading coefficient is not the exact zero ball. A coefficient that merely contains zero is kept.

Swaps poly1 and poly2 efficiently.

Returns the number of bytes allocated on the heap by x (the coefficient array and the limbs of the coefficients), excluding sizeof(acb_poly_struct).

Return the length of poly and its degree, the length minus one (-1 for the zero polynomial).

Return whether poly is exactly the polynomial 0, 1 or x (with exact coefficients).

Set poly to the constant 0 or 1.

Set dest to a copy of src, either exactly or with the midpoints rounded to prec bits (the rounding error is added to the radii).

Set dest to src truncated to length n (reduced modulo x^n), exactly or rounded to prec bits.

Set the coefficient of x^n in poly to c, extending the polynomial with zeros if necessary, and normalise. Require n \ge 0.

Sets v to the coefficient of x^n in poly, which is zero if n is at least the length. Requires n \ge 0.

Sets {res, n} to the reversal of {poly, len} as a polynomial of length n \ge \mathit{len}, that is, res[i] = poly[n - 1 - i] with zeros where the index is out of range. Aliasing is allowed. A wrapper of _gr_poly_reverse.

Set res to poly divided by x^n, discarding the coefficients of x^0, \ldots, x^{n-1}. Require n \ge 0. The underscore version writes \mathit{len} - n coefficients, requires n \le \mathit{len} and allows res to be poly. Wrappers of _gr_poly_shift_right.

Set res to poly multiplied by x^n. Require n \ge 0. The underscore version writes \mathit{len} + n coefficients and allows res to be poly. Wrappers of _gr_poly_shift_left.

Truncates poly to length at most n (reduces it modulo x^n) and normalises it. Requires n \ge 0.

Returns the index of the first coefficient of poly that is not the exact zero ball, or -1 if poly is zero. A coefficient that merely contains zero counts as nonzero, so the result is a lower bound for the valuation of the exact polynomials represented.

Set poly to the real polynomial re, rounding integer or rational coefficients to prec bits; acb_poly_set_arb_poly copies the balls exactly.

Set poly to \mathit{re} + i \cdot \mathit{im}, rounding integer or rational coefficients to prec bits.

Set poly to the constant polynomial src, exactly. The result has length zero if src is exactly zero.

Print poly to standard output or to file as a list [(c0), (c1), ...] of its coefficients from the constant term upwards, each printed with acb_fprintd to digits decimal digits.

Sets poly to a random polynomial of length at most len whose coefficients are generated by acb_randtest or acb_randtest_precise with the parameters prec and mag_bits. For testing.

Returns nonzero if A and B have the same length and identical coefficient balls (equal midpoints and radii of the real and imaginary parts).

Return nonzero if every coefficient of poly2 is contained in the corresponding coefficient of poly1, coefficients beyond the length of poly2 being zero.

Return nonzero if the coefficients of poly1 and poly2 overlap pairwise (coefficients of the longer polynomial beyond the length of the shorter one must contain zero). The underscore version requires \mathit{len1} \ge \mathit{len2}.

If, for every coefficient of x, the real part contains exactly one integer and the imaginary part contains zero, sets z to the integer polynomial with these coefficients and returns nonzero; z is then the only integer polynomial contained in x. Otherwise returns zero, and z may have been modified.

Returns nonzero if all coefficients of poly have imaginary part exactly zero.

Set res to the real polynomial with exact nonnegative coefficients that are upper bounds, rounded to prec bits, for the absolute values of the coefficients of poly. For |x| \le t, its value at t bounds the absolute value at x of every polynomial in poly.

Set {C, max(lenA, lenB)} to the sum or difference of {A, lenA} and {B, lenB}. The output may be the same array as either input, and the lengths may be zero.

Set C to A + B or A - B.

Set C to A + B or A - B truncated to length len, without computing the discarded coefficients.

Sets C to -A, exactly.

Sets C to 2^c A, exactly.

Set C to c A or A / c. Division by a ball that contains zero gives non-finite coefficients.

Set {C, n} to the product of {A, lenA} and {B, lenB} truncated to length n. Require \mathit{lenA}, \mathit{lenB} \ge 1 and 1 \le n \le \mathit{lenA} + \mathit{lenB} - 1; the output must not overlap either input. If A and B are the same pointer with the same length, the square is computed.

Set C to AB truncated to length n. If A and B are the same object, the square is computed.

Set C to the full product AB. The underscore version writes \mathit{lenA} + \mathit{lenB} - 1 coefficients, requires positive lengths and no aliasing, and calls _acb_poly_mullow.

Set z (or res) to the coefficients of x^{\mathit{nlo}}, \ldots, x^{\mathit{nhi}-1} of the product, shifted down to start at x^0. The underscore versions write \mathit{nhi} - \mathit{nlo} coefficients and require positive lengths, 0 \le \mathit{nlo} < \mathit{nhi} \le \mathit{xlen} + \mathit{ylen} - 1 and no aliasing. The algorithms and the choice between them are those of the mullow functions.

If the inputs are well-scaled, sets {z, nhi - nlo} to the coefficients of x^{\mathit{nlo}}, \ldots, x^{\mathit{nhi}-1} of the product of {x, xlen} and {y, ylen} (the square if the pointers and lengths are equal) and returns 1; otherwise returns 0 and leaves z undefined. The window may extend beyond the product, and z may alias an input.

Returns whether _acb_poly_mulmid and _acb_poly_mullow should try _acb_poly_mulmid_fmpzi first: this is the case when the number q of coefficient products in the window per input coefficient satisfies q \ge 1 and q \cdot \mathit{prec}^{0.57} \ge 240 (330 for squares). Both lengths must be at least 2.

Sets {res, len1 + len2 - 1} to the product of the monic polynomials {poly1, len1} and {poly2, len2}, with leading coefficient exactly

1. No aliasing.

Set Q to the power series inverse 1/A truncated to length n (len). The result is finite only if the constant term of A excludes zero; it is indeterminate if A is zero. The underscore version requires positive lengths and no aliasing.

Set Q to the power series quotient A / B truncated to length n. For n \le 10 or B of length 2 the coefficients are computed by the recurrence, otherwise as A \cdot (1/B) with _acb_poly_inv_series. The underscore version requires positive lengths and no aliasing.

Compute the quotient {Q, lenA - lenB + 1} and/or the remainder {R, lenB - 1} of the division of {A, lenA} by {B, lenB}. Require \mathit{lenA} \ge \mathit{lenB} \ge 1 and no aliasing. If the leading coefficient of B contains zero, the output is not finite.

Computes Q and R with A = BQ + R and \deg R < \deg B, and returns nonzero. If B is zero or its leading coefficient contains zero, returns zero and leaves Q and R unchanged.

Divides {A, len} by x - c by Horner's scheme, writing the quotient {Q, len - 1} and the remainder R = A(c). Requires \mathit{len} \ge 1.

Set g to the Taylor shift f(x + c). The underscore version works in place on {g, n}. Wrappers of _gr_poly_taylor_shift.

Set res to the composition f(g(x)) of f = poly1 and g = poly2. The underscore version writes (\mathit{len1} - 1)(\mathit{len2} - 1) + 1 coefficients and does not allow aliasing. Wrappers of _gr_poly_compose_divconquer (Composition and modular composition).

Set res to the power series composition f(g(x)) \bmod x^n. The constant term of g must be exactly zero; acb_poly_compose_series throws an exception otherwise. The underscore version does not allow aliasing. Wrappers of _gr_poly_compose_series.

Set h to the power series reversion of f, the expansion of the compositional inverse f^{-1}(x) modulo x^n. The constant term of f must be exactly zero and its linear coefficient must exclude zero (otherwise the result is indeterminate). The underscore version requires \mathit{flen} \ge 2 and no aliasing. Wrappers of _gr_poly_revert_series, which uses the fast Lagrange inversion of [Joh2015b] up to five times the Kinoshita–Li cutoff of the composition, and Newton iteration with fast composition beyond.

Set y = f(x) using Horner's rule, rectangular splitting [PS1973], or an automatic choice: rectangular splitting when \mathit{prec} \ge 1024, \mathit{len} \ge 5 + 20000/\mathit{prec} and the coefficients have at most \mathit{prec}/2 bits, Horner's rule otherwise. The underscore versions accept \mathit{len} = 0.

Set y = f(x) and z = f'(x) together, using Horner's rule, rectangular splitting (which reuses the powers of x for both values) or the automatic choice of _acb_poly_evaluate.

Set poly to (x - x_0)(x - x_1) \cdots (x - x_{n-1}). The underscore version writes n + 1 coefficients. Wrappers of _gr_poly_product_roots, which multiplies the factors in a balanced tree. For a real polynomial with roots in conjugate pairs, arb_poly_product_roots_complex avoids the spurious imaginary parts.

Allocate, free and fill a subproduct tree for the factors x - x_i of len points (Multipoint evaluation and interpolation). Wrappers of _gr_poly_tree_alloc, _gr_poly_tree_free and _gr_poly_tree_build.

Set ys[i] to the value of poly at xs[i] for 0 \le i < n by calling _acb_poly_evaluate for each point.

Evaluate poly at n points by the remainder tree algorithm, given the points or a precomputed subproduct tree. Wrappers of _gr_poly_evaluate_vec_fast_precomp. The remainder tree is numerically unstable: unless the precision grows with the number of points, the radii become large.

Set poly to the polynomial of length at most n with \mathit{poly}(x_i) = y_i, by computing divided differences (the Newton form) and converting to the monomial basis. If two of the points overlap as balls, the result is not finite.

Interpolate as acb_poly_interpolate_newton, using the barycentric form of the Lagrange interpolation formula.

Interpolate by the fast Lagrange formula on a subproduct tree. _acb_poly_interpolation_weights computes the weights w_i = 1 / \prod_{j \ne i} (x_i - x_j) from a tree, and the precomp version takes the tree and the weights as input. Wrappers of _gr_poly_interpolation_weights and _gr_poly_interpolate_fast_precomp.

Set res to the derivative of poly. The underscore version writes \mathit{len} - 1 coefficients and allows aliasing. Wrappers of _gr_poly_derivative.

Set res to the n-th derivative of poly. The underscore version writes \mathit{len} - n coefficients (nothing if \mathit{len} \le n) and allows aliasing. Wrappers of _gr_poly_nth_derivative.

Set res to the integral of poly with zero constant term. The underscore version reads {poly, len - 1}, writes {res, len} and allows aliasing. Wrappers of _gr_poly_integral.

Map \sum_k a_k x^k to \sum_k (a_k / k!) x^k (Borel transform) or to \sum_k a_k k!\, x^k (inverse Borel transform). The underscore versions allow aliasing.

Set b to the binomial transform of a truncated to length len, b_n = \sum_{k=0}^{n} (-1)^k \binom{n}{k} a_k. The transform is the power series composition f(x) \mapsto (1-x)^{-1} f(x/(x-1)) and is an involution. The underscore versions require positive lengths and do not allow aliasing.

Set b to the Graeffe transform G of P = a, defined by G(x^2) = (-1)^d P(x) P(-x) with d = \deg P, so that the roots of G are the squares of the roots of P. The underscore version reads {a, len}, writes len coefficients and allows aliasing.

Set res to f^{e} truncated to length len, by binary exponentiation with truncated products. The underscore version requires len to be at most the length of the untruncated power, positive lengths and no aliasing. Wrappers of _gr_poly_pow_series_ui_binexp.

Set res to f^{e}. The underscore version writes e(\mathit{flen} - 1) + 1 coefficients, requires \mathit{flen} \ge 1 and no aliasing.

Set h to the power series f^g = \exp(g \log f) truncated to length len. If g is constant, _acb_poly_pow_acb_series is used. The underscore version requires positive lengths with \mathit{flen}, \mathit{glen} \le \mathit{len} and no aliasing.

Set h to f^g = \exp(g \log f) for a constant exponent g, truncated to length len. The underscore version requires positive lengths with \mathit{flen} \le \mathit{len} and no aliasing.

Set g to the power series square root of h, with constant term \sqrt{h_0}, truncated to length n. Computes the reciprocal square root to half the length and finishes with one Karp–Markstein step [KM1997]. The underscore version does not allow aliasing.

Set g to the power series h^{-1/2} truncated to length n, by the division-free Newton iteration g \leftarrow g + g(1 - hg^2)/2. Wrappers of _gr_poly_rsqrt_series_newton. The underscore version does not allow aliasing.

Set res to \log f = \log f_0 + \int f'/f\, dx truncated to length n. The underscore version allows aliasing. Wrappers of _gr_poly_log_series.

Set res to \log(1 + f), which is more accurate than acb_poly_log_series when the constant term of f is small. Wrappers of _gr_poly_log1p_series.

Set res to \operatorname{atan} f, \operatorname{asin} f or \operatorname{acos} f truncated to length n. The underscore versions allow aliasing. Wrappers of _gr_poly_atan_series, _gr_poly_asin_series and _gr_poly_acos_series.

Set res to the inverse hyperbolic tangent, sine or cosine of f truncated to length n. The underscore versions allow aliasing. Wrappers of the corresponding _gr_poly functions.

Set f to \exp h truncated to length n. The underscore versions allow aliasing.

Set f to \exp(\pi i h) truncated to length n, using acb_exp_pi_i for the constant term (which is accurate when h_0 is close to a rational number with small denominator). The underscore version allows aliasing.

Set s and c to \sin h and \cos h truncated to length n, computed together. The underscore version allows aliasing. For n \ge 3 and nonconstant h this wraps _gr_poly_sin_cos_series.

Set s to \sin h or c to \cos h truncated to length n. The underscore versions allow aliasing. Wrappers of _gr_poly_sin_series and _gr_poly_cos_series.

Set g to \tan h truncated to length n. The underscore version does not allow aliasing. Wrappers of _gr_poly_tan_series, which uses Newton iteration on \operatorname{atan} for long series.

Set g to \cot h truncated to length n. The underscore version allows aliasing. Wrappers of _gr_poly_cot_series.

Compute the trigonometric functions of \pi h truncated to length n. These are more accurate than multiplying by \pi first when the constant term of h is close to an integer or a half-integer. Wrappers of the corresponding _gr_poly functions.

Set s and/or c to \sinh h and \cosh h truncated to length n.

Set g to \tanh h or \coth h truncated to length n. The underscore versions allow aliasing. Wrappers of _gr_poly_tanh_series and _gr_poly_coth_series.

Set s to \operatorname{sinc} h = \sin(h)/h or to \operatorname{sinc}(\pi h) truncated to length n. A constant term that contains zero is handled through the Taylor series of \operatorname{sinc} on a ball around zero, so that the removable singularity does not cause a division by zero.

Set res to branch k of the Lambert W function of the power series z, truncated to length len. The value at the constant term is computed by acb_lambertw with the same k and flags (which select the branch cut conventions, see there) [Joh2017b], and the remaining coefficients by Newton iteration on w e^w = z. The underscore version allows aliasing.

Set res to \Gamma(h), 1/\Gamma(h), \log \Gamma(h) or \psi(h) truncated to length n. The underscore versions allow aliasing.

Set res to the rising factorial f (f+1) \cdots (f+r-1) truncated to length trunc, by binary splitting. The underscore version requires flen, r and trunc to be positive and no aliasing.

Set {z, len} to S(s, a, q, n) by summing the terms one by one; the series of (k+a)^{-s-t} is (k+a)^{-s} \sum_j (-\log(k+a))^j t^j/j!. The threaded version splits the sum over flint_get_num_threads() threads.

Sets {z, len} to S(s, a, q, n) using a transposed multipoint evaluation, in \tilde O(\max(n, \mathit{len})) arithmetic operations instead of O(n \cdot \mathit{len}).

Returns the number of guard bits used by _acb_poly_powsum_series_tree for the exact parameters s, a, q and the centre c: roughly a constant times \min(n, \mathit{len}) plus a term for the variation of the weights, estimated in double precision from a sample of the terms.

Returns nonzero if _acb_poly_powsum_series_tree is predicted to be faster than _acb_poly_powsum_series_naive (or the threaded naive version if naive_threaded is set) for these parameters, using empirical cost models and the guard bit estimate. This selects the algorithm in the Euler–Maclaurin summation of the Hurwitz zeta function and in the direct summation of the polylogarithm for small |z|.

Sets {z, len} to \sum_{k=1}^{n} k^{-(s+t)} as a power series in t. Powers of composite k = ij are computed as products i^{-(s+t)} j^{-(s+t)} of stored powers, and the even terms are grouped as a polynomial in 2^{-(s+t)}. This takes about n / \log n powers, n/2 multiplications and storage for n/6 power series, and is faster than the naive algorithm only when len is small.

Chooses the parameters N (number of terms summed directly) and M (number of Bernoulli terms) of the Euler–Maclaurin formula for the length-d series of \zeta(s, a), aiming at an error of about 2^{-\mathit{target}} times an estimate |a^{-s}| of the magnitude (absolute error 2^{-\mathit{target}} for a = 1), and sets bound to the corresponding error bound.

Compute bounds for the error of the Euler–Maclaurin evaluation with parameters N, M: _acb_poly_zeta_em_bound bounds each of the d coefficients, _acb_poly_zeta_em_bound1 gives a single bound for all of them. The formulas are those of [Joh2013].

Evaluate the tail (the Bernoulli number terms) of the Euler–Maclaurin formula for \zeta(s + x, a) as a power series, given N + a and the series of (N + a)^{-(s+x)}, by the naive recurrence or by binary splitting.

Sets {z, d} to the truncated Euler–Maclaurin sum of order N, M for the series of \zeta(s + x, a) (without the error term). If deflate is nonzero, \zeta(s + x, a) - 1/(s + x - 1) is computed, which permits expansion at s = 1.

Sets {z, d} to the series of \zeta(s + x, a) (or the deflated function if deflate is nonzero), choosing the Euler–Maclaurin parameters with _acb_poly_zeta_em_choose_param for the target prec and adding the error bound to each coefficient (Zeta functions, polylogarithms and L-functions).

Set res to the Hurwitz zeta function \zeta(s, a) of the power series s = f for a constant a, truncated to length n; a = 1 gives the Riemann zeta function. If deflate is nonzero, \zeta(s, a) + 1/(1 - s) is computed, which is finite at s = 1; with s = 1 + x this gives the Stieltjes constants, \sum_{k=0}^{n-1} \frac{(-1)^k}{k!} \gamma_k(a) x^k.

Set {w, len} to the Taylor series in x of the polylogarithm \operatorname{Li}_{s+x}(z) for complex constants s and z; len must be positive and w must not alias s or z. The small version sums the power series in z (for |z| < 1), the zeta version writes the polylogarithm as a combination of two Hurwitz zeta functions, and the default uses the small version for |z| < 1/2 and the zeta version otherwise (and acb_hypgeom_dilog for s = 2 and length 1) (Zeta functions, polylogarithms and L-functions).

Set w to \operatorname{Li}_s(z) for a power series s and a constant z, truncated to length len. The underscore version requires positive lengths and allows aliasing.

Set res to the error function of the power series z, truncated to length n. These wrappers of acb_hypgeom_erf_series are kept for backwards compatibility; see also acb_hypgeom_erfc_series and acb_hypgeom_erfi_series.

Set res to the arithmetic-geometric mean M(1, z) of 1 and the power series z, truncated to length n: the derivatives at the constant term come from acb_agm1_cpx, and the series is composed with the nonconstant part of z.

Wrappers, kept for backwards compatibility, of acb_elliptic_k_series (the complete elliptic integral K(z)) and acb_elliptic_p_series (the Weierstrass function \wp(z, \tau)) in acb_elliptic.h, which should be used instead.

Set bound to an upper bound for the absolute values of the complex roots of every polynomial in poly, using Fujiwara's bound [Fuj1916]

The bound is infinite if the leading coefficient contains zero or the length is at most 1.

Given a point m, a nonconstant polynomial f = {poly, len} of degree n and its derivative polyder, sets r to a box centred at m that contains a disk of radius n |f(m)/f'(m)|, which contains at least one root of every polynomial in the ball f.

Given approximations {roots, len - 1} of the roots of {poly, len}, replaces each by an inclusion box from _acb_poly_root_inclusion around its midpoint, moves the boxes that do not overlap any other box to the front, and returns their number. Every box contains a root; if the return value equals the degree, each box contains exactly one root and all roots are isolated.

Attempts to compute all n roots of the nonzero polynomial poly of degree n, writing n enclosures to roots and returning the number of roots that are isolated; these come first. If the return value equals n, every enclosure contains exactly one root. initial gives starting values (or NULL), and maxiter limits the number of iterations (0 selects a default). The polynomial should be squarefree.

Sets {roots, len - 1} to approximations of the roots of {poly, len} computed by cd_poly_find_roots in double precision after rescaling x and the coefficients so that the coefficients are representable as doubles, with the radii set to zero. Returns the largest relative step of the last iteration. prec (if below 53) only serves as an early termination criterion.

Given a real polynomial poly (stored as an acb_poly_t with zero imaginary parts) and isolating enclosures of all its complex roots, returns nonzero if it can prove that the enclosures whose imaginary part contains zero contain real roots. Then every such root is real (its imaginary part can be set to zero), and every other enclosure contains a nonreal root. Returns zero if this cannot be decided at the accuracy of the input and the precision prec.

Sets roots (room for 2\,\mathit{len} doubles) to approximations of the \mathit{len} - 1 roots of poly and returns the largest relative step |\Delta z_k| / |z_k| of the last iteration (at least 2^{-50}). initial is NULL or holds \mathit{len} - 1 starting values (zero entries are replaced by values from the Newton polygon).

Update the \mathit{len} - 1 approximate roots in z with one damped Weierstrass–Durand–Kerner step z_k \leftarrow z_k - \delta_k, where \delta_k = f(z_k) / (a_n \prod_{j \ne k} (z_k - z_j)) is scaled down so that |\delta_k| \le stepsize_bound, and return the largest relative step. The version with pivot evaluates large roots through the reversed polynomial and orders the factors of the products to reduce the risk of overflow; it does not preserve the order of the roots.

Sets z_r, z_i to n - 1 initial values for the roots of the polynomial with coefficients p_r, p_i of length n: the nonzero entries of z0 (of length d, or NULL), completed by points on circles given by the Newton polygon of (k, -\log|p_k|) [Bin1996].

Evaluates the polynomial of length n with the given coefficients at the points with indices n_{\mathrm{start}} \le k < n_{\mathrm{end}}, by Horner's rule vectorised over the points.

Compute the Weierstrass denominators w_k = c \prod_{j \ne k} (z_k - z_j), with c = lc_r + i lc_i, for n_{\mathrm{start}} \le k < n_{\mathrm{end}}. cd_poly_weierstrass uses the d points values for both factors and exploits the symmetry of the differences; cd_poly_weierstrass_distinct_orders takes the factors z_j from col_values (in an order chosen to avoid overflow) and the points z_k from row_values, skipping a factor that is exactly zero.

Applies the damped updates z_k \leftarrow z_k - \delta_k with \delta_k = v_k / w_k (values vp, denominators wdk, using Smith's division), scaled so that |\delta_k| \le stepsize_bound, for n_{\mathrm{start}} \le k < n_{\mathrm{end}}, and returns the largest relative step |\delta_k|/|z_k| before damping.

Sets {h, len} to (a + bx^d)^g truncated to length len, where {f, flen} is a + bx^d with d = \mathit{flen} - 1 and zero coefficients in between (not checked), using the binomial series. No aliasing.

Sets {w, len} to the power series a^{b + x} = a^b \sum_k (\log a)^k x^k / k! truncated to length len. Also available under the name _acb_poly_pow_cpx.

Sets {res, trunc} to the power series N^{-(c + x)} truncated to length trunc.

Sets res to the product of {src, len} and c + x, truncated to length trunc (which must be len or len + 1). Aliasing of res and src is allowed.