FLINT3.7.0-dev
Algorithm

Series evaluation and the bit-burst algorithm

Cost
About 2N/32\sqrt{N/3} full products for NN terms by tapered rectangular splitting; O(M(n)log⁡2n)O(M(n)\log^2 n) 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 t<2−rt < 2^{-r}. 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, B=2FLINT_BITSB = 2^{\mathtt{FLINT\_BITS}} and nn is a number of limbs.

Rectangular splitting#

A Taylor series ∑k<Nakvk\sum_{k<N} a_k v^k with rational coefficients is evaluated at a fixed-point vv by rectangular splitting [Smi1989] [PS1973]: with blocks of mm terms,

Sb=∑i<mamb+i vi+vmSb+1,S_b = \sum_{i<m} a_{mb+i}\, v^i + v^m S_{b+1},

the powers v,…,vmv, \ldots, v^m are computed once (mm 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 1/k!1/k! 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 1/(2k+1)1/(2k + 1) the integers D/(2k+1)D/(2k+1) for a group of odd numbers with product DD are used, with one rescaling per group.

Tapering. Block bb is multiplied by vmb<2−rmbv^{mb} < 2^{-rmb} when it enters the sum, so only its top ⌈(FLINT_BITSn+g−rmb)/FLINT_BITS⌉\lceil(\mathtt{FLINT\_BITS} n + g - rmb)/\mathtt{FLINT\_BITS}\rceil limbs matter. Computing each block in its shortened window reduces the total cost to about mm products for the powers and N/(3m)N/(3m) for the block boundaries; with m≈N/1.5m \approx \sqrt{N/1.5} this is about 2N/32\sqrt{N/3} full products, against N/3N/3 for the tapered Horner scheme (_mp_real_series_tapered), which is faster only below about a dozen limbs. Errors committed in block b≥1b \ge 1 are damped by 2−min⁡(g,rm)2^{-\min(g, rm)}, and the error of the whole sum, a few units at its own precision, by the final multiplication by tt or t2t^2 (for the odd functions and 1−cos⁡1 - \cos), which is below 2−r2^{-r}. 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 sin⁡\sin, sinh⁡\sinh, atan⁡\operatorname{atan} and atanh⁡\operatorname{atanh}, 3.6 ulps for 1−cos⁡1 - \cos and cosh⁡−1\cosh - 1 (with the error of t2t^2 times a sum near 1/21/2), and 5 ulps for exp, whose sum is the result.

The tangent has coefficients Tk+2/(2k+3)!T_{k+2}/(2k+3)! 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 QjQ_j fits j+1j + 1 limbs, and the sum is carried as QjQ_j times the partial sum, so that a term costs j+1j + 1 scalar passes and moving to the next chunk one division by Qj/Qj−1Q_j/Q_{j-1}.

For the sizes on the hot paths (arguments below 2−322^{-32} or 2−642^{-64} 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 O(N)O(\sqrt{N}) full products at best. Brent's bit-burst algorithm [Bre1976b] instead splits the argument into slices of increasing length,

t=t0+t1+⋯+tK,tk=bits 2k…2k+1 of t (roughly),t = t_0 + t_1 + \cdots + t_K, \qquad t_k = \text{bits } 2^k\ldots 2^{k+1} \text{ of } t \text{ (roughly)},

and computes exp⁡(t)=∏kexp⁡(tk)\exp(t) = \prod_k \exp(t_k), where each exp⁡(tk)\exp(t_k) 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 2k2^k bits starting at bit 2k2^k needs about p/2kp/2^k terms whose integers grow by 2k2^k bits per term, so each slice costs O(M(p)log⁡p)O(M(p)\log p) and the whole O(M(p)log⁡2p)O(M(p)\log^2 p).

For the exponential the splitting computes T/(QBQE)=∑kxk/(k! BDk)T/(QB^{QE}) = \sum_k x^k/(k!\,B^{Dk}) for a slice xB−Dx B^{-D}. For the sine and cosine, both are obtained from one tree over the series in y=x2y = x^2:

sin⁡x′=x′ Q−B′Q,1−cos⁡x′=AQ,−B′Q=∑k≥1(−y)k(2k+1)!,−AQ=∑k≥1(2k+1)(−y)k(2k+1)!,\sin x' = x'\,\frac{Q - B'}{Q}, \qquad 1 - \cos x' = \frac{A}{Q}, \qquad -\frac{B'}{Q} = \sum_{k \ge 1}\frac{(-y)^k}{(2k+1)!}, \quad -\frac{A}{Q} = \sum_{k \ge 1}\frac{(2k+1)(-y)^k}{(2k+1)!},

using 1/(2k)!=(2k+1)/(2k+1)!1/(2k)! = (2k+1)/(2k+1)! so that both share the denominator Q=∏(2i)(2i+1)Q = \prod (2i)(2i+1); the second track costs two extra products per merge, half the work of a splitting of exp⁡(ix)\exp(ix) over all 2N2N terms. Past a term threshold the cosine track is dropped and recovered from the slice's denominator by one square root. The slice factors exp⁡(ixk)\exp(ix_k) are multiplied by mp_real_mul_complex.

These splittings have fixed midpoints, so every merge at a given level multiplies by the same power xsx^s 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 hh times, so that the reduced argument is below 2−r2^{-r} for a tuned depth rr, evaluate the reduced function by bit-burst, and undo the halving: the exponential by hh squarings, the sine and cosine by hh angle doublings on g=1−cos⁡g = 1 - \cos alone,

g(2θ)=2g(2−g),sin⁡x=2g−g2,g(2\theta) = 2g(2 - g), \qquad \sin x = \sqrt{2g - g^2},

with every intermediate a pure fraction and one square root at the end.

Proposition 1. Squaring a value with relative error ε\varepsilon gives relative error at most 2ε+ε22\varepsilon + \varepsilon^2; a doubling of gg with absolute error δ\delta, for g<1/2g < 1/2, gives an absolute error at most 4δ+2δ24\delta + 2\delta^2; and 2g−g2\sqrt{2g - g^2} divides an absolute error of gg by 2sin⁡x⋅2\sin x \cdot (to first order) 1/(1−g)1/(1 - g).

Proof. (y(1+ε))2=y2(1+2ε+ε2)(y(1 + \varepsilon))^2 = y^2(1 + 2\varepsilon + \varepsilon^2). For the doubling, ddg2g(2−g)=4−4g∈(2,4]\frac{d}{dg} 2g(2 - g) = 4 - 4g \in (2, 4] and the second derivative is −4-4. For the square root, ddg2g−g2=(1−g)/2g−g2=cos⁡x/sin⁡x\frac{d}{dg}\sqrt{2g - g^2} = (1 - g)/\sqrt{2g - g^2} = \cos x/\sin x, and cos⁡x≤1\cos x \le 1.

Hence hh squarings amplify the relative error by 2h2^h, and hh doublings followed by the square root amplify the absolute error by at most 22h/sin⁡x2^{2h}/\sin x; since any path that doubles at all has x≥2−z−1x \ge 2^{-z-1} for an argument with zz leading zero bits, h+log⁡2n+8h + \log_2 n + 8 resp. 2h+z+log⁡2n+82h + z + \log_2 n + 8 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 ss 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#

Referenced from#

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.
Cite this page

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