45

Everybody knows, or at least, every programmer should know, that using the float type could lead to precision errors. However, in some cases, an exact solution would be great and there are cases where comparing using an epsilon value is not enough. Anyway, that's not really the point.

I knew about the Decimal type in Python but never tried to use it. It states that "Decimal numbers can be represented exactly" and I thought that it meant a clever implementation that allows to represent any real number. My first try was:

>>> from decimal import Decimal
>>> d = Decimal(1) / Decimal(3)
>>> d3 = d * Decimal(3)
>>> d3 < Decimal(1)
True

Quite disappointed, I went back to the documentation and kept reading:

The context for arithmetic is an environment specifying precision [...]

OK, so there is actually a precision. And the classic issues can be reproduced:

>>> dd = d * 10**20
>>> dd
Decimal('33333333333333333333.33333333')
>>> for i in range(10000):
...    dd += 1 / Decimal(10**10)
>>> dd
Decimal('33333333333333333333.33333333')

So, my question is: is there a way to have a Decimal type with an infinite precision? If not, what's the more elegant way of comparing 2 decimal numbers (e.g. d3 < 1 should return False if the delta is less than the precision).

Currently, when I only do divisions and multiplications, I use the Fraction type:

>>> from fractions import Fraction
>>> f = Fraction(1) / Fraction(3)
>>> f
Fraction(1, 3)
>>> f * 3 < 1
False
>>> f * 3 == 1
True

Is it the best approach? What could be the other options?

djvg
  • 11,722
  • 5
  • 72
  • 103
Maxime Chéramy
  • 17,761
  • 8
  • 54
  • 75
  • 11
    how do you want to represent `Pi` with your hypothetical Decimal type? – jfs Dec 03 '13 at 15:16
  • related: [How dangerous is it to compare floating point values?](http://stackoverflow.com/a/10335601/4279) – jfs Dec 03 '13 at 15:21
  • 1
    @J.F.Sebastian I would not be surprised if not possible. That's why I'm asking "what's the more elegant way of comparing 2 decimal numbers". – Maxime Chéramy Dec 03 '13 at 15:26
  • I'm also thinking of a type that'd allow many manipulations (basic operations, common functions, etc) but keep an exact representation. For example, the Fraction type seems to handle perfectly many cases. In fact, any time the result is not an irrational number. But maybe we could do better with another representation that would include a larger subset. Something with a dynamic precision like a kid would do at school for instance. Of course I could not represent `Pi`, but quite often, `Pi` is just a constant of the problem. – Maxime Chéramy Dec 03 '13 at 15:30
  • 1
    Before you reinvent the wheel with your exact representation, have a look at Sage or sympy – chthonicdaemon Dec 03 '13 at 15:48
  • I was reading the documentation of SymPy but I can't find a type (that could directly replace Decimal). But indeed, SymPy, that does symbolic computation, could probably do the trick. – Maxime Chéramy Dec 03 '13 at 15:55

5 Answers5

56

The Decimal class is best for financial type addition, subtraction multiplication, division type problems:

>>> (1.1+2.2-3.3)*10000000000000000000
4440.892098500626                            # relevant for government invoices...
>>> import decimal
>>> D=decimal.Decimal
>>> (D('1.1')+D('2.2')-D('3.3'))*10000000000000000000
Decimal('0.0')

The Fraction module works well with the rational number problem domain you describe:

>>> from fractions import Fraction
>>> f = Fraction(1) / Fraction(3)
>>> f
Fraction(1, 3)
>>> f * 3 < 1
False
>>> f * 3 == 1
True

For pure multi precision floating point for scientific work, consider mpmath.

If your problem can be held to the symbolic realm, consider sympy. Here is how you would handle the 1/3 issue:

>>> sympy.sympify('1/3')*3
1
>>> (sympy.sympify('1/3')*3) == 1
True

Sympy uses mpmath for arbitrary precision floating point, includes the ability to handle rational numbers and irrational numbers symbolically.

Consider the pure floating point representation of the irrational value of √2: 

>>> math.sqrt(2)
1.4142135623730951
>>> math.sqrt(2)*math.sqrt(2)
2.0000000000000004
>>> math.sqrt(2)*math.sqrt(2)==2
False

Compare to sympy:

>>> sympy.sqrt(2)
sqrt(2)                              # treated symbolically
>>> sympy.sqrt(2)*sympy.sqrt(2)==2
True

You can also reduce values:

>>> import sympy
>>> sympy.sqrt(8)
2*sqrt(2)                            # √8 == √(4 x 2) == 2*√2...

However, you can see issues with Sympy similar to straight floating point if not careful:

>>> 1.1+2.2-3.3
4.440892098500626e-16
>>> sympy.sympify('1.1+2.2-3.3')
4.44089209850063e-16                   # :-(

This is better done with Decimal:

>>> D('1.1')+D('2.2')-D('3.3')
Decimal('0.0')

Or using Fractions or Sympy and keeping values such as 1.1 as ratios:

>>> sympy.sympify('11/10+22/10-33/10')==0
True
>>> Fraction('1.1')+Fraction('2.2')-Fraction('3.3')==0
True

Or use Rational in sympy:

>>> frac=sympy.Rational
>>> frac('1.1')+frac('2.2')-frac('3.3')==0
True
>>> frac('1/3')*3
1

You can play with sympy live.

twasbrillig
  • 17,084
  • 9
  • 43
  • 67
dawg
  • 98,345
  • 23
  • 131
  • 206
  • 2
    "Chevaux de course" -> "Horses for courses" -> British / Australian saying means choose the right horse for the course you are going to ride -> choose the right person (or tool) for the job. – dawg Dec 03 '13 at 16:40
  • 3
    Ok :). Don't say that to a French guy, that's really "wtf". I don't think there's really an equivalent in French thought, maybe "(il faut) choisir chaussure à son pied". – Maxime Chéramy Dec 03 '13 at 16:53
