The problem with binary float

In decimal math, there are many numbers that can’t be represented with a fixed number of decimal digits, e.g. 1/3 = 0.3333333333…….

In base 2 (the way that standard floating point is calculated), 1/2 = 0.1, 1/4 = 0.01, 1/8 = 0.001, etc. Decimal 0.2 equals 2/10 equals 1/5, resulting in the binary fractional number 0.001100110011001… As you can see, the problem is that some decimal numbers can’t be represented exactly in binary, resulting in small roundoff errors.

So we need a decimal data type that represents exactly decimal numbers. Instead of a binary data type, we need a decimal one.

Why floating point?

So we go to decimal, but why floating point?

Floating point numbers use a fixed quantity of digits (precision) to represent a number, working with an exponent when the number gets too big or too small. For example, with a precision of 5:

  1234 ==>   1234e0
 12345 ==>  12345e0
123456 ==>  12346e1

(note that in the last line the number got rounded to fit in five digits).

In contrast, we have the example of a long integer with infinite precision, meaning that you can have the number as big as you want, and you’ll never lose any information.

In a fixed point number, the position of the decimal point is fixed. For a fixed point data type, check Tim Peter’s FixedPoint at SourceForge [4]. I’ll go for floating point because it’s easier to implement the arithmetic behaviour of the standard, and then you can implement a fixed point data type over Decimal.

But why can’t we have a floating point number with infinite precision? It’s not so easy, because of inexact divisions. E.g.: 1/3 = 0.3333333333333… ad infinitum. In this case you should store an infinite amount of 3s, which takes too much memory, ;).

John Roth proposed to eliminate the division operator and force the user to use an explicit method, just to avoid this kind of trouble. This generated adverse reactions in comp.lang.python, as everybody wants to have support for the / operator in a numeric data type.

With this exposed maybe you’re thinking “Hey! Can we just store the 1 and the 3 as numerator and denominator?”, which takes us to the next point.

Why not rational?

Rational numbers are stored using two integer numbers, the numerator and the denominator. This implies that the arithmetic operations can’t be executed directly (e.g. to add two rational numbers you first need to calculate the common denominator).

Quoting Alex Martelli:

The performance implications of the fact that summing two rationals (which take O(M) and O(N) space respectively) gives a rational which takes O(M+N) memory space is just too troublesome. There are excellent Rational implementations in both pure Python and as extensions (e.g., gmpy), but they’ll always be a “niche market” IMHO. Probably worth PEPping, not worth doing without Decimal – which is the right way to represent sums of money, a truly major use case in the real world.

Anyway, if you’re interested in this data type, you maybe will want to take a look at PEP 239: Adding a Rational Type to Python.

So, what do we have?

The result is a Decimal data type, with bounded precision and floating point.

Will it be useful? I can’t say it better than Alex Martelli:

Python (out of the box) doesn’t let you have binary floating point numbers with whatever precision you specify: you’re limited to what your hardware supplies. Decimal, be it used as a fixed or floating point number, should suffer from no such limitation: whatever bounded precision you may specify on number creation (your memory permitting) should work just as well. Most of the expense of programming simplicity can be hidden from application programs and placed in a suitable decimal arithmetic type. As per http://speleotrove.com/decimal/, a single data type can be used for integer, fixed-point, and floating-point decimal arithmetic – and for money arithmetic which doesn’t drive the application programmer crazy.

There are several uses for such a data type. As I said before, I will use it as base for Money. In this case the bounded precision is not an issue; quoting Tim Peters:

A precision of 20 would be way more than enough to account for total world economic output, down to the penny, since the beginning of time.

The Arithmetic Model

The specification is based on a decimal arithmetic model, as defined by the relevant standards: IEEE 854 [3], ANSI X3-274 [1], and the proposed revision [5] of IEEE 754 [6].

The model has three components:

