Correctly rounded elementary functions
- Cost
- That of one evaluation at the target precision plus 20 to 24 guard bits; a retry, with probability about , doubles the guard bits.
The elementary functions of arf (arf_exp, arf_log, arf_sin, arf_atan, arf_pow and the others of Elementary functions) return the function value rounded to prec bits in a given direction. In the strict modes (ARF_RND_DOWN, ARF_RND_UP, ARF_RND_FLOOR, ARF_RND_CEIL and ARF_RND_NEAR) the result is correctly rounded: it is the representable number that rounding the exact value would give, as for the arithmetic operations of IEEE 754 [IEEE754]. This page describes how that is achieved on top of the fixed-point kernels of Elementary functions, and the variants with a weaker guarantee: the relaxed modes of arf, the fixed-precision functions of nfloat and the complex functions of acf.
A kernel returns a fixed-point enclosure, a frame with error counts , such that the value lies in (one of the counts is zero for a one-sided bound). Correct rounding needs more than a small error: it needs to know on which side of every rounding boundary lies, which no fixed precision guarantees, since may lie arbitrarily close to a boundary. This is the table maker's dilemma [MBD2018].
Certifying a frame#
Let be the position (in units of ) of the last bit kept at prec bits, so that with the bits of above in and the discarded part , and let bound the error counts. The rounding of is decided when the enclosure lies strictly between two consecutive multiples of , that is between two rounding boundaries (for the directed modes the boundaries are the representable numbers multiples of , for rounding to nearest also the midpoints between them):
- two-sided bounds: the bits of are neither all zero nor all one;
- one-sided bounds: when is known to lie above , all zero is fine as well (and so is a exact at
precbits); when lies below , all one is fine; - rounding to nearest: when the window is all equal to the bit at and , lies within a quarter ulp of a representable number, far from the ties, and rounds to it from either side. A value exponentially close to a representable number (such as for large ) therefore needs no more precision than any other in this mode.
In each decided case rounds like with its bits below the half bit replaced by a single sticky bit, which an exact rounding of the integer then performs. The test reads a window of bits and costs nothing next to the evaluation.
Ziv's strategy#
If the window does not decide the rounding, the evaluation is repeated with more guard bits [Ziv1991]:
Input: , prec, a strict rounding mode.
Output: correctly rounded.
- Set .
- Evaluate the kernel at bits and certify the frame. If the rounding is decided, return.
- Set if it was 0, else double it, and go to 2.
With guard bits the first attempt fails with probability about for a value whose bits are random, and each retry squares the chance of failure, so that the expected cost is that of one evaluation. The doubling makes the total cost at most a constant factor more than the last attempt.
Termination#
The loop terminates whenever is not a dyadic number, since then a frame accurate enough excludes every rounding boundary. For the elementary functions at dyadic arguments this is a consequence of the Lindemann–Weierstrass theorem: is transcendental for every algebraic , and so are for algebraic , , , , and the hyperbolic functions and other inverse functions at algebraic . The remaining cases have algebraic values and are recognised before any evaluation:
- the values at (and , , and so on), and the logarithms , , and the powers , of
arf_exp2andarf_exp10at integers; - the functions of , whose values at rational are algebraic: by Niven's theorem the only rational values of and are , and , which at dyadic means the multiples of ; the only rational values of are and , at the multiples of ; and correspondingly , and are dyadic only at ;
- powers , which are algebraic for dyadic and :
arf_powcomputes exactly every power whose result is dyadic (integer powers, and the -th roots of perfect powers for ) before evaluating, so that the loop only sees irrational values.
Other arguments give irrational values (such as from arf_exp2), for which the loop terminates as well. No bound on the number of retries is known at multiple precision (exhaustive searches have bounded the precision needed for the hardest cases of the double-precision formats [MBD2018]). In practice a retry is rare, and the asymptotic cases below, which are the ones where an argument of special form puts the value very close to a representable number, are decided without retries.
Asymptotic cases#
Near some points the value is a dyadic number times with a tiny of known sign: and for tiny , , , and likewise, , , and, for huge arguments, , and so on. When lies below the last bit, a two-sided bound would never decide a directed rounding of such a value (its window is all zero or all one), whatever the precision. The functions recognise these arguments from their exponents and round directly from and the sign of with a one-sided bound, without evaluating the function, at any exponent; near the singular points of the inverse functions (such as near , which is ) the same is done with the exact square root when it is dyadic. A quotient is decided by one division with remainder.
Relaxed modes#
The modes ARF_RND_FAST and ARF_RND_ACCURATE drop correct rounding for speed: the first frame is final. ARF_RND_ACCURATE rounds the frame to nearest, which with 20 guard bits gives an error below ulp, and ARF_RND_FAST truncates the frame plus its upper error count, within one ulp. In these modes the inexact flag is set whenever a kernel was evaluated; the exact cases above are still detected before any evaluation and reported as exact, except the exact powers of arf_pow (and arf_exp10), which would cost a test on every call: the register path evaluates them within its error bound like any other power.
Compositions and quotients#
The less common functions are compositions of the kernels: the inverse trigonometric and hyperbolic functions of , and square roots, of , the functions of the sine, and so on. They evaluate the inner functions in a relaxed mode at a few more bits on temporaries, bound the error of the composition explicitly (the relative errors of the factors add up, with the condition numbers of the outer operations), and certify the result like a frame, retrying at a higher working precision until the rounding is decided. The reciprocal functions (, , and their hyperbolic counterparts) and the tangent from a sine and cosine divide a frame by another frame or by an exact mantissa at the precision of the current attempt, with the error of the quotient bounded from those of the operands, and certify the quotient.
Large exponents#
The arguments and results of arf may have exponents beyond a word. The exponential of a large argument and the powers return their binary exponent as an exact integer; the frame is rounded at exponent zero and shifted afterwards, so that the rounding does not depend on the size of the exponent. The cost of the argument reduction, however, grows with the exponent of the argument (see Argument reduction), so arf uses the same magnitude limits as arb: the exponential and the hyperbolic functions of and the trigonometric functions of give NaN rather than a result whose cost would not be polynomial in prec. The functions of reduce exactly and have no limit.
Fixed precision: nfloat#
The elementary functions of nfloat evaluate a kernel once, at the function precision of the context plus 12 guard bits (16 from 4096 bits on), and round the frame to the context's precision: there is no retry, and the result is within about one ulp at the function precision. With the directed rounding flags NFLOAT_RND_FLOOR and NFLOAT_RND_CEIL the error count is added in the direction of rounding, so that the result is a valid lower or upper bound within a few ulps, and the asymptotic cases above give the bound in the right direction. The exact cases give exact results, as in arf.
Complex numbers: acf#
The complex functions of acf round each part of the result. In the strict modes each part is correctly rounded, whatever its size against the other part; in the relaxed modes each part is within 1 resp. 0.51 ulp of the larger part, which spares the cost of resolving a part that is exponentially smaller than the other. The parts are compositions of the real functions and their certification follows the same scheme; see Complex elementary functions.
Use in FLINT#
- The elementary functions of Elementary functions, Elementary functions and Rounded arithmetic and elementary functions.
arf_const_picertifies the floor of ofmp_realat increasing precision in the same way.
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 arf_atan2(arf_ptr res, arf_srcptr y, arf_srcptr x, slong prec, arf_rnd_t rnd)int arf_pow(arf_ptr res, arf_srcptr x, arf_srcptr y, slong prec, arf_rnd_t rnd)int arf_const_pi(arf_ptr res, slong prec, arf_rnd_t rnd)Referenced from#
- Floating-point arithmetic in FLINT (overview)
- Complex elementary functions (algorithm)
- Elementary functions (algorithm)
- arf.h (module)
References#
- [IEEE754] IEEE Standard for Floating-Point Arithmetic. IEEE Std 754-2008, 2008. https://doi.org/10.1109/IEEESTD.2008.4610935
- [MBD2018] J.-M. Muller, N. Brunie, F. de Dinechin, C.-P. Jeannerod, M. Joldes, V. Lefèvre, G. Melquiond, N. Revol and S. Torres, Handbook of Floating-Point Arithmetic, second edition, Birkhäuser (2018), https://doi.org/10.1007/978-3-319-76526-6
- [Ziv1991] A. Ziv. Fast evaluation of elementary mathematical functions with correctly rounded last bit. ACM Transactions on Mathematical Software 17:3 (1991), 410–423. https://doi.org/10.1145/114697.116813
The FLINT team, “Correctly rounded elementary functions,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/floating-point/correct-rounding.html (generated 2026-11-17).
@misc{flint-doc-algorithms-floating-point-correct-rounding,
author = {{The FLINT team}},
title = {{Correctly rounded elementary functions}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/floating-point/correct-rounding.html},
note = {Generated 2026-11-17}
}