What causes floating point rounding errors?

Question

I am aware that floating point arithmetic has precision problems. I usually overcome them by switching to a fixed decimal representation of the number, or simply by neglecting the error.

However, I do not know what are the causes of this inaccuracy. Why are there so many rounding issues with float numbers?

Answer 1

This is because some fractions need a very large (or even infinite) amount of places to be expressed without rounding. This holds true for decimal notation as much as for binary or any other. If you would limit the amount of decimal places to use for your calculations (and avoid making calculations in fraction notation), you would have to round even a simple expression as 1/3 + 1/3. Instead of writing 2/3 as a result you would have to write 0.33333 + 0.33333 = 0.66666 which is not identical to 2/3.

In case of a computer the number of digits is limited by the technical nature of its memory and CPU registers. The binary notation used internally adds some more difficulties. Computers normally can't express numbers in fraction notation, though some programming languages add this ability, which allows those problems to be avoided to a certain degree.

What Every Computer Scientist Should Know About Floating-Point Arithmetic

Answer 2

Primarily, rounding errors come from the fact that the infinity of all real numbers cannot possibly be represented by the finite memory of a computer, let alone a tiny slice of memory such as a single floating point variable, so many numbers stored are just approximations of the number they are meant to represent.

Since there are only a limited number of values which are not an approximation, and any operation between an approximation and an another number results in an approximation, rounding errors are almost inevitable.

The important thing is to realise when they are likely to cause a problem and take steps to mitigate the risks.

---

In addition to David Goldberg's essential What Every Computer Scientist Should Know About Floating-Point Arithmetic (re-published by Sun/Oracle as an appendix to their Numerical Computation Guide), which was mentioned by thorsten, the ACCU journal Overload ran an excellent series of articles by Richard Harris about the Floating Point Blues.

The series started with

• You're Going To Have To Think! in Overload #99 (pdf, p5-10):

Numerical computing has many pitfalls. Richard Harris starts looking for a silver bullet.

The dragon of numerical error is not often roused from his slumber, but if incautiously approached he will occasionally inflict catastrophic damage upon the unwary programmer's calculations.

So much so that some programmers, having chanced upon him in the forests of IEEE 754 floating point arithmetic, advise their fellows against travelling in that fair land.

In this series of articles we shall explore the world of numerical computing, contrasting floating point arithmetic with some of the techniques that have been proposed as safer replacements for it. We shall learn that the dragon's territory is far reaching indeed and that in general we must tread carefully if we fear his devastating attention.

Richard starts by explaining the taxonomy of real numbers, rational, irrational, algebraic and transcendental. He then goes on to explain IEEE754 representation, before going on to cancellation error and order of execution problems.

If you read no deeper than this, you will have an excellent grounding in the problems associated with floating point numbers.

If you want to know more however, he continues with

• Why Fixed Point Won't Cure Your Floating Point Blues in Overload #100 (pdf, p15-22)
• Why Rationals Won’t Cure Your Floating Point Blues in Overload #101 (pdf, p9-13)
• Why Computer Algebra Won’t Cure Your Floating Point Blues in Overload #102 (pdf, p9-14).
• Why Interval Arithmetic Won’t Cure Your Floating Point Blues in Overload 103 (pdf, p19-24)

He then switches to trying to help you cure your Calculus Blues

• Why [Insert Algorithm Here] Won’t Cure Your Calculus Blues in Overload 104 (pdf, p22-24).
• Why Finite Differences Won’t Cure Your Calculus Blues in Overload 105 (pdf, p5-12).
• Why Polynomial Approximation Won't Cure Your Calculus Blues in Overload 106 (pdf, p16-25).
• Why Computer Algebra Won’t Cure Your Calculus Blues in Overload 107 (pdf, p15-20).

and last but not least, there is

• Why Automatic Differentiation Won’t Cure Your Calculus Blues in Overload 108 (pdf, p4-11).

The whole series of articles are well worth looking into, and at 66 pages in total, they are still smaller than the 77 pages of the Goldberg paper.