• Numbers: just the values that the operation uses as input or output.
• Operations: addition, multiplication, etc.
• Context: a set of parameters and rules that the user can select and which govern the results of operations (for example, the precision to be used).

Numbers

Numbers may be finite or special values. The former can be represented exactly. The latter are infinites and undefined (such as 0/0).

Finite numbers are defined by three parameters:

• Sign: 0 (positive) or 1 (negative).
• Coefficient: a non-negative integer.
• Exponent: a signed integer, the power of ten of the coefficient multiplier.

The numerical value of a finite number is given by:

(-1)**sign * coefficient * 10**exponent

Special values are named as following:

• Infinity: a value which is infinitely large. Could be positive or negative.
• Quiet NaN (“qNaN”): represent undefined results (Not a Number). Does not cause an Invalid operation condition. The sign in a NaN has no meaning.
• Signaling NaN (“sNaN”): also Not a Number, but will cause an Invalid operation condition if used in any operation.

Context

The context is a set of parameters and rules that the user can select and which govern the results of operations (for example, the precision to be used).

The context gets that name because it surrounds the Decimal numbers, with parts of context acting as input to, and output of, operations. It’s up to the application to work with one or several contexts, but definitely the idea is not to get a context per Decimal number. For example, a typical use would be to set the context’s precision to 20 digits at the start of a program, and never explicitly use context again.

These definitions don’t affect the internal storage of the Decimal numbers, just the way that the arithmetic operations are performed.

The context is mainly defined by the following parameters (see Context Attributes for all context attributes):

• Precision: The maximum number of significant digits that can result from an arithmetic operation (integer > 0). There is no maximum for this value.
• Rounding: The name of the algorithm to be used when rounding is necessary, one of “round-down”, “round-half-up”, “round-half-even”, “round-ceiling”, “round-floor”, “round-half-down”, and “round-up”. See Rounding Algorithms below.
• Flags and trap-enablers: Exceptional conditions are grouped into signals, controllable individually, each consisting of a flag (boolean, set when the signal occurs) and a trap-enabler (a boolean that controls behavior). The signals are: “clamped”, “division-by-zero”, “inexact”, “invalid-operation”, “overflow”, “rounded”, “subnormal” and “underflow”.

Default Contexts

The specification defines two default contexts, which should be easily selectable by the user.

Basic Default Context:

• flags: all set to 0
• trap-enablers: inexact, rounded, and subnormal are set to 0; all others are set to 1
• precision: is set to 9
• rounding: is set to round-half-up

Extended Default Context:

• flags: all set to 0
• trap-enablers: all set to 0
• precision: is set to 9
• rounding: is set to round-half-even

Exceptional Conditions

The table below lists the exceptional conditions that may arise during the arithmetic operations, the corresponding signal, and the defined result. For details, see the specification [2].

Note: when the standard talks about “Insufficient storage”, as long as this is implementation-specific behaviour about not having enough storage to keep the internals of the number, this implementation will raise MemoryError.

Regarding Overflow and Underflow, there’s been a long discussion in python-dev about artificial limits. The general consensus is to keep the artificial limits only if there are important reasons to do that. Tim Peters gives us three:

…eliminating bounds on exponents effectively means overflow (and underflow) can never happen. But overflow is a valuable safety net in real life fp use, like a canary in a coal mine, giving danger signs early when a program goes insane.

Virtually all implementations of 854 use (and as IBM’s standard even suggests) “forbidden” exponent values to encode non-finite numbers (infinities and NaNs). A bounded exponent can do this at virtually no extra storage cost. If the exponent is unbounded, then additional bits have to be used instead. This cost remains hidden until more time- and space- efficient implementations are attempted.

Big as it is, the IBM standard is a tiny start at supplying a complete numeric facility. Having no bound on exponent size will enormously complicate the implementations of, e.g., decimal sin() and cos() (there’s then no a priori limit on how many digits of pi effectively need to be known in order to perform argument reduction).