6

So, my question is: is there a way to have a Decimal type with an infinite precision?

No, since storing an irrational number would require infinite memory.

Where Decimal is useful is representing things like monetary amounts, where the values need to be exact and the precision is known a priori.

From the question, it is not entirely clear that Decimal is more appropriate for your use case than float.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • I'm more interested by the second part of the question: "If not, what's the more elegant way of comparing 2 decimal numbers (e.g. d3 < 1 should return False if the delta is less than the precision)." – Maxime Chéramy Dec 03 '13 at 15:04
  • "potentially require infinite memory" is not enough otherwise there would be no big integers. The issue is that results may be irrational (can't be represented by `Fraction` precisely) and such results actually require infinite memory (and/or infinite time) e.g., `sqrt(2)`, `Pi`. – jfs Dec 03 '13 at 15:29
  • 1
    `storing an irrational number would require infinite memory` They only require infinite memory if represented as floating point numbers. You can represent irrational numbers as a symbolic object of course. Wolfram alpha. mathematic, and sympy do this. – dawg Dec 03 '13 at 18:21
  • 1
    @dawg: symbolic representations works only as long as you can get results analytically (algebraically). Otherwise we wouldn't need numerical methods. – jfs Dec 03 '13 at 21:09
  • More generally, the reals are [uncountable](https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument), but variable-width (finite) bit patterns are countable, so for *any* general encoding you might use, including those involving arbitrary precision values, there will always be real numbers which cannot be encoded, in any given interval. – Kevin Oct 07 '16 at 21:47
3

is there a way to have a Decimal type with an infinite precision?

No; for any non-empty interval on the real line, you cannot represent all the numbers in the set with infinite precision using a finite number of bits. This is why Fraction is useful, as it stores the numerator and denominator as integers, which can be represented precisely:

>>> Fraction("1.25")
Fraction(5, 4)
jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
  • Note that `Fraction('1.25')` is safer, as providing a float literal can introduce the same problem you are trying to avoid (namely, `Fraction` does not receive the exact value you intended to provide). – chepner Dec 03 '13 at 15:19
  • 2
    "You cannot represent numbers other than integers with infinite precision using a finite number of bits" seems misleading. Consider computer algebra systems that can represent such numbers as `π` and `√2` symbolically and perform exact computations with them (e.g. `√2√3 = √6`, `cos(π)=-1`). This can be done within the bounds of available memory just as for big integers. I think what you mean to say is: for any nonempty interval on the real line, you cannot represent _all_ the numbers in the set with infinite precision using a finite number of bits. – svk Dec 03 '13 at 15:21
  • @svk Thanks for your comment. A type that represent the numbers symbolically in order to perform exact computations could be a great solution. Is there such a module available for Python? – Maxime Chéramy Dec 03 '13 at 15:36
1

If you are new to Decimal, this post is relevant: Python floating point arbitrary precision available?

The essential idea from the answers and comments is that for computationally tough problems where precision is needed, you should use the mpmath module https://code.google.com/p/mpmath/. An important observation is that,

The problem with using Decimal numbers is that you can't do much in the way of math functions on Decimal objects

Community
  • 1
  • 1
William Denman
  • 3,046
  • 32
  • 34
  • The answers are indeed interesting, thank you. In order to complete your answer, SymPy allows to do symbolic mathematics which could be a good way to handle exact solutions. – Maxime Chéramy Dec 03 '13 at 15:53
  • Yup sympy is great, I use it in my research (and it's free). I also use Mathematica (but it's $$$). – William Denman Dec 03 '13 at 16:06
1

Just to point out something that might not be immediately obvious to everyone:

The documentation for the decimal module says

... The exactness carries over into arithmetic. In decimal floating point, 0.1 + 0.1 + 0.1 - 0.3 is exactly equal to zero.

(Also see the classic: Is floating point math broken?)

However, if we use decimal.Decimal naively, we get the same "unexpected" result

>>> Decimal(0.1) + Decimal(0.1) + Decimal(0.1) == Decimal(0.3)
False

The problem in the naive example above is the use of float arguments, which are "losslessly converted to [their] exact decimal equivalent," as explained in the docs.

The trick (implicit in the accepted answer) is to construct the Decimal instances using e.g. strings, instead of floats

>>> Decimal('0.1') + Decimal('0.1') + Decimal('0.1') == Decimal('0.3')
True

or, perhaps more convenient in some cases, using tuples (<sign>, <digits>, <exponent>)

>>> Decimal((0, (1,), -1)) + Decimal((0, (1,), -1)) + Decimal((0, (1,), -1)) == Decimal((0, (3,), -1))
True

Note: this does not answer the original question, but it is closely related, and may be of help to people who end up here based on the question title.

djvg
  • 11,722
  • 5
  • 72
  • 103