Editing Rounding (section)

===Table-maker's dilemma===
[[William M. Kahan]] coined the term "The Table-Maker's Dilemma" for the unknown cost of rounding [[transcendental function]]s:
{{Blockquote|Nobody knows how much it would cost to compute {{math|''y''{{sup|''w''}}}} correctly rounded for {{em|every}} two floating-point arguments at which it does not over/underflow. Instead, reputable math libraries compute elementary [[transcendental function]]s mostly within slightly more than half an [[unit in the last place|ulp]] and almost always well within one ulp. Why can't {{math|''y''{{sup|''w''}}}} be rounded within half an ulp like SQRT? Because nobody knows how much computation it would cost... No general way exists to predict how many extra digits will have to be carried to compute a transcendental expression and round it {{em|correctly}} to some preassigned number of digits. Even the fact (if true) that a finite number of extra digits will ultimately suffice may be a deep theorem.<ref>{{cite web |last=Kahan |first=William Morton |author-link=William Morton Kahan |title=A Logarithm Too Clever by Half |url=https://people.eecs.berkeley.edu/~wkahan/LOG10HAF.TXT |access-date=2008-11-14}}</ref>}}

The [[IEEE 754]] floating-point standard guarantees that add, subtract, multiply, divide, [[fused multiply–add]], square root, and floating-point remainder will give the correctly rounded result of the infinite-precision operation. No such guarantee was given in the 1985 standard for more complex functions and they are typically only accurate to within the last bit at best. However, the 2008 standard guarantees that conforming implementations will give correctly rounded results which respect the active rounding mode; implementation of the functions, however, is optional.

Using the [[Gelfond–Schneider theorem]] and [[Lindemann–Weierstrass theorem]], many of the standard elementary functions can be proved to return [[transcendental number|transcendental]] results, except on some well-known arguments; therefore, from a theoretical point of view, it is always possible to correctly round such functions. However, for an implementation of such a function, determining a limit for a given precision on how accurate results need to be computed, before a correctly rounded result can be guaranteed, may demand a lot of computation time or may be out of reach.<ref name="Muller_2010">{{cite book |author-last1=Muller |author-first1=Jean-Michel |author-last2=Brisebarre |author-first2=Nicolas |author-last3=de Dinechin |author-first3=Florent |author-last4=Jeannerod |author-first4=Claude-Pierre |author-last5=Lefèvre |author-first5=Vincent |author-last6=Melquiond |author-first6=Guillaume |author-last7=Revol |author-first7=Nathalie |author7-link=Nathalie Revol |author-last8=Stehlé |author-first8=Damien |author-last9=Torres |author-first9=Serge |title=Handbook of Floating-Point Arithmetic |date=2010 |publisher=[[Birkhäuser]] |edition=1 |isbn=978-0-8176-4704-9<!-- print --> |doi=10.1007/978-0-8176-4705-6 |lccn=2009939668<!-- |id={{isbn |978-0-8176-4705-6}} (online), {{isbn|0-8176-4704-X}} (print) -->|chapter=Chapter 12: Solving the Table Maker's Dilemma|chapter-url=https://cds.cern.ch/record/1315760}}</ref> In practice, when this limit is not known (or only a very large bound is known), some decision has to be made in the implementation (see below); but according to a probabilistic model, correct rounding can be satisfied with a very high probability when using an intermediate accuracy of up to twice the number of digits of the target format plus some small constant (after taking special cases into account).

Some programming packages offer correct rounding. The [[GNU MPFR]] package gives correctly rounded arbitrary precision results. Some other libraries implement elementary functions with correct rounding in [[Double-precision floating-point format#IEEE 754 double-precision binary floating-point format: binary64|IEEE 754 double precision]] (binary64):
* [[IBM]]'s ''ml4j'', which stands for ''Mathematical Library for Java'', written by [[Abraham Ziv]] and Moshe Olshansky in 1999, correctly rounded to nearest only.<ref>{{cite web |url=https://netlib.org/na-digest-html/99/v99n16.html |title=NA Digest Sunday, April 18, 1999 Volume 99 : Issue 16 |date=18 April 1999| accessdate=29 August 2022}}</ref><ref>{{cite web |url=http://www.alphaworks.ibm.com/tech/mathlibrary4java/ |title=Math Library for Java |url-status=dead |archive-url=https://web.archive.org/web/19990508150807/http://www.alphaworks.ibm.com/tech/mathlibrary4java/ |archive-date=8 May 1999}}</ref> This library was claimed to be portable, but only binaries for [[PowerPC]]/[[IBM AIX|AIX]], [[SPARC]]/[[Oracle Solaris|Solaris]] and [[x86]]/[[Windows NT]] were provided. According to its documentation, this library uses a first step with an accuracy a bit larger than double precision, a second step based on [[double-double arithmetic]], and a third step with a 768-bit precision based on arrays of IEEE 754 double-precision floating-point numbers.
* IBM's ''Accurate portable mathematical library'' (abbreviated as APMathLib or just MathLib),<ref>{{cite web |url=http://oss.software.ibm.com/mathlib/ |title=Accurate Portable Mathematical Library |archive-url=https://web.archive.org/web/20050207110205/http://oss.software.ibm.com/mathlib/ |archive-date=7 February 2005}}</ref><ref>{{GitHub|dreal-deps/mathlib}}.</ref> also called libultim,<ref>{{cite web |url=http://www.math.utah.edu/cgi-bin/man2html.cgi?/usr/local/man/man3/libultim.3 |title=libultim – ultimate correctly-rounded elementary-function library |url-status=dead |archive-url=https://web.archive.org/web/20210301025744/http://www.math.utah.edu/cgi-bin/man2html.cgi?/usr/local/man/man3/libultim.3 |archive-date=1 March 2021}}</ref> in rounding to nearest only. This library uses up to 768 bits of working precision. It was included in the [[GNU C Library]] in 2001,<ref>{{cite web|url=https://sourceware.org/git/?p=glibc.git;a=commit;h=e4d8276142b9c07b23043ef44b0fe8fa7bcc3121 |title=Git - glibc.git/commit |publisher=Sourceware.org |date= |accessdate=2022-07-18}}</ref> but the "slow paths" (providing correct rounding) were removed from 2018 to 2021.<!-- Search for "slow path" in the git log. -->
* CRlibm, written in the old Arénaire team (LIP, [[ENS Lyon]]), first distributed in 2003.<ref>{{cite journal |last1=de Dinechin |first1=Florent |last2=Lauter |first2=Christoph |last3=Muller |first3=Jean-Michel |title=Fast and correctly rounded logarithms in double-precision |journal=RAIRO-Theor. Inf. Appl. |date=January–March 2007 |volume=41 |number=1 |pages=85–102 |doi=10.1051/ita:2007003 |id={{HAL|ensl-00000007v2}} |citeseerx=10.1.1.106.6652 }}</ref> It supports the 4 rounding modes and is proved, using the knowledge of the hardest-to-round cases.<ref>{{cite web |url=http://lipforge.ens-lyon.fr/www/crlibm/ |archive-url=https://web.archive.org/web/20161027224938/http://lipforge.ens-lyon.fr/www/crlibm |archive-date=2016-10-27 |title=CRlibm – Correctly Rounded mathematical library}}</ref><ref>{{GitHub|taschini/crlibm}}</ref> More efficient than IBM MathLib.<ref name=coremath-ieee29/> Succeeded by Metalibm (2014), which automates the formal proofs.<ref>{{cite conference|last1=Kupriianova |first1=Olga |last2=Lauter |first2=Christoph |title=Metalibm: A Mathematical Functions Code Generator |conference=Mathematical Software – ICMS 2014|url=https://hal.science/hal-01513490/ |date=2014 |volume=8592 |pages=713–717 |doi=10.1007/978-3-662-44199-2_106}}</ref>
* [[Sun Microsystems]]'s libmcr of 2004, in the 4 rounding modes.<ref>{{cite web |url=http://www.math.utah.edu/cgi-bin/man2html.cgi?/usr/local/man/man3/libmcr.3 |title=libmcr – correctly-rounded elementary-function library |url-status=dead |archive-url=https://web.archive.org/web/20210225085748/http://www.math.utah.edu/cgi-bin/man2html.cgi?/usr/local/man/man3/libmcr.3 |archive-date=25 February 2021}}</ref><ref>{{GitHub|simonbyrne/libmcr}}.</ref> For the difficult cases, this library also uses multiple precision, and the number of words is increased by 2 each time the Table-maker's dilemma occurs (with undefined behavior in the very unlikely event that some limit of the machine is reached).<!-- in the sources: "nw += 2;" in a loop -->
* The CORE-MATH project (2022) provides some correctly rounded functions in the 4 rounding modes for [[x86-64]] processors. Proved using the knowledge of the hardest-to-round cases.<ref>{{cite web |url=https://core-math.gitlabpages.inria.fr/ |title=The CORE-MATH project |accessdate=30 August 2022}}</ref><ref name=coremath-ieee29>{{cite conference |url=https://inria.hal.science/hal-03721525v3 |last1=Sibidanov |first1=Alexei |last2=Zimmermann |first2=Paul |last3=Glondu |first3=Stéphane |title=The CORE-MATH Project |conference=29th IEEE Symposium on Computer Arithmetic (ARITH 2022) |conference-url=https://arith2022.arithsymposium.org/ |date=2022 |accessdate=30 August 2022}}</ref>
* [[LLVM]] libc provides some correctly rounded functions in the 4 rounding modes.<ref>{{cite web |title=Math Functions — The LLVM C Library |url=https://libc.llvm.org/math |website=libc.llvm.org}}</ref>

There exist [[computable number]]s for which a rounded value can never be determined no matter how many digits are calculated. Specific instances cannot be given but this follows from the undecidability of the [[halting problem]]. For instance, if [[Goldbach's conjecture]] is true but [[unprovable]], then the result of rounding the following value, {{mvar|n}}, [[#Rounding up|up to the next integer]] cannot be determined: either {{mvar|n}}=1+10<sup>−{{mvar|k}}</sup> where {{mvar|k}} is the first even number greater than 4 which is not the sum of two primes, or {{mvar|n}}=1 if there is no such number. The rounded result is 2 if such a number {{mvar|k}} exists and 1 otherwise. The value before rounding can however be approximated to any given precision even if the conjecture is unprovable.