Edward Loper give us an example of when the limits are to be crossed: probabilities.

That said, Robert Brewer and Andrew Lentvorski want the limits to be easily modifiable by the users. Actually, this is quite possible:

>>> d1 = Decimal("1e999999999")     # at the exponent limit
>>> d1
Decimal("1E+999999999")
>>> d1 * 10                         # exceed the limit, got infinity
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in ?
    d1 * 10
  ...
  ...
Overflow: above Emax
>>> getcontext().Emax = 1000000000  # increase the limit
>>> d1 * 10                         # does not exceed any more
Decimal("1.0E+1000000000")
>>> d1 * 100                        # exceed again
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in ?
    d1 * 100
  ...
  ...
Overflow: above Emax

Rounding Algorithms

round-down: The discarded digits are ignored; the result is unchanged (round toward 0, truncate):

1.123 --> 1.12
1.128 --> 1.12
1.125 --> 1.12
1.135 --> 1.13

round-half-up: If the discarded digits represent greater than or equal to half (0.5) then the result should be incremented by 1; otherwise the discarded digits are ignored:

1.123 --> 1.12
1.128 --> 1.13
1.125 --> 1.13
1.135 --> 1.14

round-half-even: If the discarded digits represent greater than half (0.5) then the result coefficient is incremented by 1; if they represent less than half, then the result is not adjusted; otherwise the result is unaltered if its rightmost digit is even, or incremented by 1 if its rightmost digit is odd (to make an even digit):

1.123 --> 1.12
1.128 --> 1.13
1.125 --> 1.12
1.135 --> 1.14

round-ceiling: If all of the discarded digits are zero or if the sign is negative the result is unchanged; otherwise, the result is incremented by 1 (round toward positive infinity):

 1.123 -->  1.13
 1.128 -->  1.13
-1.123 --> -1.12
-1.128 --> -1.12

round-floor: If all of the discarded digits are zero or if the sign is positive the result is unchanged; otherwise, the absolute value of the result is incremented by 1 (round toward negative infinity):

 1.123 -->  1.12
 1.128 -->  1.12
-1.123 --> -1.13
-1.128 --> -1.13

round-half-down: If the discarded digits represent greater than half (0.5) then the result is incremented by 1; otherwise the discarded digits are ignored:

1.123 --> 1.12
1.128 --> 1.13
1.125 --> 1.12
1.135 --> 1.13

round-up: If all of the discarded digits are zero the result is unchanged, otherwise the result is incremented by 1 (round away from 0):

1.123 --> 1.13
1.128 --> 1.13
1.125 --> 1.13
1.135 --> 1.14

Explicit construction

The explicit construction does not get affected by the context (there is no rounding, no limits by the precision, etc.), because the context affects just operations’ results. The only exception to this is when you’re Creating from Context.

Decimal(35)
Decimal(-124)

Decimal("-12")
Decimal("23.2e-7")

Decimal("Inf")
Decimal("NaN")

(1) says  D(1.1) == D('1.1')
but       1.1 == 1.1000000000000001
so        D(1.1) == D(1.1000000000000001)
together: D(1.1000000000000001) == D('1.1')

d = Decimal (1.1, 1)  # take float value to 1 decimal place
d = Decimal (1.1)  # gets `places` from pre-set context

Decimal.from_float(floatNumber, [decimal_places])

Decimal.from_float(1.1, 2): The same as doing Decimal('1.1').
Decimal.from_float(1.1, 16): The same as doing Decimal('1.1000000000000001').
Decimal.from_float(1.1): The same as doing Decimal('1100000000000000088817841970012523233890533447265625e-51').

Decimal((1, (3, 2, 2, 5), -2))     # for -32.25

Decimal( (0, (0,), 'F') )          # for Infinity
Decimal( (0, (0,), 'n') )          # for Not a Number

Decimal(value1)
Decimal.from_float(value2, [decimal_places])

