Elementary functions
- Cost
- word operations up to a few hundred limbs; at high precision ( for the AGM logarithm), plus the cost of the argument reduction for huge arguments.
All elementary functions in FLINT – the exponential, the logarithm, sine, cosine and tangent, the arctangent, the functions of , and the hyperbolic, inverse and reciprocal functions derived from them – are evaluated by one set of fixed-point kernels in the mp_real module. The kernels cover precisions from one limb, where an evaluation takes a few dozen nanoseconds, to hundreds of millions of bits. The number types wrap them: arf rounds their results correctly, nfloat rounds them once to a fixed precision, arb turns them into balls, and acb, acf and nfloat_complex combine the real functions into complex ones. The design follows [Joh2014c] (medium precision) and [HJ2024] (high precision with precomputation), with the classical algorithms of Brent [Bre1976agm] [Bre1976b]; [Mul2016] and [BZ2011] are general references.
Throughout, , is a number of limbs and a number of bits.
Overview#
An evaluation has three stages.
- Argument reduction. The argument , a floating-point number, is reduced to a fixed-point number : by multiples of for the exponential, by the exponent for the logarithm, by multiples of for the trigonometric functions (exactly by for the functions of ), and to for the arctangent (Argument reduction).
The kernel computes for at limbs with an error bound in units of . The kernel is chosen by size:
Limbs exp, sin, cos log atan 1–3 table-driven table-driven table-driven 4–32 dense tables dense tables dense tables 33–600 bitwise bitwise bitwise 601–65536 multi-prime Newton–Taylor Newton–Taylor above table-free Newton–Taylor Newton–Taylor The table-based kernels reduce further, against tables of logarithms or arctangents, to a remainder ; the multi-prime kernels reduce by integer combinations of logarithms of primes (or arguments of Gaussian primes); the table-free kernels halve the argument.
- The reduced series. The function at the remainder is a Taylor series, evaluated by rectangular splitting at moderate precision and by the bit-burst algorithm at high precision. The series is also called directly when the argument itself is small enough, since its cost falls with while that of a table-based reduction does not.
The reconstruction undoes the reductions: a product of the factors or a power of two for the exponential, a sum of tabulated logarithms for the logarithm, a rotation or the half-angle formulas for the sine and cosine. Each stage has an error bound in units of its last limb, and the bounds add up to the error count that the kernel returns (Fixed-point frames and error bounds).
Argument reduction#
Below, is the argument, an exact dyadic number (the midpoint, for a ball).
Exponential. For , write with . The quotient is computed from the top limbs of and two limbs of (stored as the fraction ), which gives or ; one multiply-subtract by the cached floor of and a correction give . For the quotient is rounded up and the remainder complemented, so that with and no division. In the ball functions of mp_real the bound keeps the exponent of the result in the safe range of Ball arithmetic with limb-granular radii; the floating-point entry points return a larger quotient as a multiprecision integer.
Both reductions turn a short argument into a full-length one, which costs a full exponential however few bits the argument has, whereas the cost of the bit-burst evaluation grows with the number of bits. So beyond the bitwise kernels, is evaluated as when , or when is short enough for the next rule (always above 65536 limbs, where the table-free kernel is a bit-burst anyway); and in the range of the diophantine kernel, an argument with leading zero bits and significant bits below them goes to the bit-burst directly when is below a bound that grows with and the precision: from 64 bits () at 600 to 2000 limbs to 1024 (), 4096 () and 32768 bits () from 30000 limbs. At 51907 limbs, for example, with a 64-bit number below takes 0.046 s instead of 0.31 s, and 0.039 s instead of 0.30 s (the profile program p-exp_window measures these choices).
Logarithm. For with , (up to 600 limbs) or (beyond). Near both forms cancel up to bits for , and the working precision is raised by that much; for larger the function uses with and the reduced atanh series.
Sine and cosine. For , the quotient approximating from below makes ; a fold for brings the argument into , and the outputs are permuted and negated according to . The constant for the quotient and for the remainder come from the caches. The reduction is absolute: near a nonzero multiple of the reduced argument is small and its leading bits cancel. The floating-point entry points used by arf and arb repeat the reduction with as many more bits as cancel, so that the result keeps its relative accuracy; the ball functions of mp_real show the cancellation in the radius instead.
Tangent. The tangent is reduced the same way and finished as or . Near a zero or a pole, is small and an absolute error is a relative error of the result, so the kernel runs with the leading zero bits of as extra precision, repeating the reduction at the higher precision when needed. This terminates because has finite irrationality measure, at most [ZZ2020]: a -bit dyadic satisfies for large , so a repetition beyond extra bits is never needed (and is not made: the ball function of mp_real then reports failure).
Functions of . For , and the reduction is exact: the units bit and the fraction bits of the dyadic midpoint give with , and , and goes to the kernel with the leading zero bits of as extra precision. The results therefore keep their relative accuracy near every zero and pole, and multiples of (and odd multiples of for the tangent) give exact results.
Inverse functions. reduces by (or for ). The other inverse and hyperbolic functions are compositions without cancellation, listed under mp_real_log1p_bits; for example with computed exactly.
Hyperbolic functions and powers. , and are formed from and one approximate reciprocal, with the precision raised by the bits that cancel in for . is with : the logarithm is computed to as many more bits as the magnitude of needs, multiplied exactly by the mantissa of , and the exponential of the result is returned with the binary exponent of the reduction.
Huge arguments. The reductions are exact or carried to the precision the exponent of the argument requires, so their cost grows with the exponent: linearly for the exponential, whose quotient by has as many bits as the exponent, and for the trigonometric functions, which need to about bits for an argument . The wrappers therefore bound the exponent in terms of the precision (see Balls in arb).
The kernels#
The algorithms of the kernels have pages of their own:
The logarithm and the arctangent at more than 600 limbs, and the AGM logarithm, are described here.
Newton–Taylor inversion#
Above 600 limbs the logarithm and the arctangent are computed from the forward functions. If is any real number,
exactly (the second for ). If is correct to bits, then , and terms of the Taylor series of or give bits; since the -th term has leading zero bits, the series costs a fraction of one multiplication. The starting value is computed at bits (for the arctangent, whose series is in , ) by the bitwise kernel or recursively, so the whole costs one forward evaluation plus about a tenth of one. Everything around the forward function is ball arithmetic: the cancellation in , the forward function's error, the series and its tail are carried by the radii. This is a single Newton step of high order in the sense of [BZ2011].
The AGM logarithm#
The logarithm also has an algorithm, from the arithmetic-geometric mean [Sal1976] [Bre1976agm]. _mp_real_neglog_agm uses the formula of Sasaki and Kanada [SK1982],
with and . For it sets and , so that needs no root:
The shift makes small enough that terms of the theta series suffice (); the merged exponents of the two series are , consecutive ones differing by , so the series cost about one product per term. The first AGM step needs no square root, since . The AGM itself runs about iterations in its slow phase and is finished by the series of mp_real_agm.
With warm caches the Newton–Taylor logarithm over the diophantine exponential is faster up to about limbs; without tables, the AGM logarithm wins from about 20000 limbs, which is why mp_real_exp_agm uses it.
Fixed-point frames and error bounds#
A kernel returns a fixed-point frame: an array of limbs and an error count such that the true value lies within units of , where is the unit of the frame (a power of , shifted by the binary exponent of the reduction). Some bounds are one-sided – the value lies in or – which the wrappers use to decide roundings near exact values. The floating-point entry points of mp_real (_mp_real_exp_fp, _mp_real_log_fp, _mp_real_log1p_fp, _mp_real_sin_cos_fp, _mp_real_tan_fp, _mp_real_atan_fp, _mp_real_atan2_fp, _mp_real_sinh_cosh_fp, _mp_real_tanh_fp, _mp_real_pow_fp and the functions of ; see Elementary functions of floating-point mantissas) take the mantissa and exponent of a floating-point argument and a target precision in bits, perform the reduction and choose the number of limbs of the kernel, and return the frame. Their contract makes the error bound independent of the path taken: the reduction contributes the errors of the tabulated constants times the quotient (for example for the floor of , which the constant's extra limbs keep below a unit), the kernel its own count, and the reconstruction one unit per truncated product. The counts are bounded in terms of the kernel's parameters (they grow linearly with the reduction depth of the bitwise kernels, to a few thousand units at most) and are a few units on the common paths; each wrapper turns the count into its own error bound or rounding decision, so that a large count costs accuracy (or a retry) but never correctness. Three situations need special care:
- Relative accuracy near zeros. Near a zero of the function ( near a multiple of , near 1, and near 0) an absolute error is a relative error of the result, so the entry points add the leading zero bits of the reduced argument to the number of limbs, and repeat the reduction at the higher precision when needed. The functions of , whose reduction is exact, keep their relative accuracy near every zero and pole.
- Reciprocals. For the cotangent, cosecant and the reciprocal hyperbolic functions the wrappers divide by the frame; the entry points choose their limbs so that the frame normalises with a short shift, and the division is done at the frame's own precision.
- Tiny arguments. For or so, , , , and so on are or times with a tiny of known sign; the wrappers return that directly, at any exponent, without evaluating a kernel (and a Taylor polynomial of degree two or three serves a little further).
The thresholds between kernels are tuned by measurement and do not affect the error bounds.
Register fast paths#
On 64-bit machines, arguments with a mantissa of one or two limbs at a target precision of at most one or two limbs are evaluated entirely in registers by inline functions shared by arf, nfloat, arb, acb and acf (arf/elem.h, acf/elem.h): they perform the reduction in double arithmetic with exact integer corrections, evaluate the table-driven kernels of three or four words, and return a frame with an error count of a few units, falling back to the general entry points for arguments outside their range. These paths give the elementary functions their speed at 64 and 128 bits, where the general code would spend most of its time in setup.
From kernels to number types#
arf (Correctly rounded elementary functions) rounds a frame correctly when the bits between the rounding point and the error bound decide the rounding, and otherwise repeats the evaluation with more guard bits (Ziv's strategy); exact results and values of the form with a tiny are handled without evaluation. The relaxed modes ARF_RND_FAST and ARF_RND_ACCURATE round the first frame.
nfloat evaluates once, at the function precision of the context plus 12 guard bits (16 from 4096 bits on, where the error bounds of the bitwise kernels grow), and rounds the frame to the precision of the context: the result is within about one ulp, and with the directed rounding flags it is a valid bound, the error count being added in the direction of rounding.
arb (Balls in arb) converts a frame for the exact midpoint into a ball and adds the propagated error of the radius.
acb, acf and nfloat_complex combine the real functions by formulas that keep each part accurate; see Complex elementary functions.
Balls in arb#
A point evaluation such as arb_exp_arf, arb_log_arf or arb_atan_arf evaluates the entry point at the precision plus the same guard bits as nfloat and converts the frame into a ball: the midpoint is rounded to prec bits and the radius is the error count times plus the rounding error of the midpoint. The radius therefore stays within a few ulps, and the result has close to prec bits of relative accuracy, also near zeros. A ball function such as arb_exp receives and proceeds as follows.
- Special values (zero, infinities, NaN, an infinite radius) are handled directly, and so are arguments beyond the magnitude limits, which keep the cost polynomial in the precision (The polynomial time guarantee):
arb_expreturns or a tiny ball when , andarb_sin_cosreturns when . - If , the precision is lowered to about the relative accuracy of the input plus 20 to 30 bits; more bits would be hidden by the propagated error. If the input has less than about 20 bits of accuracy, the function is evaluated on the interval instead, using its monotonicity (for and , the endpoints and the extrema in between).
- Otherwise the function of the exact midpoint is computed by the point evaluation, and the propagated error is added.
The propagated error uses a bound on the derivative over the ball (Elementary functions), which the point evaluation provides nearly for free: the sine and cosine return upper bounds of and read from the top bits of the frames, so that the error of is bounded by and that of by ; the hyperbolic functions use for from the frame of , and the exponential . For the functions of the bounds are multiplied by . The logarithm bounds the error of , , by and the arctangent by .
Derived functions#
arb_expm1andarb_log1puse the entry points with the subtraction of 1 built in, at a precision increased by the bits that would be lost to cancellation for small arguments.arb_sinh_cosh,arb_tanhandarb_cothare computed from the hyperbolic entry points;arb_asinh,arb_acoshandarb_atanhfromarb_log,arb_log1pandarb_sqrt.arb_asinandarb_acosuse , andarb_atan2combinesarb_atanwith .arb_sin_piandarb_cos_pireduce modulo exactly before multiplying by , so they are exact at integers and half-integers and accurate near the zeros; a dyadic with a small denominator, like a rational inarb_sin_cos_pi_fmpqandarb_tan_pi_fmpq, is evaluated as an algebraic number where that is faster (Sines and cosines of rational multiples of π).arb_powwith exact arguments and a positive base (or an integer exponent) evaluates in one go; otherwise it is in ball arithmetic, with the special cases of Powers and roots.- In
arf,nfloatandacfthe less common functions (arf_asin,arf_acosh,arf_log10,arf_sinc_pi, ...) are compositions of the ones above at a few more bits, with an explicit bound for the error of the composition; one-sided expansions near the singular points (such as near , or for huge ) avoid the stalls of two-sided bounds. - Logarithms of smooth integers at high precision are assembled from cached logarithms of primes (
arb_log_ui_from_prev,arb_log_primes_vec_bsplit).
The constants and used by the reductions, and by arb_const_pi and arb_const_log2, are kept as exact floors in static tables and a shared cache (Caching).
Use in FLINT#
- The ball functions of
mp_real(mp_real_exp_bits,mp_real_log_bits,mp_real_sin_cos_bits, ...) apply the same reductions and kernels tomp_real_tballs, with the radius propagated like that ofarb(Elementary functions of balls). - The floating-point entry points serve
arf(Elementary functions),nfloat(Elementary functions),arb(Elementary functions), and through themacb,acfandnfloat_complex.
void arb_sin_cos(arb_t s, arb_t c, const arb_t x, slong prec)int arf_exp(arf_ptr res, arf_srcptr x, slong prec, arf_rnd_t rnd)int arf_log(arf_ptr res, arf_srcptr x, slong prec, arf_rnd_t rnd)int arf_sin_cos(arf_ptr res1, arf_ptr res2, arf_srcptr x, slong prec, arf_rnd_t rnd)int arf_atan(arf_ptr res, arf_srcptr x, slong prec, arf_rnd_t rnd)int _mp_real_log_fp(nn_ptr y, slong * len, slong * ue, ulong * err, nn_srcptr d, slong n, slong e, int base2, slong pb)int _mp_real_sin_cos_fp(nn_ptr ys, nn_ptr yc, slong * w, ulong * err, nn_srcptr d, slong n, slong e, slong pb, slong wmax, int rel)void _mp_real_atan_fp(nn_ptr y, slong * w, ulong * err, nn_srcptr d, slong n, slong e, slong pb, slong wmax)int _mp_real_pow_fp(nn_ptr y, ulong * err, nn_ptr q, slong * qn, int * tsgn, nn_srcptr xd, slong xn, slong xe, nn_srcptr yd, slong yn, slong ye, int ysgn, slong pb, slong tbmax)void _mp_real_neglog_newton(nn_ptr y, ulong * err, nn_srcptr x, slong n)void _mp_real_atan_newton(nn_ptr y, ulong * err, nn_srcptr x, slong n)void _mp_real_neglog_agm(nn_ptr y, ulong * err, nn_srcptr x, slong n)Referenced from#
- Correctly rounded elementary functions (algorithm)
- Floating-point arithmetic (overview)
- Ball arithmetic with limb-granular radii (algorithm)
- Floating-point arithmetic in FLINT (overview)
- Complex elementary functions (algorithm)
- Mathematical constants (algorithm)
- Series evaluation and the bit-burst algorithm (algorithm)
- Table-based argument reduction (algorithm)
- Hypergeometric functions (algorithm)
- Special functions (overview)
- Sines and cosines of rational multiples of π (algorithm)
- Elementary functions
- arb.h (module)
- arf.h (module)
mp_real_exp_notab_log2,mp_real_exp_notab_squaring,mp_real_exp_agm- Elementary functions of balls
- Fixed-point kernels
- mp_real.h (module)
- nfloat.h (module)
References#
- [Joh2014c] F. Johansson, "Efficient implementation of elementary functions in the medium-precision range", 22nd IEEE Symposium on Computer Arithmetic (ARITH 22), 83-89 (2015), https://arxiv.org/abs/1410.7176
- [HJ2024] J. van der Hoeven and F. Johansson, "Fast multiple precision exp(x) with precomputations", 2024 IEEE 31st Symposium on Computer Arithmetic (ARITH) (2024), https://hal.science/hal-04454093
- [Bre1976agm] R. P. Brent. Fast multiple-precision evaluation of elementary functions. Journal of the ACM 23:2 (1976), 242–251. https://doi.org/10.1145/321941.321944
- [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.
- [Mul2016] J.-M. Muller. Elementary Functions: Algorithms and Implementation, third edition. Birkhäuser, 2016. https://doi.org/10.1007/978-1-4899-7983-4
- [BZ2011] R. P. Brent and P. Zimmermann, Modern Computer Arithmetic, Cambridge University Press (2011), http://www.loria.fr/~zimmerma/mca/pub226.html
- [ZZ2020] D. Zeilberger and W. Zudilin. The irrationality measure of π is at most 7.103205334137... Moscow Journal of Combinatorics and Number Theory 9:4 (2020), 407–419. https://doi.org/10.2140/moscow.2020.9.407
- [Sal1976] E. Salamin. Computation of π using arithmetic-geometric mean. Mathematics of Computation 30:135 (1976), 565–570. https://doi.org/10.2307/2005327
- [SK1982] T. Sasaki and Y. Kanada. Practically fast multiple-precision evaluation of log(x). Journal of Information Processing 5:4 (1982), 247–250.
The FLINT team, “Elementary functions,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/special-functions/elementary.html (generated 2026-11-20).
@misc{flint-doc-algorithms-special-functions-elementary,
author = {{The FLINT team}},
title = {{Elementary functions}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/special-functions/elementary.html},
note = {Generated 2026-11-20}
}