FLINT3.7.0-dev
Algorithm

Table-based argument reduction

Cost
O(n2)O(n^2) word operations per evaluation at nn limbs with tables of O(n)O(n) entries (bitwise: O(r)O(r) table entries of nn limbs for a reduction depth rr), plus a series of O(n/r)O(n/r) terms.

From one limb to a few hundred limbs, the kernels of the elementary functions (Elementary functions) reduce their argument against precomputed tables until a short series finishes the evaluation: at one to three limbs from tables of a few hundred entries in registers, at four to 32 limbs by seven bits per step against dense tables, and up to 600 limbs by one bit per step against tables of log⁡(1+2−i)\log(1 + 2^{-i}) and atan⁡(2−i)\operatorname{atan}(2^{-i}). The remainder is evaluated by the series of Series evaluation and the bit-burst algorithm. Throughout, B=2FLINT_BITSB = 2^{\mathtt{FLINT\_BITS}} and nn is a number of limbs.

Table-driven kernels#

At one to three limbs on 64-bit machines, the kernels are short table-driven evaluations in registers [Tan1989]:

  • exp: v=j12−7+j22−14(+j32−21)+rv = j_1 2^{-7} + j_2 2^{-14} (+ j_3 2^{-21}) + r with tables of exp⁡(j2−7)\exp(j 2^{-7}), exp⁡(j2−14)−1\exp(j 2^{-14}) - 1 and exp⁡(j2−21)−1\exp(j 2^{-21}) - 1 (128 entries each) and a Taylor polynomial in rr;
  • log1p: a multiplicative reduction by short factors 1−Dk[j]1 - D_k[j] over three or four levels of 7 bits, with tables of −log⁡(1−Dk[j])-\log(1 - D_k[j]), then the Taylor polynomial of log⁡(1+u)\log(1 + u);
  • sin and cos: the pairs (sin⁡c,1−cos⁡c)(\sin c, 1 - \cos c) for c=j2−7c = j 2^{-7} and j2−14j 2^{-14} combined with the polynomials of the remainder by the addition formulas;
  • atan: atan⁡(v)=atan⁡(c)+atan⁡((v−c)/(1+vc))\operatorname{atan}(v) = \operatorname{atan}(c) + \operatorname{atan}((v - c)/(1 + vc)) with c=j2−9c = j 2^{-9} (513 entries) and the odd series of the quotient; for a ratio v=Y/Xv = Y/X the quotient is (512Y−jX)/(512X+jY)(512Y - jX)/(512X + jY) with an exact numerator and denominator, so atan⁡(Y/X)\operatorname{atan}(Y/X) costs one division.

The polynomials taper their precision (one limb for the innermost terms, then two, then three) and keep only the high parts of products. The tables hold three limbs per entry, read at their top limbs at smaller sizes.

Dense tables#

From four to 32 limbs, the kernels reduce the argument seven bits per level against tables, with multipliers that are exact single limbs, so that applying a level costs one row of one-limb products. For exp, t←v−log⁡(2s(1+C1[j1]))t \gets v - \log(2^s(1 + C_1[j_1])) with j1j_1 the top seven bits, then t←t−log⁡(1+jk2−7k)t \gets t - \log(1 + j_k 2^{-7k}) with jk=⌊t27k⌋j_k = \lfloor t 2^{7k} \rfloor for the following levels (the tables hold floors, so tt stays nonnegative), the series of exp⁡(t)\exp(t), and the product of the factors 1+jk2−7k1 + j_k 2^{-7k}. Logarithms use the dual multiplicative reduction, arctangents rotate the vector (1,v)(1, v) by factors 1−ick1 - i c_k, and the sine and cosine rotate the pair (cos⁡t,sin⁡t)(\cos t, \sin t) by 1+ick1 + i c_k and absorb the scale ∏(1+ck2)\prod (1 + c_k^2) by the double-angle formulas cos⁡v=(X2−Y2)/N\cos v = (X^2 - Y^2)/N, sin⁡v=2XY/N\sin v = 2XY/N with N=X2+Y2N = X^2 + Y^2, so that no square root is needed.

At four to ten limbs the code is generated straight-line code with static tables, at 11 to 32 limbs a generic loop (unrolled to add-with-carry chains at 11 to 16 limbs, with an mulx/adcx/adox row in assembly where available). The deeper table levels at those sizes are computed at run time when first needed, entry by entry, and published in a process-wide cache by a compare-and-swap on a state byte, so that no reader waits. The dense kernels are about 1.5 to 4 times faster than the bitwise kernels at the same sizes.

