openerp/tools/float_utils.py

   1 # -*- coding: utf-8 -*-
   2 ##############################################################################
   3 #
   4 #    OpenERP, Open Source Business Applications
   5 #    Copyright (c) 2011 OpenERP S.A. <http://openerp.com>
   6 #
   7 #    This program is free software: you can redistribute it and/or modify
   8 #    it under the terms of the GNU Affero General Public License as
   9 #    published by the Free Software Foundation, either version 3 of the
  10 #    License, or (at your option) any later version.
  11 #
  12 #    This program is distributed in the hope that it will be useful,
  13 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 #    GNU Affero General Public License for more details.
  16 #
  17 #    You should have received a copy of the GNU Affero General Public License
  18 #    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19 #
  20 ##############################################################################
  21
  22 import math
  23
  24 def _float_check_precision(precision_digits=None, precision_rounding=None):
  25     assert (precision_digits is not None or precision_rounding is not None) and \
  26         not (precision_digits and precision_rounding),\
  27          "exactly one of precision_digits and precision_rounding must be specified"
  28     if precision_digits is not None:
  29         return 10 ** -precision_digits
  30     return precision_rounding
  31
  32 def float_round(value, precision_digits=None, precision_rounding=None):
  33     """Return ``value`` rounded to ``precision_digits``
  34        decimal digits, minimizing IEEE-754 floating point representation
  35        errors, and applying HALF-UP (away from zero) tie-breaking rule.
  36        Precision must be given by ``precision_digits`` or ``precision_rounding``,
  37        not both!
  38
  39        :param float value: the value to round
  40        :param int precision_digits: number of fractional digits to round to.
  41        :param float precision_rounding: decimal number representing the minimum
  42            non-zero value at the desired precision (for example, 0.01 for a
  43            2-digit precision).
  44        :return: rounded float
  45     """
  46     rounding_factor = _float_check_precision(precision_digits=precision_digits,
  47                                              precision_rounding=precision_rounding)
  48     if rounding_factor == 0 or value == 0: return 0.0
  49
  50     # NORMALIZE - ROUND - DENORMALIZE
  51     # In order to easily support rounding to arbitrary 'steps' (e.g. coin values),
  52     # we normalize the value before rounding it as an integer, and de-normalize
  53     # after rounding: e.g. float_round(1.3, precision_rounding=.5) == 1.5
  54
  55     # TIE-BREAKING: HALF-UP
  56     # We want to apply HALF-UP tie-breaking rules, i.e. 0.5 rounds away from 0.
  57     # Due to IEE754 float/double representation limits, the approximation of the
  58     # real value may be slightly below the tie limit, resulting in an error of
  59     # 1 unit in the last place (ulp) after rounding.
  60     # For example 2.675 == 2.6749999999999998.
  61     # To correct this, we add a very small epsilon value, scaled to the
  62     # the order of magnitude of the value, to tip the tie-break in the right
  63     # direction.
  64     # Credit: discussion with OpenERP community members on bug 882036
  65
  66     normalized_value = value / rounding_factor # normalize
  67     epsilon_magnitude = math.log(abs(normalized_value), 2)
  68     epsilon = 2**(epsilon_magnitude-53)
  69     normalized_value += cmp(normalized_value,0) * epsilon
  70     rounded_value = round(normalized_value) # round to integer
  71     result = rounded_value * rounding_factor # de-normalize
  72     return result
  73
  74 def float_is_zero(value, precision_digits=None, precision_rounding=None):
  75     """Returns true if ``value`` is small enough to be treated as
  76        zero at the given precision (smaller than the corresponding *epsilon*).
  77        The precision (``10**-precision_digits`` or ``precision_rounding``)
  78        is used as the zero *epsilon*: values less than that are considered
  79        to be zero.
  80        Precision must be given by ``precision_digits`` or ``precision_rounding``,
  81        not both!
  82
  83        Warning: ``float_is_zero(value1-value2)`` is not equivalent to
  84        ``float_compare(value1,value2) == 0``, as the former will round after
  85        computing the difference, while the latter will round before, giving
  86        different results for e.g. 0.006 and 0.002 at 2 digits precision.
  87
  88        :param int precision_digits: number of fractional digits to round to.
  89        :param float precision_rounding: decimal number representing the minimum
  90            non-zero value at the desired precision (for example, 0.01 for a
  91            2-digit precision).
  92        :param float value: value to compare with the precision's zero
  93        :return: True if ``value`` is considered zero
  94     """
  95     epsilon = _float_check_precision(precision_digits=precision_digits,
  96                                              precision_rounding=precision_rounding)
  97     return abs(float_round(value, precision_rounding=epsilon)) < epsilon
  98
  99 def float_compare(value1, value2, precision_digits=None, precision_rounding=None):
 100     """Compare ``value1`` and ``value2`` after rounding them according to the
 101        given precision. A value is considered lower/greater than another value
 102        if their rounded value is different. This is not the same as having a
 103        non-zero difference!
 104        Precision must be given by ``precision_digits`` or ``precision_rounding``,
 105        not both!
 106
 107        Example: 1.432 and 1.431 are equal at 2 digits precision,
 108        so this method would return 0
 109        However 0.006 and 0.002 are considered different (this method returns 1)
 110        because they respectively round to 0.01 and 0.0, even though
 111        0.006-0.002 = 0.004 which would be considered zero at 2 digits precision.
 112
 113        Warning: ``float_is_zero(value1-value2)`` is not equivalent to
 114        ``float_compare(value1,value2) == 0``, as the former will round after
 115        computing the difference, while the latter will round before, giving
 116        different results for e.g. 0.006 and 0.002 at 2 digits precision.
 117
 118        :param int precision_digits: number of fractional digits to round to.
 119        :param float precision_rounding: decimal number representing the minimum
 120            non-zero value at the desired precision (for example, 0.01 for a
 121            2-digit precision).
 122        :param float value1: first value to compare
 123        :param float value2: second value to compare
 124        :return: (resp.) -1, 0 or 1, if ``value1`` is (resp.) lower than,
 125            equal to, or greater than ``value2``, at the given precision.
 126     """
 127     rounding_factor = _float_check_precision(precision_digits=precision_digits,
 128                                              precision_rounding=precision_rounding)
 129     value1 = float_round(value1, precision_rounding=rounding_factor)
 130     value2 = float_round(value2, precision_rounding=rounding_factor)
 131     delta = value1 - value2
 132     if float_is_zero(delta, precision_rounding=rounding_factor): return 0
 133     return -1 if delta < 0.0 else 1
 134
 135 def float_repr(value, precision_digits):
 136     """Returns a string representation of a float with the
 137        the given number of fractional digits. This should not be
 138        used to perform a rounding operation (this is done via
 139        :meth:`~.float_round`), but only to produce a suitable
 140        string representation for a float.
 141
 142         :param int precision_digits: number of fractional digits to
 143                                      include in the output
 144     """
 145     # Can't use str() here because it seems to have an intrisic
 146     # rounding to 12 significant digits, which causes a loss of
 147     # precision. e.g. str(123456789.1234) == str(123456789.123)!!
 148     return ("%%.%sf" % precision_digits) % value
 149
 150
 151 if __name__ == "__main__":
 152
 153     import time
 154     start = time.time()
 155     count = 0
 156     errors = 0
 157
 158     def try_round(amount, expected, precision_digits=3):
 159         global count, errors; count += 1
 160         result = float_repr(float_round(amount, precision_digits=precision_digits),
 161                             precision_digits=precision_digits)
 162         if result != expected:
 163             errors += 1
 164             print '###!!! Rounding error: got %s , expected %s' % (result, expected)
 165
 166     # Extended float range test, inspired by Cloves Almeida's test on bug #882036.
 167     fractions = [.0, .015, .01499, .675, .67499, .4555, .4555, .45555]
 168     expecteds = ['.00', '.02', '.01', '.68', '.67', '.46', '.456', '.4556']
 169     precisions = [2, 2, 2, 2, 2, 2, 3, 4]
 170     for magnitude in range(7):
 171         for i in xrange(len(fractions)):
 172             frac, exp, prec = fractions[i], expecteds[i], precisions[i]
 173             for sign in [-1,1]:
 174                 for x in xrange(0,10000,97):
 175                     n = x * 10**magnitude
 176                     f = sign * (n + frac)
 177                     f_exp = ('-' if f != 0 and sign == -1 else '') + str(n) + exp
 178                     try_round(f, f_exp, precision_digits=prec)
 179
 180     stop = time.time()
 181
 182     # Micro-bench results:
 183     # 47130 round calls in 0.422306060791 secs, with Python 2.6.7 on Core i3 x64
 184     # with decimal:
 185     # 47130 round calls in 6.612248100021 secs, with Python 2.6.7 on Core i3 x64
 186     print count, " round calls, ", errors, "errors, done in ", (stop-start), 'secs'