Series evaluation and the bit-burst algorithm
- Cost
- About full products for terms by tapered rectangular splitting; by the bit-burst algorithm.
After an argument reduction (Argument reduction, Table-based argument reduction), the kernels of the elementary functions are left with the value of a function at a small fixed-point argument . This page describes how that value is computed: by the Taylor series with rectangular splitting at moderate precision, and by Brent's bit-burst algorithm at high precision, which also serves the table-free kernels for single evaluations at huge precision. Throughout, and is a number of limbs.
Rectangular splitting#
A Taylor series with rational coefficients is evaluated at a fixed-point by rectangular splitting [Smi1989] [PS1973]: with blocks of terms,
the powers are computed once ( full products), every term is one scalar multiply-add of a precomputed power by a one-limb coefficient, and each block boundary costs one full product. The coefficients are generated as ratios of consecutive integers, chained downwards so that one mpn_divrem_1 closes each run of factors that fills a limb; for the integers for a group of odd numbers with product are used, with one rescaling per group.
Tapering. Block is multiplied by when it enters the sum, so only its top limbs matter. Computing each block in its shortened window reduces the total cost to about products for the powers and for the block boundaries; with this is about full products, against for the tapered Horner scheme (_mp_real_series_tapered), which is faster only below about a dozen limbs. Errors committed in block are damped by , and the error of the whole sum, a few units at its own precision, by the final multiplication by or (for the odd functions and ), which is below . What remains is the error of that last product, taken directly over the significant limbs of its operands: one unit for the high product and up to one for each operand truncated below it. The results are within 3.1 ulps for , , and , 3.6 ulps for and (with the error of times a sum near ), and 5 ulps for exp, whose sum is the result.
The tangent has coefficients involving the tangent numbers, which are not ratios of small integers. Their leading denominators are small, though: in _mp_real_series_rs_tan, the terms are grouped into chunks whose common denominator fits limbs, and the sum is carried as times the partial sum, so that a term costs scalar passes and moving to the next chunk one division by .
For the sizes on the hot paths (arguments below or after a reduction, up to a few dozen limbs), the series are generated straight-line code; a generic engine making the same calls in the same order serves the other sizes with identical results.
Bit-burst evaluation#
At high precision the Taylor series of the reduced argument has many terms, and evaluating it with full-precision arithmetic costs full products at best. Brent's bit-burst algorithm [Bre1976b] instead splits the argument into slices of increasing length,
and computes , where each is the sum of a series with a short rational argument, evaluated exactly by binary splitting (Binary splitting of hypergeometric series in mp_real). A slice of bits starting at bit needs about terms whose integers grow by bits per term, so each slice costs and the whole .
For the exponential the splitting computes for a slice . For the sine and cosine, both are obtained from one tree over the series in :
using so that both share the denominator ; the second track costs two extra products per merge, half the work of a splitting of over all terms. Past a term threshold the cosine track is dropped and recovered from the slice's denominator by one square root. The slice factors are multiplied by mp_real_mul_complex.
These splittings have fixed midpoints, so every merge at a given level multiplies by the same power of the argument; the powers are tabulated, and their fft_small transforms are computed once per tree for the entries used by at least two merges (Power tables with precomputed transforms).
_mp_real_exp_reduced and _mp_real_sin_cos_reduced choose between the series, one bit-burst step (the leading slice by binary splitting and the rest by the series at the reduced size) and the full cascade, by tuned thresholds that depend on the number of threads (a slice parallelises where the series does not). The slices of a cascade run as tasks on the available threads.
Table-free evaluation#
A single evaluation at huge precision cannot amortise tables. The table-free kernels halve the argument times, so that the reduced argument is below for a tuned depth , evaluate the reduced function by bit-burst, and undo the halving: the exponential by squarings, the sine and cosine by angle doublings on alone,
with every intermediate a pure fraction and one square root at the end.
Proposition 1. Squaring a value with relative error gives relative error at most ; a doubling of with absolute error , for , gives an absolute error at most ; and divides an absolute error of by (to first order) .
Proof. . For the doubling, and the second derivative is . For the square root, , and .
Hence squarings amplify the relative error by , and doublings followed by the square root amplify the absolute error by at most ; since any path that doubles at all has for an argument with leading zero bits, resp. guard bits keep the amplified error below one output ulp, and the bound written is 128 ulps.
mp_real_exp_notab_squaring applies the same idea to balls, with ball squarings, and mp_real_exp_agm improves a starting value computed this way by one Newton–Taylor step on the AGM logarithm.
Use in FLINT#
_mp_real_series_rsand_mp_real_series_rs_sin_cosevaluate the reduced series by tapered rectangular splitting,_mp_real_series_taperedby the tapered Horner scheme and_mp_real_series_rs_tanthe chunked tangent series._mp_real_exp_reducedand_mp_real_sin_cos_reducedchoose between the series and the bit-burst algorithm;_mp_real_exp_notaband_mp_real_sin_cos_notabare the table-free kernels, andmp_real_exp_notab_squaringandmp_real_exp_agmthe table-free ball exponentials.
void _mp_real_series_rs(nn_ptr res, nn_srcptr x, slong n, flint_bitcnt_t r, int func)void _mp_real_series_tapered(nn_ptr res, nn_srcptr x, slong n, flint_bitcnt_t r, int func)void _mp_real_series_rs_tan(nn_ptr res, nn_srcptr x, slong n, flint_bitcnt_t r)void _mp_real_exp_reduced(nn_ptr y, ulong * err, nn_srcptr t, slong n, flint_bitcnt_t r, int alg)void _mp_real_sin_cos_reduced(nn_ptr ysin, nn_ptr yg, ulong * err, nn_srcptr t, slong n, flint_bitcnt_t r, int alg)void _mp_real_exp_notab(nn_ptr y, ulong * err, nn_srcptr x, slong n)void mp_real_exp_notab_squaring(mp_real_t res, const mp_real_t x, slong n)void mp_real_exp_agm(mp_real_t res, const mp_real_t x, slong n)Referenced from#
- Binary splitting of hypergeometric series in mp_real (algorithm)
- Multi-prime argument reduction (algorithm)
- Table-based argument reduction (algorithm)
- Elementary functions (algorithm)
_mp_real_series_rs,_mp_real_series_rs_sin_cos
References#
- [Smi1989] D. M. Smith. Efficient multiple-precision evaluation of elementary functions. Mathematics of Computation 52 (1989), 131–134. https://doi.org/10.1090/S0025-5718-1989-0971406-0
- [PS1973] M. S. Paterson and L. J. Stockmeyer, "On the number of nonscalar multiplications necessary to evaluate polynomials", SIAM J. Comput (1973)
- [Bre1976b] R. P. Brent. The complexity of multiple-precision evaluation of elementary functions. In J. F. Traub (ed.), Analytic Computational Complexity, Academic Press, 1976, 151–176.
The FLINT team, “Series evaluation and the bit-burst algorithm,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/special-functions/elementary-series.html (generated 2026-11-17).
@misc{flint-doc-algorithms-special-functions-elementary-series,
author = {{The FLINT team}},
title = {{Series evaluation and the bit-burst algorithm}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/special-functions/elementary-series.html},
note = {Generated 2026-11-17}
}