fixedpoint.py
Go to the documentation of this file.
00001 #!/usr/bin/env python
00002 """
00003 FixedPoint objects support decimal arithmetic with a fixed number of
00004 digits (called the object's precision) after the decimal point.  The
00005 number of digits before the decimal point is variable & unbounded.
00006 
00007 The precision is user-settable on a per-object basis when a FixedPoint
00008 is constructed, and may vary across FixedPoint objects.  The precision
00009 may also be changed after construction via FixedPoint.set_precision(p).
00010 Note that if the precision of a FixedPoint is reduced via set_precision,
00011 information may be lost to rounding.
00012 
00013 >>> x = FixedPoint("5.55")  # precision defaults to 2
00014 >>> print x
00015 5.55
00016 >>> x.set_precision(1)      # round to one fraction digit
00017 >>> print x
00018 5.6
00019 >>> print FixedPoint("5.55", 1)  # same thing setting to 1 in constructor
00020 5.6
00021 >>> repr(x) #  returns constructor string that reproduces object exactly
00022 "FixedPoint('5.6', 1)"
00023 >>>
00024 
00025 When FixedPoint objects of different precision are combined via + - * /,
00026 the result is computed to the larger of the inputs' precisions, which also
00027 becomes the precision of the resulting FixedPoint object.
00028 
00029 >>> print FixedPoint("3.42") + FixedPoint("100.005", 3)
00030 103.425
00031 >>>
00032 
00033 When a FixedPoint is combined with other numeric types (ints, floats,
00034 strings representing a number) via + - * /, then similarly the computation
00035 is carried out using-- and the result inherits --the FixedPoint's
00036 precision.
00037 
00038 >>> print FixedPoint(1) / 7
00039 0.14
00040 >>> print FixedPoint(1, 30) / 7
00041 0.142857142857142857142857142857
00042 >>>
00043 
00044 The string produced by str(x) (implictly invoked by "print") always
00045 contains at least one digit before the decimal point, followed by a
00046 decimal point, followed by exactly x.get_precision() digits.  If x is
00047 negative, str(x)[0] == "-".
00048 
00049 The FixedPoint constructor can be passed an int, long, string, float,
00050 FixedPoint, or any object convertible to a float via float() or to a
00051 long via long().  Passing a precision is optional; if specified, the
00052 precision must be a non-negative int.  There is no inherent limit on
00053 the size of the precision, but if very very large you'll probably run
00054 out of memory.
00055 
00056 Note that conversion of floats to FixedPoint can be surprising, and
00057 should be avoided whenever possible.  Conversion from string is exact
00058 (up to final rounding to the requested precision), so is greatly
00059 preferred.
00060 
00061 >>> print FixedPoint(1.1e30)
00062 1099999999999999993725589651456.00
00063 >>> print FixedPoint("1.1e30")
00064 1100000000000000000000000000000.00
00065 >>>
00066 
00067 The following Python operators and functions accept FixedPoints in the
00068 expected ways:
00069 
00070     binary + - * / % divmod
00071         with auto-coercion of other types to FixedPoint.
00072         + - % divmod  of FixedPoints are always exact.
00073         * / of FixedPoints may lose information to rounding, in
00074             which case the result is the infinitely precise answer
00075             rounded to the result's precision.
00076         divmod(x, y) returns (q, r) where q is a long equal to
00077             floor(x/y) as if x/y were computed to infinite precision,
00078             and r is a FixedPoint equal to x - q * y; no information
00079             is lost.  Note that q has the sign of y, and abs(r) < abs(y).
00080     unary -
00081     == != < > <= >=  cmp
00082     min  max
00083     float  int  long    (int and long truncate)
00084     abs
00085     str  repr
00086     hash
00087     use as dict keys
00088     use as boolean (e.g. "if some_FixedPoint:" -- true iff not zero)
00089 
00090 Methods unique to FixedPoints:
00091    .copy()              return new FixedPoint with same value
00092    .frac()              long(x) + x.frac() == x
00093    .get_precision()     return the precision(p) of this FixedPoint object
00094    .set_precision(p)    set the precision of this FixedPoint object
00095    
00096 Provided as-is; use at your own risk; no warranty; no promises; enjoy!
00097 """
00098 
00099 # Released to the public domain 28-Mar-2001,
00100 # by Tim Peters (tim.one@home.com).
00101 
00102 
00103 # 28-Mar-01 ver 0.0,4
00104 #     Use repr() instead of str() inside __str__, because str(long) changed
00105 #     since this was first written (used to produce trailing "L", doesn't
00106 #     now).
00107 #
00108 # 09-May-99 ver 0,0,3
00109 #     Repaired __sub__(FixedPoint, string); was blowing up.
00110 #     Much more careful conversion of float (now best possible).
00111 #     Implemented exact % and divmod.
00112 #
00113 # 14-Oct-98 ver 0,0,2
00114 #     Added int, long, frac.  Beefed up docs.  Removed DECIMAL_POINT
00115 #     and MINUS_SIGN globals to discourage bloating this class instead
00116 #     of writing formatting wrapper classes (or subclasses)
00117 #
00118 # 11-Oct-98 ver 0,0,1
00119 #     posted to c.l.py
00120 
00121 __copyright__ = "Copyright (C) Python Software Foundation"
00122 __author__ = "Tim Peters"
00123 __version__ = 0, 1, 0
00124 
00125 def bankersRounding(self, dividend, divisor, quotient, remainder):
00126     """
00127     rounding via nearest-even
00128     increment the quotient if
00129          the remainder is more than half of the divisor
00130       or the remainder is exactly half the divisor and the quotient is odd
00131     """
00132     c = cmp(remainder << 1, divisor)
00133     # c < 0 <-> remainder < divisor/2, etc
00134     if c > 0 or (c == 0 and (quotient & 1) == 1):
00135         quotient += 1
00136     return quotient
00137 
00138 def addHalfAndChop(self, dividend, divisor, quotient, remainder):
00139     """
00140     the equivalent of 'add half and chop'
00141     increment the quotient if
00142          the remainder is greater than half of the divisor
00143       or the remainder is exactly half the divisor and the quotient is >= 0
00144     """
00145     c = cmp(remainder << 1, divisor)
00146     # c < 0 <-> remainder < divisor/2, etc
00147     if c > 0 or (c == 0 and quotient >= 0):
00148         quotient += 1
00149     return quotient
00150 
00151 # 2002-10-20 dougfort - fake classes for pre 2.2 compatibility
00152 try:
00153     object
00154 except NameError:
00155     class object:
00156         pass
00157     def property(x, y):
00158         return None
00159 
00160 # The default value for the number of decimal digits carried after the
00161 # decimal point.  This only has effect at compile-time.
00162 DEFAULT_PRECISION = 2
00163 
00164 class FixedPoint(object):
00165     """Basic FixedPoint object class,
00166         The exact value is self.n / 10**self.p;
00167         self.n is a long; self.p is an int
00168     """
00169     __slots__ = ['n', 'p']
00170     def __init__(self, value=0, precision=DEFAULT_PRECISION):
00171         self.n = self.p = 0
00172         self.set_precision(precision)
00173         p = self.p
00174 
00175         if isinstance(value, type("42.3e5")):
00176             n, exp = _string2exact(value)
00177             # exact value is n*10**exp = n*10**(exp+p)/10**p
00178             effective_exp = exp + p
00179             if effective_exp > 0:
00180                 n = n * _tento(effective_exp)
00181             elif effective_exp < 0:
00182                 n = self._roundquotient(n, _tento(-effective_exp))
00183             self.n = n
00184             return
00185 
00186         if isinstance(value, type(42)) or isinstance(value, type(42L)):
00187             self.n = long(value) * _tento(p)
00188             return
00189 
00190         if isinstance(value, type(self)):
00191             temp = value.copy()
00192             temp.set_precision(p)
00193             self.n, self.p = temp.n, temp.p
00194             return
00195 
00196         if isinstance(value, type(42.0)):
00197             # XXX ignoring infinities and NaNs and overflows for now
00198             import math
00199             f, e = math.frexp(abs(value))
00200             assert f == 0 or 0.5 <= f < 1.0
00201             # |value| = f * 2**e exactly
00202 
00203             # Suck up CHUNK bits at a time; 28 is enough so that we suck
00204             # up all bits in 2 iterations for all known binary double-
00205             # precision formats, and small enough to fit in an int.
00206             CHUNK = 28
00207             top = 0L
00208             # invariant: |value| = (top + f) * 2**e exactly
00209             while f:
00210                 f = math.ldexp(f, CHUNK)
00211                 digit = int(f)
00212                 assert digit >> CHUNK == 0
00213                 top = (top << CHUNK) | digit
00214                 f = f - digit
00215                 assert 0.0 <= f < 1.0
00216                 e = e - CHUNK
00217 
00218             # now |value| = top * 2**e exactly
00219             # want n such that n / 10**p = top * 2**e, or
00220             # n = top * 10**p * 2**e
00221             top = top * _tento(p)
00222             if e >= 0:
00223                 n = top << e
00224             else:
00225                 n = self._roundquotient(top, 1L << -e)
00226             if value < 0:
00227                 n = -n
00228             self.n = n
00229             return
00230 
00231         if isinstance(value, type(42-42j)):
00232             raise TypeError("can't convert complex to FixedPoint: " +
00233                             `value`)
00234 
00235         # can we coerce to a float?
00236         yes = 1
00237         try:
00238             asfloat = float(value)
00239         except:
00240             yes = 0
00241         if yes:
00242             self.__init__(asfloat, p)
00243             return
00244 
00245         # similarly for long
00246         yes = 1
00247         try:
00248             aslong = long(value)
00249         except:
00250             yes = 0
00251         if yes:
00252             self.__init__(aslong, p)
00253             return
00254 
00255         raise TypeError("can't convert to FixedPoint: " + `value`)
00256 
00257     def get_precision(self):
00258         """Return the precision of this FixedPoint.
00259 
00260            The precision is the number of decimal digits carried after
00261            the decimal point, and is an int >= 0.
00262         """
00263 
00264         return self.p
00265 
00266     def set_precision(self, precision=DEFAULT_PRECISION):
00267         """Change the precision carried by this FixedPoint to p.
00268 
00269            precision must be an int >= 0, and defaults to
00270            DEFAULT_PRECISION.
00271 
00272            If precision is less than this FixedPoint's current precision,
00273            information may be lost to rounding.
00274         """
00275 
00276         try:
00277             p = int(precision)
00278         except:
00279             raise TypeError("precision not convertable to int: " +
00280                             `precision`)
00281         if p < 0:
00282             raise ValueError("precision must be >= 0: " + `precision`)
00283 
00284         if p > self.p:
00285             self.n = self.n * _tento(p - self.p)
00286         elif p < self.p:
00287             self.n = self._roundquotient(self.n, _tento(self.p - p))
00288         self.p = p
00289 
00290     precision = property(get_precision, set_precision)
00291 
00292     def __str__(self):
00293         n, p = self.n, self.p
00294         i, f = divmod(abs(n), _tento(p))
00295         if p:
00296             frac = repr(f)[:-1]
00297             frac = "0" * (p - len(frac)) + frac
00298         else:
00299             frac = ""
00300         return "-"[:n<0] + \
00301                repr(i)[:-1] + \
00302                "." + frac
00303 
00304     def __repr__(self):
00305         return "FixedPoint" + `(str(self), self.p)`
00306 
00307     def copy(self):
00308         return _mkFP(self.n, self.p, type(self))
00309 
00310     __copy__ = copy
00311 
00312     def __deepcopy__(self, memo):
00313         return self.copy()
00314 
00315     def __cmp__(self, other):
00316         xn, yn, p = _norm(self, other, FixedPoint=type(self))
00317         return cmp(xn, yn)
00318 
00319     def __hash__(self):
00320         """ Caution!  == values must have equal hashes, and a FixedPoint
00321             is essentially a rational in unnormalized form.  There's
00322             really no choice here but to normalize it, so hash is
00323             potentially expensive.
00324             n, p = self.__reduce()
00325 
00326             Obscurity: if the value is an exact integer, p will be 0 now,
00327             so the hash expression reduces to hash(n).  So FixedPoints
00328             that happen to be exact integers hash to the same things as
00329             their int or long equivalents.  This is Good.  But if a
00330             FixedPoint happens to have a value exactly representable as
00331             a float, their hashes may differ.  This is a teensy bit Bad.
00332         """
00333         n, p = self.__reduce()
00334         return hash(n) ^ hash(p)
00335 
00336     def __nonzero__(self):
00337         """ Returns true if this FixedPoint is not equal to zero"""
00338         return self.n != 0
00339 
00340     def __neg__(self):
00341         return _mkFP(-self.n, self.p, type(self))
00342 
00343     def __abs__(self):
00344         """ Returns new FixedPoint containing the absolute value of this FixedPoint"""
00345         if self.n >= 0:
00346             return self.copy()
00347         else:
00348             return -self
00349 
00350     def __add__(self, other):
00351         n1, n2, p = _norm(self, other, FixedPoint=type(self))
00352         # n1/10**p + n2/10**p = (n1+n2)/10**p
00353         return _mkFP(n1 + n2, p, type(self))
00354 
00355     __radd__ = __add__
00356 
00357     def __sub__(self, other):
00358         if not isinstance(other, type(self)):
00359             other = type(self)(other, self.p)
00360         return self.__add__(-other)
00361 
00362     def __rsub__(self, other):
00363         return (-self) + other
00364 
00365     def __mul__(self, other):
00366         n1, n2, p = _norm(self, other, FixedPoint=type(self))
00367         # n1/10**p * n2/10**p = (n1*n2/10**p)/10**p
00368         return _mkFP(self._roundquotient(n1 * n2, _tento(p)), p, type(self))
00369 
00370     __rmul__ = __mul__
00371 
00372     def __div__(self, other):
00373         n1, n2, p = _norm(self, other, FixedPoint=type(self))
00374         if n2 == 0:
00375             raise ZeroDivisionError("FixedPoint division")
00376         if n2 < 0:
00377             n1, n2 = -n1, -n2
00378         # n1/10**p / (n2/10**p) = n1/n2 = (n1*10**p/n2)/10**p
00379         return _mkFP(self._roundquotient(n1 * _tento(p), n2), p, type(self))
00380 
00381     def __rdiv__(self, other):
00382         n1, n2, p = _norm(self, other, FixedPoint=type(self))
00383         return _mkFP(n2, p, FixedPoint=type(self)) / self
00384 
00385     def __divmod__(self, other):
00386         n1, n2, p = _norm(self, other, FixedPoint=type(self))
00387         if n2 == 0:
00388             raise ZeroDivisionError("FixedPoint modulo")
00389         # floor((n1/10**p)/(n2*10**p)) = floor(n1/n2)
00390         q = n1 / n2
00391         # n1/10**p - q * n2/10**p = (n1 - q * n2)/10**p
00392         return q, _mkFP(n1 - q * n2, p, type(self))
00393 
00394     def __rdivmod__(self, other):
00395         n1, n2, p = _norm(self, other, FixedPoint=type(self))
00396         return divmod(_mkFP(n2, p), self)
00397 
00398     def __mod__(self, other):
00399         return self.__divmod__(other)[1]
00400 
00401     def __rmod__(self, other):
00402         n1, n2, p = _norm(self, other, FixedPoint=type(self))
00403         return _mkFP(n2, p, type(self)).__mod__(self)
00404 
00405     def __float__(self):
00406         """Return the floating point representation of this FixedPoint. 
00407             Caution! float can lose precision.
00408         """
00409         n, p = self.__reduce()
00410         return float(n) / float(_tento(p))
00411 
00412     def __long__(self):
00413         """EJG/DF - Should this round instead?
00414             Note e.g. long(-1.9) == -1L and long(1.9) == 1L in Python
00415             Note that __int__ inherits whatever __long__ does,
00416                  and .frac() is affected too
00417         """
00418         answer = abs(self.n) / _tento(self.p)
00419         if self.n < 0:
00420             answer = -answer
00421         return answer
00422 
00423     def __int__(self):
00424         """Return integer value of FixedPoint object."""
00425         return int(self.__long__())
00426     
00427     def frac(self):
00428         """Return fractional portion as a FixedPoint.
00429 
00430            x.frac() + long(x) == x
00431         """
00432         return self - long(self)
00433 
00434     def _roundquotient(self, x, y):
00435         """
00436         Divide x by y,
00437         return the result of rounding
00438         Developers may substitute their own 'round' for custom rounding
00439         y must be > 0
00440         """
00441         assert y > 0
00442         n, leftover = divmod(x, y)
00443         return self.round(x, y, n, leftover)
00444 
00445     def __reduce(self):
00446         """ Return n, p s.t. self == n/10**p and n % 10 != 0"""
00447         n, p = self.n, self.p
00448         if n == 0:
00449             p = 0
00450         while p and n % 10 == 0:
00451             p = p - 1
00452             n = n / 10
00453         return n, p
00454 
00455 # 2002-10-04 dougfort - Default to Banker's Rounding for backward compatibility
00456 FixedPoint.round = bankersRounding
00457 
00458 # return 10L**n
00459 
00460 def _tento(n, cache={}):
00461     """Cached computation of 10**n"""
00462     try:
00463         return cache[n]
00464     except KeyError:
00465         answer = cache[n] = 10L ** n
00466         return answer
00467 
00468 def _norm(x, y, isinstance=isinstance, FixedPoint=FixedPoint,
00469                 _tento=_tento):
00470     """Return xn, yn, p s.t.
00471            p = max(x.p, y.p)
00472            x = xn / 10**p
00473            y = yn / 10**p
00474 
00475         x must be FixedPoint to begin with; if y is not FixedPoint,
00476         it inherits its precision from x.
00477 
00478         Note that this method is called a lot, so default-arg tricks are helpful.
00479     """
00480     assert isinstance(x, FixedPoint)
00481     if not isinstance(y, FixedPoint):
00482         y = FixedPoint(y, x.p)
00483     xn, yn = x.n, y.n
00484     xp, yp = x.p, y.p
00485     if xp > yp:
00486         yn = yn * _tento(xp - yp)
00487         p = xp
00488     elif xp < yp:
00489         xn = xn * _tento(yp - xp)
00490         p = yp
00491     else:
00492         p = xp  # same as yp
00493     return xn, yn, p
00494 
00495 def _mkFP(n, p, FixedPoint=FixedPoint):
00496     """Make FixedPoint objext - Return a new FixedPoint object with the selected precision."""
00497     f = FixedPoint()
00498     #print '_mkFP Debug: %s, value=%s' % (type(f),n)
00499     f.n = n
00500     f.p = p
00501     return f
00502 
00503 # crud for parsing strings
00504 import re
00505 
00506 # There's an optional sign at the start, and an optional exponent
00507 # at the end.  The exponent has an optional sign and at least one
00508 # digit.  In between, must have either at least one digit followed
00509 # by an optional fraction, or a decimal point followed by at least
00510 # one digit.  Yuck.
00511 
00512 _parser = re.compile(r"""
00513     \s*
00514     (?P<sign>[-+])?
00515     (
00516         (?P<int>\d+) (\. (?P<frac>\d*))?
00517     |
00518         \. (?P<onlyfrac>\d+)
00519     )
00520     ([eE](?P<exp>[-+]? \d+))?
00521     \s* $
00522 """, re.VERBOSE).match
00523 
00524 del re
00525 
00526 
00527 def _string2exact(s):
00528     """Return n, p s.t. float string value == n * 10**p exactly."""
00529     m = _parser(s)
00530     if m is None:
00531         raise ValueError("can't parse as number: " + `s`)
00532 
00533     exp = m.group('exp')
00534     if exp is None:
00535         exp = 0
00536     else:
00537         exp = int(exp)
00538 
00539     intpart = m.group('int')
00540     if intpart is None:
00541         intpart = "0"
00542         fracpart = m.group('onlyfrac')
00543     else:
00544         fracpart = m.group('frac')
00545         if fracpart is None or fracpart == "":
00546             fracpart = "0"
00547     assert intpart
00548     assert fracpart
00549 
00550     i, f = long(intpart), long(fracpart)
00551     nfrac = len(fracpart)
00552     i = i * _tento(nfrac) + f
00553     exp = exp - nfrac
00554 
00555     if m.group('sign') == "-":
00556         i = -i
00557 
00558     return i, exp
00559 
00560 def _test():
00561     """Unit testing framework"""
00562     fp = FixedPoint
00563     o = fp("0.1")
00564     assert str(o) == "0.10"
00565     t = fp("-20e-2", 5)
00566     assert str(t) == "-0.20000"
00567     assert t < o
00568     assert o > t
00569     assert min(o, t) == min(t, o) == t
00570     assert max(o, t) == max(t, o) == o
00571     assert o != t
00572     assert --t == t
00573     assert abs(t) > abs(o)
00574     assert abs(o) < abs(t)
00575     assert o == o and t == t
00576     assert t.copy() == t
00577     assert o == -t/2 == -.5 * t
00578     assert abs(t) == o + o
00579     assert abs(o) == o
00580     assert o/t == -0.5
00581     assert -(t/o) == (-t)/o == t/-o == 2
00582     assert 1 + o == o + 1 == fp(" +00.000011e+5  ")
00583     assert 1/o == 10
00584     assert o + t == t + o == -o
00585     assert 2.0 * t == t * 2 == "2" * t == o/o * 2L * t
00586     assert 1 - t == -(t - 1) == fp(6L)/5
00587     assert t*t == 4*o*o == o*4*o == o*o*4
00588     assert fp(2) - "1" == 1
00589     assert float(-1/t) == 5.0
00590     for p in range(20):
00591         assert 42 + fp("1e-20", p) - 42 == 0
00592     assert 1/(42 + fp("1e-20", 20) - 42) == fp("100.0E18")
00593     o = fp(".9995", 4)
00594     assert 1 - o == fp("5e-4", 10)
00595     o.set_precision(3)
00596     assert o == 1
00597     o = fp(".9985", 4)
00598     o.set_precision(3)
00599     assert o == fp(".998", 10)
00600     assert o == o.frac()
00601     o.set_precision(100)
00602     assert o == fp(".998", 10)
00603     o.set_precision(2)
00604     assert o == 1
00605     x = fp(1.99)
00606     assert long(x) == -long(-x) == 1L
00607     assert int(x) == -int(-x) == 1
00608     assert x == long(x) + x.frac()
00609     assert -x == long(-x) + (-x).frac()
00610     assert fp(7) % 4 == 7 % fp(4) == 3
00611     assert fp(-7) % 4 == -7 % fp(4) == 1
00612     assert fp(-7) % -4 == -7 % fp(-4) == -3
00613     assert fp(7.0) % "-4.0" == 7 % fp(-4) == -1
00614     assert fp("5.5") % fp("1.1") == fp("5.5e100") % fp("1.1e100") == 0
00615     assert divmod(fp("1e100"), 3) == (long(fp("1e100")/3), 1)
00616 
00617 if __name__ == '__main__':
00618     _test()
00619 


pyclearsilver
Author(s): Scott Hassan/hassan@willowgarage.com
autogenerated on Sat Dec 28 2013 17:47:30