FLINT3.7.0-dev

Roots of Legendre polynomials and Gauss–Legendre nodes

Synopsis#include <flint/arb_hypgeom.h>
void arb_hypgeom_legendre_p_ui_root(arb_t res, arb_t weight, ulong n, ulong k, slong prec)source

Sets res to the kk-th root xkx_k of the Legendre polynomial PnP_n, with the roots in decreasing order 1>x0>x1>⋯>xn−1>−11 > x_0 > x_1 > \cdots > x_{n-1} > -1, and, if weight is not NULL, sets weight to the corresponding weight wk=2/((1−xk2)Pn′(xk)2)w_k = 2 / ((1 - x_k^2) P'_n(x_k)^2) of Gauss–Legendre quadrature on [−1,1][-1, 1]. Requires 0≤k<n0 \le k < n. See Roots of Legendre polynomials and Gauss–Legendre nodes.

For n≥64n \ge 64 and a precision of at least 128 bits, the positive roots are computed by _arb_hypgeom_legendre_p_ui_root_bitburst when the precision is between 0.3n0.3n and 15n15n and by _arb_hypgeom_legendre_p_ui_root_taylor otherwise; for smaller nn or precision, or if their certification fails, by Newton iteration with evaluations of PnP_n. See Gauss–Legendre nodes and weights.

int _arb_hypgeom_legendre_p_ui_root_bitburst(arb_t res, arb_t weight, ulong n, ulong k, slong prec)source
int _arb_hypgeom_legendre_p_ui_root_taylor(arb_t res, arb_t weight, ulong n, ulong k, slong prec)source

Computes the root xkx_k of PnP_n and, if weight is not NULL, its weight as arb_hypgeom_legendre_p_ui_root, for a positive root, 0≤k<⌊n/2⌋0 \le k < \lfloor n/2 \rfloor and n≤228n \le 2^{28} (2142^{14} on 32-bit systems), by bit-burst Newton steps with Taylor transfers (efficient when prec is comparable to nn) or by Newton–Taylor steps from a lower-precision enclosure (efficient when prec is much larger or much smaller than nn). Returns 1 on success, and 0 if the arguments are out of range or a certification step failed, in which case res and weight are undefined. See Bit-burst Newton steps and Newton–Taylor steps.

arb_hypgeom_legendre_p_ui_root computes an enclosure of the kk-th root xkx_k of the Legendre polynomial PnP_n and, optionally, the weight wk=2/((1−xk2)Pn′(xk)2)w_k = 2/((1-x_k^2) P_n'(x_k)^2), so that

∫−11f(x) dx≈∑k=0n−1wkf(xk)\int_{-1}^{1} f(x)\,dx \approx \sum_{k=0}^{n-1} w_k f(x_k)

is the nn-point Gauss–Legendre quadrature rule, exact for polynomials of degree less than 2n2n. The roots are numbered in decreasing order, 1>x0>x1>⋯>xn−1>−11 > x_0 > x_1 > \cdots > x_{n-1} > -1, which is the order of increasing θ\theta for the roots of Pn(cos⁡θ)P_n(\cos\theta). Only the roots with k<⌈n/2⌉k < \lceil n/2 \rceil need to be computed, since xn−1−k=−xkx_{n-1-k} = -x_k and wn−1−k=wkw_{n-1-k} = w_k; the function uses this symmetry itself. An index k≥nk \ge n raises an exception. The function is the one used by acb_calc_integrate to generate its quadrature rules (Rigorous numerical integration). The algorithms are described in Gauss–Legendre nodes and weights.

AlgorithmLegendre functions and orthogonal polynomialsLegendre polynomials of large degree by the method of Johansson and Mezzarobba (hypergeometric series at 0 and 1, an asymptotic expansion with explicit error bounds, and a recurrence, chosen by cost and cancellation), Gauss–Legendre nodes and weights by Newton iteration, bit-burst Newton steps and Newton–Taylor steps with certified Taylor bounds, associated Legendre functions of both kinds through 2F1 and connection formulas, spherical harmonics, and the classical orthogonal polynomials and their extensions to non-integer degree.

Example#

The 20-point rule integrates exe^x over [−1,1][-1, 1] to more than 30 digits; the error of the rule itself is about 10−6010^{-60}:

Examplearb_hypgeom_gauss_legendre.cchecked by make checkdoc
#include <flint/arb.h>
#include <flint/arb_hypgeom.h>

int main(void)
{
    arb_t x, w, s, t, wsum;
    ulong n = 20, k;
    slong prec = 128;

    arb_init(x);
    arb_init(w);
    arb_init(s);
    arb_init(t);
    arb_init(wsum);

    for (k = 0; k < n; k++)
    {
        arb_hypgeom_legendre_p_ui_root(x, w, n, k, prec);
        if (k == 0)
        {
            flint_printf("x_0 = "); arb_printn(x, 30, 0); flint_printf("\n");
            flint_printf("w_0 = "); arb_printn(w, 30, 0); flint_printf("\n");
        }
        /* s += w_k exp(x_k) */
        arb_exp(t, x, prec);
        arb_addmul(s, w, t, prec);
        arb_add(wsum, wsum, w, prec);
    }

    flint_printf("sum of weights = "); arb_printn(wsum, 30, 0); flint_printf("\n");
    flint_printf("quadrature     = "); arb_printn(s, 30, 0); flint_printf("\n");

    /* exact value e - 1/e */
    arb_const_e(t, prec);
    arb_inv(x, t, prec);
    arb_sub(t, t, x, prec);
    flint_printf("e - 1/e        = "); arb_printn(t, 30, 0); flint_printf("\n");

    arb_clear(x);
    arb_clear(w);
    arb_clear(s);
    arb_clear(t);
    arb_clear(wsum);
    flint_cleanup();
    return 0;
}
Output
x_0 = [0.993128599185094924786122388471 +/- 3.21e-31]
w_0 = [0.0176140071391521183118619623519 +/- 4.72e-32]
sum of weights = [2.00000000000000000000000000000 +/- 1.08e-37]
quadrature     = [2.35040238728760291376476370119 +/- 1.21e-30]
e - 1/e        = [2.35040238728760291376476370119 +/- 1.21e-30]

The enclosure of the quadrature sum is rigorous for the sum, but it does not include the error of the quadrature rule. For an integral with a proved error bound, use acb_calc_integrate, which bounds the quadrature error using the analyticity of the integrand [Joh2018a].

References#

Cite this page

The FLINT team, “Roots of Legendre polynomials and Gauss–Legendre nodes (arb_hypgeom.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/arb_hypgeom/legendre-roots.html (generated 2026-11-20).