{{Short description|Strategies to make sure approximate calculations stay close to accurate}} {{Use dmy dates|date=May 2019|cs1-dates=y}}
'''Floating-point error mitigation''' is the minimization of errors caused by the fact that real numbers cannot, in general, be accurately represented in a fixed space. By definition, floating-point error cannot be eliminated, and, at best, can only be managed.
Huberto M. Sierra noted in his 1956 patent "Floating Decimal Point Arithmetic Control Means for Calculator":<ref>{{cite web |url =https://www.freepatentsonline.com/3037701.html|title =Floating decimal point arithmetic control means for calculator: United States Patent 3037701|website =FreePatentsOnline.com|access-date =21 January 2022|date =1962-06-05}}</ref> {{blockquote|Thus under some conditions, the major portion of the significant data digits may lie beyond the capacity of the registers. Therefore, the result obtained may have little meaning if not totally erroneous.}}
The Z1, developed by Konrad Zuse in 1936, was the first computer with floating-point arithmetic and was thus susceptible to floating-point error. Early computers, however, with operation times measured in milliseconds, could not solve large, complex problems<ref>{{cite web|url= http://wikieducator.org/History_of_Computer_Development_%26_Generation_of_Computer|title= History of Computer Development & Generation of Computer|date= September 2014|website= WikiEducator|accessdate= 2018-02-17 }}</ref> and thus were seldom plagued with floating-point error. Today, however, with supercomputer system performance measured in petaflops, floating-point error is a major concern for computational problem solvers.
The following sections describe the strengths and weaknesses of various means of mitigating floating-point error.
== Numerical error analysis == Though not the primary focus of numerical analysis,<ref>{{cite web|url= http://webs.um.es/eliseo/um/uploads/Main/TrefethendefNA.pdf|title= The Definition of Numerical Analysis|last1= Trefethen|first1= Lloyd N. |date= 1992|publisher= SIAM|accessdate= 2018-02-16}}</ref><ref name=Higham1>{{cite book|title=Accuracy and Stability of Numerical Algorithms |edition=2 |first=Nicholas John |author-link=Nicholas Higham |last=Higham |publisher=Society for Industrial and Applied Mathematics (SIAM) |year=2002 |isbn=978-0-89871-521-7|url=https://books.google.com/books?id=epilvM5MMxwC&q=accuracy+and+stability+of+numerical+algorithms+higham }}</ref>{{rp|5}} numerical error analysis exists for the analysis and minimization of floating-point rounding error.
== Monte Carlo arithmetic == Error analysis by Monte Carlo arithmetic is accomplished by repeatedly injecting small errors into an algorithm's data values and determining the relative effect on the results.
== Extension of precision == Extension of precision is using of larger representations of real values than the one initially considered. The IEEE 754 standard defines precision as the number of digits available to represent real numbers. A programming language can include single precision (32 bits), double precision (64 bits), and quadruple precision (128 bits). While extension of precision makes the effects of error less likely or less important, the true accuracy of the results is still unknown.
== Variable-length arithmetic == Variable length arithmetic represents numbers as a string of digits of a variable's length limited only by the memory available. Variable-length arithmetic operations are considerably slower than fixed-length format floating-point instructions. When high performance is not a requirement, but high precision is, variable length arithmetic can prove useful, though the actual accuracy of the result may not be known.
== Use of the error term of a floating-point operation == The floating-point algorithm known as ''TwoSum''<ref>{{cite journal |last1=Richard Shewchuk |first1=Jonathan |title=Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates |journal=Discrete & Computational Geometry |date=October 1997 |volume=18 |issue=3 |pages=305–363 |doi=10.1007/PL00009321 |s2cid=189937041 |url=https://people.eecs.berkeley.edu/~jrs/papers/robustr.pdf |access-date=14 November 2022}}</ref> or ''2Sum'', due to Knuth and Møller, and its simpler, but restricted version ''FastTwoSum'' or ''Fast2Sum'' (3 operations instead of 6), allow one to get the (exact) error term of a floating-point addition rounded to nearest. One can also obtain the (exact) error term of a floating-point multiplication rounded to nearest in 2 operations with a fused multiply–add (FMA), or 17 operations if the FMA is not available (with an algorithm due to Dekker). These error terms can be used in algorithms in order to improve the accuracy of the final result, e.g. with floating-point expansions or compensated algorithms.
Operations giving the result of a floating-point addition or multiplication rounded to nearest with its error term (but slightly differing from algorithms mentioned above) have been standardized and recommended in the IEEE 754-2019 standard.
== Choice of a different radix == Changing the radix, in particular from binary to decimal, can help to reduce the error and better control the rounding in some applications, such as financial applications.
== Interval arithmetic == Interval arithmetic is a mathematical technique used to put bounds on rounding errors and measurement errors in mathematical computation. Values are intervals, which can be represented in various ways, such as:<ref name="IEEE_2015_1788">{{cite journal |title=IEEE Standard for Interval Arithmetic |journal=IEEE STD 1788-2015 |date=30 June 2015 |pages=1–97 |doi=10.1109/IEEESTD.2015.7140721|isbn=978-0-7381-9720-3 }}</ref> * inf-sup: a lower bound and an upper bound on the true value; * mid-rad: an approximation and an error bound (called ''midpoint'' and ''radius'' of the interval); * triplex: an approximation, a lower bound and an upper bound on the error.
<blockquote>"Instead of using a single floating-point number as approximation for the value of a real variable in the mathematical model under investigation, interval arithmetic acknowledges limited precision by associating with the variable a set of reals as possible values. For ease of storage and computation, these sets are restricted to intervals."<ref name=Hickey>{{cite journal|last1= Hickey |first1= T. |last2= Ju|first2= Q. |last3= van Emden|first3= M.H. |date= September 2001 |title= Interval Arithmetic: from Principles to Implementation|url= http://fab.cba.mit.edu/classes/S62.12/docs/Hickey_interval.pdf|journal= Journal of the ACM|volume= 48|issue= 5|pages= 1038–1068 |doi= 10.1145/502102.502106|access-date= 2018-02-16|citeseerx= 10.1.1.43.8001 |s2cid= 15105694 }}</ref></blockquote>The evaluation of interval arithmetic expression may provide a large range of values,<ref name=Hickey/> and may seriously overestimate the true error boundaries.<ref name=Kahan1>{{cite web|url= https://people.eecs.berkeley.edu/~wkahan/UnumSORN.pdf|title= A Critique of John L. Gustafson's THE END of ERROR — Unum Computation and his A Radical Approach to Computation with Real Numbers|last1= Kahan|first1= William|authorlink= William Kahan|date= July 2016|accessdate= 2018-02-17}}</ref>{{rp|8}}
== Gustafson's unums == Unums ("Universal Numbers") are an extension of variable length arithmetic proposed by John Gustafson.<ref name="Gustafson">{{cite book |author-last=Gustafson |author-first=John Leroy |author-link=John Leroy Gustafson |url=https://www.crcpress.com/The-End-of-Error-Unum-Computing/Gustafson/p/book/9781482239867 |title=The End of Error: Unum Computing |date=2016-02-04 |publisher=CRC Press |isbn=978-1-4822-3986-7 |edition=2nd corrected printing, 1st |series=Chapman & Hall / CRC Computational Science |volume=24 |access-date=2016-05-30 |orig-year=2015-02-05}} [https://books.google.com/books?id=fZsXBgAAQBAJ] [http://www.crcpress.com/product/isbn/9781482239867]</ref> Unums have variable length fields for the exponent and significand lengths and error information is carried in a single bit, the ubit, representing possible error in the least significant bit of the significand (ULP).<ref name="Gustafson"/>{{rp|4}}
The efficacy of unums is questioned by William Kahan.<ref name="Kahan1"/>
== Bounded floating point == '''Bounded floating point''' is a method proposed and patented by Alan Jorgensen.<ref name=HPCWire>{{cite news |title=Inventor Claims to Have Solved Floating Point Error Problem |url=https://www.hpcwire.com/2018/01/17/inventor-claims-solved-floating-point-error-problem/|first1=Tiffany|last1=Trader |access-date=1 March 2022 |work=HPCwire |date=17 January 2018}}</ref> The data structure includes the standard IEEE 754 data structure and interpretation, as well as information about the error between the true real value represented and the value stored by the floating point representation.<ref name=2021Patent>{{cite patent|country=US|number=11023230B2 | status=patent| title = Apparatus for Calculating and Retaining a Bound on Error during Floating Point Operations and Methods Thereof| fdate = 2020-01-20 | gdate = 2021-06-01 | inventor-last = Jorgensen | inventor-first = Alan A.}}</ref>
Bounded floating point has been criticized as being derivative of Gustafson's work on unums and interval arithmetic.<ref name=HPCWire/><ref>{{cite news |title=Has the Decades-Old Floating Point Error Problem been Solved? |url=https://insidehpc.com/2018/01/decades-old-floating-point-error-problem-solved/ |access-date=1 March 2022 |work=insideHPC |date=17 January 2018}}</ref>
== References == {{reflist}}
Category:Floating point Category:Computer arithmetic Category:Error