Bitwise reduction#

Up to 600 limbs, the argument is reduced by subtracting tabulated values Li=log⁡(1+2−i)L_i = \log(1 + 2^{-i}) or Ai=atan⁡(2−i)A_i = \operatorname{atan}(2^{-i}), in the manner of the BKM and CORDIC algorithms [BKM1994] [Mul2016], but at multiple precision and with a series for the remainder. The tables are computed once at the precision and index range in use and cached.

Lemma 1. Let c0>c1>⋯>cr>0c_0 > c_1 > \cdots > c_r > 0 with ci−1<2cic_{i-1} < 2c_i, and 0≤x<2c00 \le x < 2c_0. The greedy reduction, which for i=0,…,ri = 0, \ldots, r subtracts cic_i from xx if x≥cix \ge c_i, leaves 0≤x<cr0 \le x < c_r, using each cic_i at most once.

Proof. Before step ii we have 0≤x<2ci0 \le x < 2c_i: this holds for i=0i = 0, and if x≥cix \ge c_i the step leaves x−ci<cix - c_i < c_i, otherwise x<cix < c_i; in both cases x<ci<2ci+1x < c_i < 2c_{i+1}. After step rr the same argument gives x<crx < c_r.

The logarithms satisfy the hypothesis, since 2Li+1=log⁡(1+2−i+2−2i−2)>Li2L_{i+1} = \log(1 + 2^{-i} + 2^{-2i-2}) > L_i, and so do the arctangents, by concavity of atan⁡\operatorname{atan}.

Exponential. After the reduction x=∑i∈ULi+tx = \sum_{i \in U} L_i + t with t<Lr<2−rt < L_r < 2^{-r},

exp⁡(x)=exp⁡(t)∏i∈U(1+2−i),\exp(x) = \exp(t) \prod_{i \in U} (1 + 2^{-i}),

and each factor is one shift-and-add. When the series for exp⁡(t)\exp(t) is long, sinh⁡t\sinh t is computed instead (half the terms) and exp⁡(t)=sinh⁡t+1+sinh⁡2t\exp(t) = \sinh t + \sqrt{1 + \sinh^2 t}.

Logarithm. Dually, a product P=∏i∈U(1+2−i)P = \prod_{i \in U}(1 + 2^{-i}) is built greedily below X=1+xX = 1 + x, each accepted factor one shift-and-add, and

log⁡X=∑i∈ULi+2atanh⁡X−PX+P.\log X = \sum_{i \in U} L_i + 2\operatorname{atanh}\frac{X - P}{X + P}.

The numerator is the exact deficit maintained through the reduction, and the single division both normalises by PP and produces the atanh argument, whose series has half the terms of that of log⁡(1+u)\log(1 + u).

Arctangent. The vector (X,Y)=(1,x)(X, Y) = (1, x) is rotated by the factors 1−i2−i1 - i 2^{-i} whenever Y≥2−iXY \ge 2^{-i} X, that is whenever the angle atan⁡(Y/X)≥Ai\operatorname{atan}(Y/X) \ge A_i. This is the greedy reduction of the angle with steps AiA_i, so atan⁡(Y/X)<2−r\operatorname{atan}(Y/X) < 2^{-r} at the end, and atan⁡x=∑i∈UAi+atan⁡(Y/X)\operatorname{atan} x = \sum_{i \in U} A_i + \operatorname{atan}(Y/X) with one division. The decisions compare YY with a shift of XX and never read the table; the growth of ∣X+iY∣|X + iY| needs no compensation because angles are scale invariant.

Half-angle reconstruction#

For the sine and cosine, the angle x/2x/2 is reduced greedily by the AiA_i, i≥1i \ge 1 (by Lemma 1, since x/2<1/2<2A1x/2 < 1/2 < 2A_1), and the used indices define W=wx+iwy=∏i∈U(1+i2−i)W = w_x + i w_y = \prod_{i \in U} (1 + i 2^{-i}), whose argument is ∑i∈UAi\sum_{i \in U} A_i. Halving is needed because the decisions are taken on a short model of the remainder that requires table entries below 2−i2^{-i}; the doubled angles 2Ai2A_i would not qualify.

Theorem 2. Let x/2=arg⁡W+t′x/2 = \arg W + t' and u=tan⁡t′u = \tan t'. With T=wy+wxuT = w_y + w_x u and D=wx−wyuD = w_x - w_y u,