While this series covers much of the same ground, I found it rather more accessible than Goldberg's paper. I also found it easier to understand the more complex parts of the paper after reading the earlier of Richards articles and after those early articles, Richard branches off into many interesting areas not touched on by the Goldberg paper.

---

As thus spake a.k. mentioned in comments:

As the author of those articles I'd like to mention that I have created interactive versions of them on my blog www.thusspakeak.com starting with thusspakeak.com/ak/2013/06.

Answer 3

Well, thorsten has the definitive link. I would add:

Any form of representation will have some rounding error for some number. Try to express 1/3 in IEEE floating point, or in decimal. Neither can do it accurately. This is going beyond answering your question, but I have used this rule of thumb successfully:

• Store user-entered values in decimal (because they almost certainly entered it in a decimal representation - very few users will use binary or hex). That way you always have the exact user-entered representation.
• If you have to store user-entered fractions, store the numerator and denominator (also in decimal)
• If you have a system with multiple units of measure for the same quantity (like Celsius/Fahrenheit), and the user can enter both, store the value they entered and the units they entered them in. Don't try to convert and save as a single representation, unless you can do it without loss of precision/accuracy. Use the stored value and units in all calculations.
• Store machine generated values in IEEE floating point (this can be numbers generated by an electronic measurement device, like an analog sensor with an A/D converter, or the unrounded result of a calculation). Note that this doesn't apply if you're reading a sensor over a serial connection and it's already giving you the value in a decimal format (e.g. 18.2 C).
• Store user-viewable totals, etc., in decimal (like a bank account balance). Round appropriately, but use that value as the definitive value for all future calculations.

Answer 4

What seems to have not been mentioned so far are the concepts of an unstable algorithm and an ill-conditioned problem. I'll address the former first, as that seems to be a more frequent pitfall for novice numericists.

Consider the computation of the powers of the (reciprocal) golden ratio φ=0.61803… ; one possible way to go about it is to use the recursion formula φ^n=φ^(n-2)-φ^(n-1), starting with φ^0=1 and φ^1=φ. If you run this recursion in your favorite computing environment and compare the results with accurately evaluated powers, you'll find a slow erosion of significant figures. Here's what happens for instance in Mathematica:

