Table-based argument reduction
- Cost
- word operations per evaluation at limbs with tables of entries (bitwise: table entries of limbs for a reduction depth ), plus a series of 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 and . The remainder is evaluated by the series of Series evaluation and the bit-burst algorithm. Throughout, and 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: with tables of , and (128 entries each) and a Taylor polynomial in ;
- log1p: a multiplicative reduction by short factors over three or four levels of 7 bits, with tables of , then the Taylor polynomial of ;
- sin and cos: the pairs for and combined with the polynomials of the remainder by the addition formulas;
- atan: with (513 entries) and the odd series of the quotient; for a ratio the quotient is with an exact numerator and denominator, so 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, with the top seven bits, then with for the following levels (the tables hold floors, so stays nonnegative), the series of , and the product of the factors . Logarithms use the dual multiplicative reduction, arctangents rotate the vector by factors , and the sine and cosine rotate the pair by and absorb the scale by the double-angle formulas , with , 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 or , 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 with , and . The greedy reduction, which for subtracts from if , leaves , using each at most once.
Proof. Before step we have : this holds for , and if the step leaves , otherwise ; in both cases . After step the same argument gives .
The logarithms satisfy the hypothesis, since , and so do the arctangents, by concavity of .
Exponential. After the reduction with ,
and each factor is one shift-and-add. When the series for is long, is computed instead (half the terms) and .
Logarithm. Dually, a product is built greedily below , each accepted factor one shift-and-add, and
The numerator is the exact deficit maintained through the reduction, and the single division both normalises by and produces the atanh argument, whose series has half the terms of that of .
Arctangent. The vector is rotated by the factors whenever , that is whenever the angle . This is the greedy reduction of the angle with steps , so at the end, and with one division. The decisions compare with a shift of and never read the table; the growth of needs no compensation because angles are scale invariant.
Half-angle reconstruction#
For the sine and cosine, the angle is reduced greedily by the , (by Lemma 1, since ), and the used indices define , whose argument is . Halving is needed because the decisions are taken on a short model of the remainder that requires table entries below ; the doubled angles would not qualify.
Theorem 2. Let and . With and ,
Proof. By the addition formula, . The formulas follow from , and with , after multiplying numerator and denominator by .
The quotient is never formed: each output costs one reciprocal and one high product. The modulus cancels, so no scale factor is needed, and in the limb version the residual enters through and as and , the common factor cancelling as well.
Signed digits on vector lanes#
From a few limbs on 64-bit machines, the bitwise reductions use signed digits : for the exponential, with and , the digit chosen by comparing with . Since , the remainder satisfies before step for any decision taken on an approximation of within about (to first order, a remainder below is kept, and one above it drops by about ; the tolerance of 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 digits are nonzero, against for the unsigned greedy reduction.
The full-precision operands are held in radix 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 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 up (to 768 at several hundred limbs).
The reduction parameter 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 , and from a ladder of values beyond (from 64 at a dozen limbs to 768).
Use in FLINT#
- The table-driven kernels of one to three limbs are inline functions (
mp_real/small.h), also called directly by the register paths ofarf,nfloat,arbandacfat one and two limbs. - The dense kernels are
_mp_real_exp_dense_rt,_mp_real_sin_cos_dense_rtand their siblings. - The bitwise kernels are
_mp_real_exp_bitwise_rs,_mp_real_log1p_bitwise_rs,_mp_real_sin_cos_bitwise_rs,_mp_real_atan_bitwise_rsand_mp_real_tan_bitwise_rs.
void _mp_real_exp_dense_rt(nn_ptr y, nn_srcptr v, slong n)void _mp_real_exp_bitwise_rs(nn_ptr res, ulong * err, nn_srcptr x, slong n, int r)void _mp_real_log1p_bitwise_rs(nn_ptr res, ulong * err, nn_srcptr x, slong n, int r)void _mp_real_sin_cos_bitwise_rs(nn_ptr ysin, nn_ptr ycos, ulong * err, nn_srcptr x, slong n, int r)void _mp_real_atan_bitwise_rs(nn_ptr res, ulong * err, nn_srcptr x, slong n, int r)void _mp_real_tan_bitwise_rs(nn_ptr res, ulong * err, nn_srcptr x, slong n, int r)Referenced from#
- Multi-prime argument reduction (algorithm)
- Series evaluation and the bit-burst algorithm (algorithm)
- Elementary functions (algorithm)
_mp_real_exp_bitwise_rs,_mp_real_log1p_bitwise_rs,_mp_real_sin_cos_bitwise_rs,_mp_real_tan_bitwise_rs,_mp_real_atan_bitwise_rs_mp_real_small_exp_1_mpn,_mp_real_small_exp_2_mpn,_mp_real_small_exp_3_mpn,_mp_real_small_log1p_1_mpn,_mp_real_small_log1p_2_mpn,_mp_real_small_log1p_3_mpn,_mp_real_small_sin_cos_1_mpn,_mp_real_small_sin_cos_2_mpn,_mp_real_small_sin_cos_3_mpn,_mp_real_small_atan_1_mpn,_mp_real_small_atan_2_mpn,_mp_real_small_atan_3_mpn_mp_real_exp_opt_4,_mp_real_exp_opt_5,_mp_real_exp_opt_6,_mp_real_exp_opt_7,_mp_real_exp_opt_8,_mp_real_exp_opt_9,_mp_real_exp_opt_10,_mp_real_log1p_opt_4,_mp_real_log1p_opt_5,_mp_real_log1p_opt_6,_mp_real_log1p_opt_7,_mp_real_log1p_opt_8,_mp_real_log1p_opt_9,_mp_real_log1p_opt_10,_mp_real_atan_opt_4,_mp_real_atan_opt_5,_mp_real_atan_opt_6,_mp_real_atan_opt_7,_mp_real_atan_opt_8,_mp_real_atan_opt_9,_mp_real_atan_opt_10,_mp_real_sin_cos_opt_4,_mp_real_sin_cos_opt_5,_mp_real_sin_cos_opt_6,_mp_real_sin_cos_opt_7,_mp_real_sin_cos_opt_8,_mp_real_sin_cos_opt_9,_mp_real_sin_cos_opt_10_mp_real_exp_bitwise_vec,_mp_real_log1p_bitwise_vec,_mp_real_atan_bitwise_vec,_mp_real_tan_halfangle_vec
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
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).
@misc{flint-doc-algorithms-special-functions-elementary-tables,
author = {{The FLINT team}},
title = {{Table-based argument reduction}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/special-functions/elementary-tables.html},
note = {Generated 2026-11-17}
}