D.using_context(number, context)

context.create_decimal(number)

# n is any datatype accepted in Decimal(n) plus float
mycontext.create_decimal(n)

>>> # create a standard decimal instance
>>> Decimal("11.2233445566778899")
Decimal("11.2233445566778899")
>>>
>>> # create a decimal instance using the thread context
>>> thread_context = getcontext()
>>> thread_context.prec
28
>>> thread_context.create_decimal("11.2233445566778899")
Decimal("11.2233445566778899")
>>>
>>> # create a decimal instance using other context
>>> other_context = thread_context.copy()
>>> other_context.prec = 4
>>> other_context.create_decimal("11.2233445566778899")
Decimal("11.22")

Implicit construction

As the implicit construction is the consequence of an operation, it will be affected by the context as is detailed in each point.

John Roth suggested that “The other type should be handled in the same way the decimal() constructor would handle it”. But Alex Martelli thinks that

this total breach with Python tradition would be a terrible mistake. 23+”43” is NOT handled in the same way as 23+int(“45”), and a VERY good thing that is too. It’s a completely different thing for a user to EXPLICITLY indicate they want construction (conversion) and to just happen to sum two objects one of which by mistake could be a string.

So, here I define the behaviour again for each data type.

Use of Context

In the last pre-PEP I said that “The Context must be omnipresent, meaning that changes to it affects all the current and future Decimal instances”. I was wrong. In response, John Roth said:

The context should be selectable for the particular usage. That is, it should be possible to have several different contexts in play at one time in an application.

In comp.lang.python, Aahz explained that the idea is to have a “context per thread”. So, all the instances of a thread belongs to a context, and you can change a context in thread A (and the behaviour of the instances of that thread) without changing nothing in thread B.

Also, and again correcting me, he said:

(the) Context applies only to operations, not to Decimal instances; changing the Context does not affect existing instances if there are no operations on them.

Arguing about special cases when there’s need to perform operations with other rules that those of the current context, Tim Peters said that the context will have the operations as methods. This way, the user “can create whatever private context object(s) it needs, and spell arithmetic as explicit method calls on its private context object(s), so that the default thread context object is neither consulted nor modified”.

Python Usability

