arb_poly.h

Initialise poly as the zero polynomial. arb_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(arb_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 integer or rational polynomial src, rounding each coefficient to prec bits. Integers of at most prec bits are converted exactly.

Set poly to the constant polynomial src or c, exactly. The result has length zero if the constant 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 arb_fprintd to digits decimal digits.

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

Return nonzero if every coefficient of poly2 is contained in the corresponding coefficient of poly1, where coefficients beyond the length of poly2 are zero; that is, if the set represented by poly1 contains poly2.

Returns nonzero if A and B have the same length and identical coefficient balls (equal midpoints and equal radii). This compares representations, not the polynomials represented.

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), that is, if the two sets of polynomials intersect. The underscore version requires \mathit{len1} \ge \mathit{len2}.

If every coefficient of x contains exactly one integer, sets z to the integer polynomial with these coefficients and returns nonzero. Otherwise returns zero, and z may have been modified.

Set res to the 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, which is faster and gives tighter radii than a product of two different polynomials.

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 _arb_poly_mullow. Squaring is detected as for arb_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 middle product). 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.

Sets {res, len1 + len2 - 1} to the product of the monic polynomials {poly1, len1} and {poly2, len2}: the leading coefficient is set to exactly 1, and the others are computed with _arb_poly_mullow. No aliasing.

Adds to {z, nhi - nlo} upper bounds for the coefficients of x^{\mathit{nlo}}, \ldots, x^{\mathit{nhi}-1} of the product of the polynomials {x, xlen} and {y, ylen} with nonnegative mag_t coefficients. The operands are split into blocks after the substitution x \to 2^{-\mathit{scale}} x, as the radii in _arb_poly_mulmid_block. This bounds the radii in _acb_poly_mulmid_fmpzi.

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 _arb_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 (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; arb_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. The underscore versions accept \mathit{len} = 0.

Set y = f(x) for a complex ball x, using Horner's rule, rectangular splitting, or the default, which is rectangular splitting.

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 _arb_poly_evaluate.

Set y = f(x) and z = f'(x) for a complex ball x.

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.

Set poly to the real polynomial

with \mathit{rn} real roots and \mathit{cn} pairs of complex conjugate roots, of which one member of each pair is given. Either count may be zero. Use acb_poly_product_roots for complex roots that are not grouped in conjugate pairs.

Allocate, free and fill a subproduct tree for the factors x - x_i of len points, as used by fast multipoint evaluation and interpolation (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 _arb_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 arb_poly_interpolate_newton, using the barycentric form of the Lagrange interpolation formula.

Interpolate by the fast Lagrange formula on a subproduct tree. _arb_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, _arb_poly_pow_arb_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 arb_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 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 W(z) truncated to length len: the principal branch W_0 if flags is 0, the branch W_{-1} if flags is 1. The underscore version allows aliasing. The value at the constant term comes from arb_lambertw [Joh2017b], and the series from Newton iteration on w e^w = z.

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 res to the Hurwitz zeta function \zeta(s, a) of the power series s, for a constant a > 0, truncated to length n; a = 1 gives the Riemann zeta function. If a contains a nonpositive number, the result is indeterminate. If deflate is nonzero, \zeta(s, a) + 1/(1 - s) is computed, which is finite at s = 1.

Set res to the Riemann–Siegel theta function

of the power series h, truncated to length n, where the argument of the gamma function is the imaginary part of \log \Gamma (continuous in h). The underscore version does not allow aliasing.

Set res to the Riemann–Siegel function Z(h) = e^{i\theta(h)} \zeta(1/2 + ih) of the power series h, truncated to length n. The real zeros of Z are the ordinates of the zeros of \zeta on the critical line. The underscore version allows aliasing.

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.

Sets convergence_factor to an upper bound for C = \sup_{t, u \in I} \tfrac12 |f''(t)| / |f'(u)|, where I is convergence_interval and f is {poly, len}, obtained by evaluating f' and f'' on I. The bound is infinite unless f' is bounded away from zero on I; for polynomials with large coefficients, I must be narrow.

Performs one step of Newton's method for a ball x = [m \pm r] that contains exactly one root of f = {poly, len}, given a ball I \supseteq x (convergence_interval) and the factor C computed by _arb_poly_newton_convergence_factor. Computes m' = m - f(m)/f'(m) in ball arithmetic and adds C r^2 to its radius. If the new ball x' lies in I and has a smaller radius than x, sets xnew to x' and returns nonzero; otherwise sets xnew to x and returns zero.

Refines the enclosure start of a simple root to about prec bits by Newton steps at roughly doubling precisions, as in arb_calc_refine_root_newton. eval_extra_prec is the number of guard bits needed to evaluate the polynomial accurately near the root (about the bit size of the coefficients if they are large and of alternating signs).

Set poly to the Swinnerton-Dyer polynomial S_n = \prod (x \pm \sqrt{2} \pm \sqrt{3} \pm \cdots \pm \sqrt{p_n}) of degree 2^n, the minimal polynomial over \mathbb{Q} of the sum of the square roots of the first n primes. If prec is 0, the precision _arb_poly_swinnerton_dyer_ui_prec(n) is used, which is chosen so that arb_poly_get_unique_fmpz_poly should succeed.

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.

Returns the number of zero bits below the most significant bit of e, which together with the bit length gives the number of squarings and multiplications in binary exponentiation.

Returns \min((\mathit{poly\_len} - 1) e + 1, \mathit{trunc}), the length of the e-th power of a polynomial of length \mathit{poly\_len} \ge 1 truncated to length trunc, without overflow.