ph = N[1/GoldenRatio];  
Nest[Append[#1, #1[[-2]] - #1[[-1]]] & , {1, ph}, 50] - ph^Range[0, 51]  
{0., 0., 1.1102230246251565*^-16, -5.551115123125783*^-17, 2.220446049250313*^-16, 
-2.3592239273284576*^-16, 4.85722573273506*^-16, -7.147060721024445*^-16, 
1.2073675392798577*^-15, -1.916869440954372*^-15, 3.1259717037102064*^-15, 
-5.0411064211886014*^-15, 8.16837916750579*^-15, -1.3209051907825398*^-14, 
2.1377864756200182*^-14, -3.458669982359108*^-14, 5.596472721011714*^-14, 
-9.055131861349097*^-14, 1.465160458236081*^-13, -2.370673237795176*^-13, 
3.835834102607072*^-13, -6.206507137114341*^-13, 1.004234127360273*^-12, 
-1.6248848342954435*^-12, 2.6291189633497825*^-12, -4.254003796798193*^-12, 
6.883122762265558*^-12, -1.1137126558640235*^-11, 1.8020249321541067*^-11, 
-2.9157375879969544*^-11, 4.717762520172237*^-11, -7.633500108148015*^-11, 
1.23512626283229*^-10, -1.9984762736468268*^-10, 3.233602536479646*^-10, 
-5.232078810126407*^-10, 8.465681346606119*^-10, -1.3697760156732426*^-9, 
2.216344150333856*^-9, -3.5861201660070964*^-9, 5.802464316340953*^-9, 
-9.388584482348049*^-9, 1.5191048798689004*^-8, -2.457963328103705*^-8, 
3.9770682079726053*^-8, -6.43503153607631*^-8, 1.0412099744048916*^-7, 
-1.6847131280125227*^-7, 2.725923102417414*^-7, -4.4106362304299367*^-7, 
7.136559332847351*^-7, -1.1547195563277288*^-6}

The purported result for φ^41 has the wrong sign, and even earlier, the computed and actual values for φ^39 share no digits in common (3.484899258054952*^-9for the computed version against the true value7.071019424062048*^-9). The algorithm is thus unstable, and one should not use this recursion formula in inexact arithmetic. This is due to the inherent nature of the recursion formula: there is a "decaying" and "growing" solution to this recursion, and trying to compute the "decaying" solution by forward solution when there is an alternative "growing" solution is begging for numerical grief. One should thus ensure that his/her numerical algorithms are stable.

Now, on to the concept of an ill-conditioned problem: even though there may be a stable way to do something numerically, it may very well be that the problem you have just cannot be solved by your algorithm. This is the fault of the problem itself, and not the solution method. The canonical example in numerics is the solution of linear equations involving the so-called "Hilbert matrix":

The matrix is the canonical example of an ill-conditioned matrix: trying to solve a system with a large Hilbert matrix might return an inaccurate solution.

Here's a Mathematica demonstration: compare the results of exact arithmetic

Table[LinearSolve[HilbertMatrix[n], HilbertMatrix[n].ConstantArray[1, n]], {n, 2, 12}]
{{1, 1}, {1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 
  1}, {1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1,
   1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 
  1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}

and inexact arithmetic

Table[LinearSolve[N[HilbertMatrix[n]], N[HilbertMatrix[n].ConstantArray[1, n]]], {n, 2, 12}]
{{1., 1.}, {1., 1., 1.}, {1., 1., 1., 1.}, {1., 1., 1., 1., 1.},  
  {1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1.}, 
  {1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1., 1.},  
  {1., 1., 1., 0.99997, 1.00014, 0.999618, 1.00062, 0.9994, 1.00031, 
  0.999931}, {1., 1., 0.999995, 1.00006, 0.999658, 1.00122, 0.997327, 
  1.00367, 0.996932, 1.00143, 0.999717}, {1., 1., 0.999986, 1.00022, 
  0.998241, 1.00831, 0.975462, 1.0466, 0.94311, 1.04312, 0.981529, 
  1.00342}}

(If you did try it out in Mathematica, you'll note a few error messages warning of the ill-conditioning appearing.)

In both cases, simply increasing the precision is no cure; it will only delay the inevitable erosion of figures.

This is what you might be faced with. The solutions might be difficult: for the first, either you go back to the drawing board, or wade through journals/books/whatever to find if somebody else has come up with a better solution than you have; for the second, you either give up, or reformulate your problem to something more tractable.

---

I'll leave you with a quote from Dianne O'Leary:

Life may toss us some ill-conditioned problems, but there is no good reason to settle for an unstable algorithm.

Answer 5

because base 10 decimal numbers cannot be expressed in base 2

or in other words 1/10 cannot be transformed into a fraction with a power of 2 in the denominator (which is what floating point numbers essentially are)

Answer 6

In mathematics, there are infinitely many rational numbers. A 32 bit variable can only have 2³² different values, and a 64 bit variable only 2⁶⁴ values. Therefore, there are infinitely many rational numbers that have no precise representation.

We could come up with schemes that would allow us to represent 1/3 perfectly, or 1/100. It turns out that for many practical purposes this isn't very useful. There's one big exception: in finance, decimal fractions often do pop up. That's mostly because finance is essentially a human activity, not a physical one.

Therefore, we usually choose to use binary floating point, and round any value that can't be represented in binary. But in finance, we sometimes choose decimal floating point, and round values to the closest decimal value.

Answer 7

Loss of precision is not something particular to floating point types. You can't represent 1/3 = 0.3333333333... in a fixed decimal representation either, without losing some precision.

Nevertheless binary floating point types are often perceived as less accurate than decimals. So let's distinguish between two separate reasons for inaccuracy:

1. Rounding due to finite size memory

Numbers are stored in memory cells of fixed size. Memory of finite size can only represent a finite set of different numbers. But since there are infinitely many real numbers in any given range, it follows that most numbers cannot be represented exactly, but will have to be rounded to the nearest number which can be represented. This introduce some inaccuracy.

To realize decimal types are also subject to this, try this with C#'s decimal type:

(decimal) 1 * 3 / 3  -->  1
(decimal) 1 / 3 * 3  -->  0.9999999999999999999999999999

It is easy to see what is going on if you imagine a decimal format with for example just four digits:

1.000 * 3.000 = 3.000 and then 3.000 / 3.000 = 1.000

But

1.000 / 3.000 = 0.333 (remaining decimals rounded away), and then 0.333 * 3 = 0.999

The distinction between fixed-point and floating-point is not relevant here; the problem is intrinsic to any number format supporting fractions and reals.

2. Base-2 encoding rounds differently

But the problem leading to most confusion is that typical floating point number formats (like the IEEE 754 standard) rounds differently than decimal formats. The set of numbers which can be represented precisely is different.

Floating point numbers are represented as a significand part and an exponent part. For decimal numbers, the exponent base is 10, but for the typical floating-point formats the exponent base is 2. So for example 3/4 in decimal is represented as 75 * 10^-2 while in floats it is 3 * 2^-2. (*)

The choice of base makes a difference in which numbers can be expressed precisely and which numbers will have to be rounded. As shown above, 3/4 can be expressed precisely in either format, but for example 3/10 can only be expressed precisely in base-10 (3 * 10^-1). It cannot be represented precisely in base-2, but will have to be rounded to a number close to but not exactly 3/10.

This is the root cause of the infamous problem where:

0.1 + 0.2 -> 0.30000000000000004

But it is important to emphasise that base-2 representations are not more imprecise than base-10. Either format has a precision determined by the number of bits available to significand and exponents. But since humans are used to decimal numbers, the behavior of base-2 floating point numbers are unintuitive to us.

Therefore, if a calculation have to be presented to human users in decimal formats, it is also preferable to use decimal (base-10) number types to perform the calculation. But for calculations where the numbers are not presented for a human user, floating point types are preferable because of higher efficiency.

---

(*) Floating point types have some further intricancies with normalization and exponent-bias, but these are not relevant for the example

Answer 8

Your computer very likely uses standard IEEE-754 floating point numbers. These numbers have the form +/- m * 2^k where 1<=m<2 is a multiple of 2^-52 and k is an integer roughly between +/- 1000 (that’s not exactly true but roughly right).

When you calculate 1.0 / 3.0, that’s not a number in this form, so you CANNOT get the exact result. There is a rounding error. For + - * the problem is that the 52 bits of precision are often not enough, so you get a rounding error.

You will always have a rounding error if the correct result is not within the small set of floating point numbers. There are only 2^64 of them.

So what causes rounding errors? The fact that the exact result is very often not in the set of floating point numbers.

By the way: Using decimal numbers isn’t helping at all. 1/3 in decimal is 0.33… wrong. It’s 0.3333333333333.. wrong. You cannot write 1/3 as a decimal number. And (1/3)*3 will not be 1.

Answer 9

the only really obvious "rounding issue" with floating-point numbers i think about is with moving average filters:

$$\begin{align} y[n] & = \frac{1}{N}\sum\limits_{i=0}^{N-1} x[n-i] \ & = y[n-1] + \frac{1}{N}(x[n] - x[n-N]) \ \end{align}$$

to make this work without the buildup of noise, you want to make sure that the $x[n]$ you add in the current samples is precisely the same as the $x[n-N]$ you will subtract $N$ samples into the future. if it is not, then what is different is a little turd that gets stuck in your delay line and will never come out. that is because this moving average filter is actually built with an IIR that has a marginally stable pole at $z=1$ and a zero that cancels it inside. but, it's an integrator and any crap that gets integrated and not entirely removed will exist in the integrator sum forevermore. this is where fixed-point does not have the same problem that floating-point numbers do.