sin⁡x=2TDD2+T2,cos⁡x=1−2T2D2+T2,tan⁡x=2TDD2−T2.\sin x = \frac{2TD}{D^2 + T^2}, \qquad \cos x = 1 - \frac{2T^2}{D^2 + T^2}, \qquad \tan x = \frac{2TD}{D^2 - T^2}.

Proof. By the addition formula, tan⁡(x/2)=tan⁡(arg⁡W+t′)=(wy/wx+u)/(1−uwy/wx)=T/D\tan(x/2) = \tan(\arg W + t') = (w_y/w_x + u)/(1 - u w_y/w_x) = T/D. The formulas follow from sin⁡x=2τ/(1+τ2)\sin x = 2\tau/(1 + \tau^2), cos⁡x=(1−τ2)/(1+τ2)\cos x = (1 - \tau^2)/(1 + \tau^2) and tan⁡x=2τ/(1−τ2)\tan x = 2\tau/(1 - \tau^2) with τ=T/D\tau = T/D, after multiplying numerator and denominator by D2D^2.

The quotient T/DT/D is never formed: each output costs one reciprocal and one high product. The modulus ∣W∣|W| cancels, so no scale factor ∏(1+2−2i)1/2\prod(1 + 2^{-2i})^{1/2} is needed, and in the limb version the residual enters through sin⁡t′\sin t' and g=1−cos⁡t′g = 1 - \cos t' as T=wy+wxsin⁡t′−wygT = w_y + w_x \sin t' - w_y g and D=wx−wxg−wysin⁡t′D = w_x - w_x g - w_y \sin t', the common factor cos⁡t′\cos t' cancelling as well.

Signed digits on vector lanes#

From a few limbs on 64-bit machines, the bitwise reductions use signed digits di∈{−1,0,1}d_i \in \{-1, 0, 1\}: for the exponential, x=∑di=1ai−∑di=−1bi+tx = \sum_{d_i = 1} a_i - \sum_{d_i = -1} b_i + t with ai=Lia_i = L_i and bi=−log⁡(1−2−i)b_i = -\log(1 - 2^{-i}), the digit did_i chosen by comparing xx with ±0.75⋅2−i\pm 0.75 \cdot 2^{-i}. Since ai≈bi≈2−ia_i \approx b_i \approx 2^{-i}, the remainder satisfies ∣x∣≲2−i|x| \lesssim 2^{-i} before step ii for any decision taken on an approximation of xx within about 0.2⋅2−i0.2 \cdot 2^{-i} (to first order, a remainder below 0.75⋅2−i0.75 \cdot 2^{-i} is kept, and one above it drops by about 2−i2^{-i}; the tolerance of 0.25⋅2−i0.25 \cdot 2^{-i} shrinks by the second-order terms). The decisions therefore run on a 64-bit model of the remainder, refreshed every 52 indices from a short head, and never branch on the full-precision operand; about r/3r/3 digits are nonzero, against r/2r/2 for the unsigned greedy reduction.

The full-precision operands are held in radix 2562^{56} in the 64-bit lanes of vec4n vectors (see machine_vectors.h) in carry-save form: every addition of a table entry and every shift-and-add of the reconstruction is a lanewise vector operation, and the eight bits of headroom per lane admit about 60 operations between carry normalisations. The same scheme serves the logarithm (driving 1+x1 + x multiplicatively to 1), the arctangent (signed rotations) and the half-angle reconstruction. Measured on x86-64 with AVX2, this is 1.05 to 1.5 times faster than the limb version, and the cheaper reduction moves the optimal rr up (to 768 at several hundred limbs).

The reduction parameter rr trades the table and reduction work against the length of the remainder's series. Its default is tuned per function and size: per size at four to ten limbs, where the candidates are the table depths 7L−17L - 1, and from a ladder of values beyond (from 64 at a dozen limbs to 768).

Use in FLINT#

Referenced from#

References#

  • [Tan1989] P. T. P. Tang. Table-driven implementation of the exponential function in IEEE floating-point arithmetic. ACM Transactions on Mathematical Software 15:2 (1989), 144–157. https://doi.org/10.1145/63522.214389
  • [BKM1994] J.-C. Bajard, S. Kla and J.-M. Muller. BKM: a new hardware algorithm for complex elementary functions. IEEE Transactions on Computers 43:8 (1994), 955–963. https://doi.org/10.1109/12.295857
  • [Mul2016] J.-M. Muller. Elementary Functions: Algorithms and Implementation, third edition. Birkhäuser, 2016. https://doi.org/10.1007/978-1-4899-7983-4
Cite this page

The FLINT team, “Table-based argument reduction,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/special-functions/elementary-tables.html (generated 2026-11-17).