FLINT3.7.0-dev
Algorithm

Elementary functions

Cost
O(n2)O(n^2) word operations up to a few hundred limbs; O(M(n)log⁡2n)O(M(n)\log^2 n) at high precision (O(M(n)log⁡n)O(M(n)\log n) 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 πx\pi x, 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, B=2FLINT_BITSB = 2^{\mathtt{FLINT\_BITS}}, nn is a number of limbs and pp a number of bits.

Overview#

An evaluation has three stages.

  1. Argument reduction. The argument xx, a floating-point number, is reduced to a fixed-point number v∈[0,1)v \in [0, 1): by multiples of log⁡2\log 2 for the exponential, by the exponent for the logarithm, by multiples of π/2\pi/2 for the trigonometric functions (exactly by 1/21/2 for the functions of πx\pi x), and to ∣x∣<1|x| < 1 for the arctangent (Argument reduction).
  2. The kernel computes f(v)f(v) for v∈[0,1)v \in [0, 1) at nn limbs with an error bound in units of B−nB^{-n}. The kernel is chosen by size:

    Limbsexp, sin, coslogatan
    1–3table-driventable-driventable-driven
    4–32dense tablesdense tablesdense tables
    33–600bitwisebitwisebitwise
    601–65536multi-primeNewton–TaylorNewton–Taylor
    abovetable-freeNewton–TaylorNewton–Taylor

    The table-based kernels reduce vv further, against tables of logarithms or arctangents, to a remainder t<2−rt < 2^{-r}; the multi-prime kernels reduce by integer combinations of logarithms of primes (or arguments of Gaussian primes); the table-free kernels halve the argument.

  3. The reduced series. The function at the remainder tt 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 rr while that of a table-based reduction does not.

The reconstruction undoes the reductions: a product of the factors 1+2−i1 + 2^{-i} 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, mm is the argument, an exact dyadic number (the midpoint, for a ball).

Exponential. For ∣m∣≥log⁡2|m| \ge \log 2, write ∣m∣=qlog⁡2+t|m| = q\log 2 + t with t∈[0,log⁡2)t \in [0, \log 2). The quotient qq is computed from the top limbs of mm and two limbs of 1/log⁡21/\log 2 (stored as the fraction 1/log⁡2−11/\log 2 - 1), which gives qq or q−1q - 1; one multiply-subtract by the cached floor of log⁡2\log 2 and a correction give tt. For m<0m < 0 the quotient is rounded up and the remainder complemented, so that exp⁡(m)=2−qexp⁡(t′)\exp(m) = 2^{-q}\exp(t') with t′∈[0,log⁡2)t' \in [0, \log 2) and no division. In the ball functions of mp_real the bound ∣m∣<2FLINT_BITS−5|m| < 2^{\mathtt{FLINT\_BITS} - 5} 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, m∈(−1,0)m \in (-1, 0) is evaluated as 1/exp⁡(∣m∣)1/\exp(|m|) when ∣m∣<2−128|m| < 2^{-128}, or when ∣m∣|m| 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 v∈[0,1)v \in [0, 1) with zz leading zero bits and ℓ\ell significant bits below them goes to the bit-burst directly when ℓ\ell is below a bound that grows with zz and the precision: from 64 bits (z≥16z \ge 16) at 600 to 2000 limbs to 1024 (z<16z < 16), 4096 (z≥16z \ge 16) and 32768 bits (z≥64z \ge 64) from 30000 limbs. At 51907 limbs, for example, exp⁡(−x)\exp(-x) with xx a 64-bit number below 2−642^{-64} takes 0.046 s instead of 0.31 s, and exp⁡(x)\exp(x) 0.039 s instead of 0.30 s (the profile program p-exp_window measures these choices).

Logarithm. For m=2Eum = 2^E u with u∈[1/2,1)u \in [1/2, 1), log⁡m=(E−1)log⁡2+log1p⁡(2u−1)\log m = (E - 1)\log 2 + \operatorname{log1p}(2u - 1) (up to 600 limbs) or Elog⁡2−(−log⁡u)E\log 2 - (-\log u) (beyond). Near m=1m = 1 both forms cancel up to z+1z + 1 bits for ∣m−1∣<2−z|m - 1| < 2^{-z}, and the working precision is raised by that much; for larger zz the function uses log⁡(1±s)=±2atanh⁡(s/(2±s))\log(1 \pm s) = \pm 2\operatorname{atanh}(s/(2 \pm s)) with s=∣m−1∣s = |m - 1| and the reduced atanh series.

Sine and cosine. For ∣m∣≥1|m| \ge 1, the quotient qq approximating 2∣m∣/π2|m|/\pi from below makes t=∣m∣−qπ/2≥0t = |m| - q\pi/2 \ge 0; a fold v=π/2−tv = \pi/2 - t for t>π/4t > \pi/4 brings the argument into [0,π/4][0, \pi/4], and the outputs are permuted and negated according to q mod 4q \bmod 4. The constant 2/π2/\pi for the quotient and π/4\pi/4 for the remainder come from the caches. The reduction is absolute: near a nonzero multiple of π\pi 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 ±tan⁡v\pm\tan v or ∓1/tan⁡v\mp 1/\tan v. Near a zero or a pole, vv is small and an absolute error is a relative error of the result, so the kernel runs with the leading zero bits of vv as extra precision, repeating the reduction at the higher precision when needed. This terminates because π\pi has finite irrationality measure, at most 7.117.11 [ZZ2020]: a bb-bit dyadic mm satisfies ∣m−kπ/2∣≳2−7.2b|m - k\pi/2| \gtrsim 2^{-7.2b} for large bb, so a repetition beyond 8b+10248b + 1024 extra bits is never needed (and is not made: the ball function of mp_real then reports failure).

Functions of πx\pi x. For sin⁡(πm)\sin(\pi m), cos⁡(πm)\cos(\pi m) and tan⁡(πm)\tan(\pi m) the reduction is exact: the units bit and the fraction bits of the dyadic midpoint give ∣m∣=a/2+st|m| = a/2 + st with a∈{0,1,2,3}a \in \{0, 1, 2, 3\}, s=±1s = \pm 1 and t∈[0,1/4]t \in [0, 1/4], and v=πtv = \pi t goes to the kernel with the leading zero bits of tt as extra precision. The results therefore keep their relative accuracy near every zero and pole, and multiples of 1/21/2 (and odd multiples of 1/41/4 for the tangent) give exact results.

Inverse functions. atan⁡\operatorname{atan} reduces ∣m∣≥1|m| \ge 1 by atan⁡(m)=π/2−atan⁡(1/m)\operatorname{atan}(m) = \pi/2 - \operatorname{atan}(1/m) (or π/4+atan⁡((m−1)/(m+1))\pi/4 + \operatorname{atan}((m - 1)/(m + 1)) for 1<m<21 < m < 2). The other inverse and hyperbolic functions are compositions without cancellation, listed under mp_real_log1p_bits; for example acosh⁡(m)=log1p⁡(d+d(m+1))\operatorname{acosh}(m) = \operatorname{log1p}(d + \sqrt{d(m + 1)}) with d=m−1d = m - 1 computed exactly.

Hyperbolic functions and powers. sinh⁡\sinh, cosh⁡\cosh and tanh⁡\tanh are formed from E=e∣x∣E = e^{|x|} and one approximate reciprocal, with the precision raised by the bits that cancel in E−1/EE - 1/E for ∣x∣<1|x| < 1. xyx^y is exp⁡(t)\exp(t) with t=ylog⁡∣x∣t = y \log|x|: the logarithm is computed to as many more bits as the magnitude of tt needs, multiplied exactly by the mantissa of yy, 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 log⁡2\log 2 has as many bits as the exponent, and for the trigonometric functions, which need π\pi to about e+pe + p bits for an argument 2e2^e. 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 tt is any real number,

−log⁡x=t−log⁡(1+w),w=xet−1,atan⁡x=t+atan⁡w,w=xcos⁡t−sin⁡txsin⁡t+cos⁡t,-\log x = t - \log(1 + w), \quad w = x e^t - 1, \qquad \operatorname{atan} x = t + \operatorname{atan} w, \quad w = \frac{x\cos t - \sin t}{x\sin t + \cos t},

exactly (the second for ∣atan⁡x−t∣<π/2|{\operatorname{atan} x - t}| < \pi/2). If tt is correct to p0p_0 bits, then ∣w∣<2−p0|w| < 2^{-p_0}, and p/p0p/p_0 terms of the Taylor series of log⁡(1+w)\log(1 + w) or atan⁡w\operatorname{atan} w give pp bits; since the kk-th term has kp0kp_0 leading zero bits, the series costs a fraction of one multiplication. The starting value is computed at p0≈p/(N+1)p_0 \approx p/(N + 1) bits (for the arctangent, whose series is in w2w^2, p/(2N)p/(2N)) 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 ww, 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 O(M(n)log⁡n)O(M(n)\log n) algorithm, from the arithmetic-geometric mean [Sal1976] [Bre1976agm]. _mp_real_neglog_agm uses the formula of Sasaki and Kanada [SK1982],

log⁡1q=πagm⁡(θ2(q)2, θ3(q)2),0<q<1,\log\frac{1}{q} = \frac{\pi}{\operatorname{agm}(\theta_2(q)^2,\, \theta_3(q)^2)}, \qquad 0 < q < 1,

with θ2(q)=2q1/4∑k≥0qk(k+1)\theta_2(q) = 2q^{1/4}\sum_{k \ge 0} q^{k(k+1)} and θ3(q)=1+2∑k≥1qk2\theta_3(q) = 1 + 2\sum_{k \ge 1} q^{k^2}. For x∈[1/2,1)x \in [1/2, 1) it sets r=x2−er = x 2^{-e} and q=r4q = r^4, so that q1/4=rq^{1/4} = r needs no root:

−log⁡x=π/4agm⁡(4r2S22, θ32)−elog⁡2,S2=∑k≥0qk(k+1).-\log x = \frac{\pi/4}{\operatorname{agm}(4r^2 S_2^2,\, \theta_3^2)} - e\log 2, \qquad S_2 = \sum_{k \ge 0} q^{k(k+1)}.

The shift ee makes qq small enough that NN terms of the theta series suffice (e=⌈p/(4(N+1)2)⌉e = \lceil p/(4(N + 1)^2)\rceil); the merged exponents of the two series are ⌊j2/4⌋\lfloor j^2/4 \rfloor, consecutive ones differing by ⌊j/2⌋\lfloor j/2 \rfloor, so the series cost about one product per term. The first AGM step needs no square root, since θ22θ32=(2rS2θ3)2\theta_2^2\theta_3^2 = (2rS_2\theta_3)^2. The AGM itself runs about log⁡2e\log_2 e 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 7⋅1057 \cdot 10^5 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 YY and an error count ε\varepsilon such that the true value lies within ε\varepsilon units of Y2eY 2^{e}, where 2e2^e is the unit of the frame (a power of BB, shifted by the binary exponent of the reduction). Some bounds are one-sided – the value lies in [Y,Y+ε][Y, Y + \varepsilon] or [Y−ε,Y][Y - \varepsilon, Y] – 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 πx\pi x; 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 ∣q∣(log⁡2−L)|q| (\log 2 - L) for the floor LL of log⁡2\log 2, 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 (sin⁡x\sin x near a multiple of π\pi, log⁡x\log x near 1, tan⁡\tan and atan⁡\operatorname{atan} 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 πx\pi x, 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 ∣x∣<2−p/2|x| < 2^{-p/2} or so, exe^x, log⁡(1+x)\log(1 + x), sin⁡x\sin x, atan⁡x\operatorname{atan} x and so on are 11 or xx times 1+δ1 + \delta with a tiny δ\delta 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 c(1+δ)c(1 + \delta) with a tiny δ\delta 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 Y2eY 2^e rounded to prec bits and the radius is the error count times 2e2^e 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 [m±r][m \pm r] and proceeds as follows.

  1. 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_exp returns [0±∞][0 \pm \infty] or a tiny ball when ∣m∣>2max⁡(128,2p)|m| > 2^{\max(128, 2p)}, and arb_sin_cos returns [0±1][0 \pm 1] when ∣m∣>2max⁡(65536,4p)|m| > 2^{\max(65536, 4p)}.
  2. If r>0r > 0, 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 sin⁡\sin and cos⁡\cos, the endpoints and the extrema in between).
  3. 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 ∣sin⁡m∣|\sin m| and ∣cos⁡m∣|\cos m| read from the top bits of the frames, so that the error of sin⁡\sin is bounded by r∣cos⁡m∣+r2/2r |\cos m| + r^2/2 and that of cos⁡\cos by r∣sin⁡m∣+r2/2r |\sin m| + r^2/2; the hyperbolic functions use rcosh⁡m (1+2r)r \cosh m \,(1 + 2r) for r≤1/2r \le 1/2 from the frame of cosh⁡m\cosh m, and the exponential em(er−1)e^m (e^r - 1). For the functions of πx\pi x the bounds are multiplied by π\pi. The logarithm bounds the error of log⁡[m±r]\log [m \pm r], r<mr < m, by log⁡(1+r/(m−r))\log(1 + r/(m - r)) and the arctangent by r/(1+(∣m∣−r)2)r / (1 + (|m| - r)^2).

Derived functions#

The constants π\pi and log⁡2\log 2 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#

void arb_exp(arb_t z, const arb_t x, slong prec)
void arb_log(arb_t z, const arb_t x, slong prec)
void arb_sin_cos(arb_t s, arb_t c, const arb_t x, slong prec)
void arb_atan(arb_t z, 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)
slong _mp_real_exp_fp(nn_ptr y, ulong * err, nn_srcptr d, slong n, slong e, int sgnbit, slong pb)
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)

Referenced from#

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

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