• Decimal should support the basic arithmetic (+, -, *, /, //, **, %, divmod) and comparison (==, !=, <, >, <=, >=, cmp) operators in the following cases (check Implicit Construction to see what types could OtherType be, and what happens in each case):
  • Decimal op Decimal
  • Decimal op otherType
  • otherType op Decimal
  • Decimal op= Decimal
  • Decimal op= otherType
• Decimal should support unary operators (-, +, abs).
• repr() should round trip, meaning that:

  m = Decimal(...)
  m == eval(repr(m))
  

• Decimal should be immutable.
• Decimal should support the built-in methods:
  • min, max
  • float, int, long
  • str, repr
  • hash
  • bool (0 is false, otherwise true)

There’s been some discussion in python-dev about the behaviour of hash(). The community agrees that if the values are the same, the hashes of those values should also be the same. So, while Decimal(25) == 25 is True, hash(Decimal(25)) should be equal to hash(25).

The detail is that you can NOT compare Decimal to floats or strings, so we should not worry about them giving the same hashes. In short:

hash(n) == hash(Decimal(n))   # Only if n is int, long, or Decimal

Regarding str() and repr() behaviour, Ka-Ping Yee proposes that repr() have the same behaviour as str() and Tim Peters proposes that str() behave like the to-scientific-string operation from the Spec.

This is possible, because (from Aahz): “The string form already contains all the necessary information to reconstruct a Decimal object”.

And it also complies with the Spec; Tim Peters:

There’s no requirement to have a method named “to_sci_string”, the only requirement is that some way to spell to-sci-string’s functionality be supplied. The meaning of to-sci-string is precisely specified by the standard, and is a good choice for both str(Decimal) and repr(Decimal).

Decimal Attributes

Decimal has no public attributes. The internal information is stored in slots and should not be accessed by end users.

Decimal Methods

Following are the conversion and arithmetic operations defined in the Spec, and how that functionality can be achieved with the actual implementation.

• to-scientific-string: Use builtin function str():

  >>> d = Decimal('123456789012.345')
  >>> str(d)
  '1.23456789E+11'
  

• to-engineering-string: Use method to_eng_string():

  >>> d = Decimal('123456789012.345')
  >>> d.to_eng_string()
  '123.456789E+9'
  

• to-number: Use Context method create_decimal(). The standard constructor or from_float() constructor cannot be used because these do not use the context (as is specified in the Spec for this conversion).
• abs: Use builtin function abs():

  >>> d = Decimal('-15.67')
  >>> abs(d)
  Decimal('15.67')
  

• add: Use operator +:

  >>> d = Decimal('15.6')
  >>> d + 8
  Decimal('23.6')
  

• subtract: Use operator -:

  >>> d = Decimal('15.6')
  >>> d - 8
  Decimal('7.6')
  

• compare: Use method compare(). This method (and not the built-in function cmp()) should only be used when dealing with special values:

  >>> d = Decimal('-15.67')
  >>> nan = Decimal('NaN')
  >>> d.compare(23)
  '-1'
  >>> d.compare(nan)
  'NaN'
  >>> cmp(d, 23)
  -1
  >>> cmp(d, nan)
  1
  

• divide: Use operator /:

  >>> d = Decimal('-15.67')
  >>> d / 2
  Decimal('-7.835')
  

• divide-integer: Use operator //:

  >>> d = Decimal('-15.67')
  >>> d // 2
  Decimal('-7')
  

• max: Use method max(). Only use this method (and not the built-in function max()) when dealing with special values:

  >>> d = Decimal('15')
  >>> nan = Decimal('NaN')
  >>> d.max(8)
  Decimal('15')
  >>> d.max(nan)
  Decimal('NaN')
  

• min: Use method min(). Only use this method (and not the built-in function min()) when dealing with special values:

  >>> d = Decimal('15')
  >>> nan = Decimal('NaN')
  >>> d.min(8)
  Decimal('8')
  >>> d.min(nan)
  Decimal('NaN')
  

• minus: Use unary operator -:

  >>> d = Decimal('-15.67')
  >>> -d
  Decimal('15.67')
  

• plus: Use unary operator +:

  >>> d = Decimal('-15.67')
  >>> +d
  Decimal('-15.67')
  

• multiply: Use operator *:

  >>> d = Decimal('5.7')
  >>> d * 3
  Decimal('17.1')
  

• normalize: Use method normalize():

  >>> d = Decimal('123.45000')
  >>> d.normalize()
  Decimal('123.45')
  >>> d = Decimal('120.00')
  >>> d.normalize()
  Decimal('1.2E+2')
  

• quantize: Use method quantize():

  >>> d = Decimal('2.17')
  >>> d.quantize(Decimal('0.001'))
  Decimal('2.170')
  >>> d.quantize(Decimal('0.1'))
  Decimal('2.2')
  

• remainder: Use operator %:

  >>> d = Decimal('10')
  >>> d % 3
  Decimal('1')
  >>> d % 6
  Decimal('4')
  

• remainder-near: Use method remainder_near():

  >>> d = Decimal('10')
  >>> d.remainder_near(3)
  Decimal('1')
  >>> d.remainder_near(6)
  Decimal('-2')
  

• round-to-integral-value: Use method to_integral():

  >>> d = Decimal('-123.456')
  >>> d.to_integral()
  Decimal('-123')
  

• same-quantum: Use method same_quantum():

  >>> d = Decimal('123.456')
  >>> d.same_quantum(Decimal('0.001'))
  True
  >>> d.same_quantum(Decimal('0.01'))
  False
  

• square-root: Use method sqrt():

  >>> d = Decimal('123.456')
  >>> d.sqrt()
  Decimal('11.1110756')
  

• power: User operator **:

  >>> d = Decimal('12.56')
  >>> d ** 2
  Decimal('157.7536')
  

Following are other methods and why they exist:

• adjusted(): Returns the adjusted exponent. This concept is defined in the Spec: the adjusted exponent is the value of the exponent of a number when that number is expressed as though in scientific notation with one digit before any decimal point:

  >>> d = Decimal('12.56')
  >>> d.adjusted()
  1
  

• from_float(): Class method to create instances from float data types:

  >>> d = Decimal.from_float(12.35)
  >>> d
  Decimal('12.3500000')
  

• as_tuple(): Show the internal structure of the Decimal, the triple tuple. This method is not required by the Spec, but Tim Peters proposed it and the community agreed to have it (it’s useful for developing and debugging):

  >>> d = Decimal('123.4')
  >>> d.as_tuple()
  (0, (1, 2, 3, 4), -1)
  >>> d = Decimal('-2.34e5')
  >>> d.as_tuple()
  (1, (2, 3, 4), 3)
  

Context Attributes

These are the attributes that can be changed to modify the context.

• prec (int): the precision:

  >>> c.prec
  9
  

• rounding (str): rounding type (how to round):

  >>> c.rounding
  'half_even'
  

• trap_enablers (dict): if trap_enablers[exception] = 1, then an exception is raised when it is caused:

  >>> c.trap_enablers[Underflow]
  0
  >>> c.trap_enablers[Clamped]
  0
  

• flags (dict): when an exception is caused, flags[exception] is incremented (whether or not the trap_enabler is set). Should be reset by the user of Decimal instance:

  >>> c.flags[Underflow]
  0
  >>> c.flags[Clamped]
  0
  

• Emin (int): minimum exponent:

  >>> c.Emin
  -999999999
  

• Emax (int): maximum exponent:

  >>> c.Emax
  999999999
  

• capitals (int): boolean flag to use ‘E’ (True/1) or ‘e’ (False/0) in the string (for example, ‘1.32e+2’ or ‘1.32E+2’):

  >>> c.capitals
  1
  

Context Methods

The following methods comply with Decimal functionality from the Spec. Be aware that the operations that are called through a specific context use that context and not the thread context.

To use these methods, take note that the syntax changes when the operator is binary or unary, for example:

>>> mycontext.abs(Decimal('-2'))
'2'
>>> mycontext.multiply(Decimal('2.3'), 5)
'11.5'

So, the following are the Spec operations and conversions and how to achieve them through a context (where d is a Decimal instance and n a number that can be used in an Implicit construction):

• to-scientific-string: to_sci_string(d)
• to-engineering-string: to_eng_string(d)
• to-number: create_decimal(number), see Explicit construction for number.
• abs: abs(d)
• add: add(d, n)
• subtract: subtract(d, n)
• compare: compare(d, n)
• divide: divide(d, n)
• divide-integer: divide_int(d, n)
• max: max(d, n)
• min: min(d, n)
• minus: minus(d)
• plus: plus(d)
• multiply: multiply(d, n)
• normalize: normalize(d)
• quantize: quantize(d, d)
• remainder: remainder(d)
• remainder-near: remainder_near(d)
• round-to-integral-value: to_integral(d)
• same-quantum: same_quantum(d, d)
• square-root: sqrt(d)
• power: power(d, n)

The divmod(d, n) method supports decimal functionality through Context.

These are methods that return useful information from the Context:

• Etiny(): Minimum exponent considering precision.

  >>> c.Emin
  -999999999
  >>> c.Etiny()
  -1000000007
  

• Etop(): Maximum exponent considering precision.

  >>> c.Emax
  999999999
  >>> c.Etop()
  999999991
  

• copy(): Returns a copy of the context.