fixedpoint.py
Go to the documentation of this file.
1 #!/usr/bin/env python
2 """
3 FixedPoint objects support decimal arithmetic with a fixed number of
4 digits (called the object's precision) after the decimal point. The
5 number of digits before the decimal point is variable & unbounded.
6
7 The precision is user-settable on a per-object basis when a FixedPoint
8 is constructed, and may vary across FixedPoint objects. The precision
9 may also be changed after construction via FixedPoint.set_precision(p).
10 Note that if the precision of a FixedPoint is reduced via set_precision,
11 information may be lost to rounding.
12
13 >>> x = FixedPoint("5.55") # precision defaults to 2
14 >>> print x
15 5.55
16 >>> x.set_precision(1) # round to one fraction digit
17 >>> print x
18 5.6
19 >>> print FixedPoint("5.55", 1) # same thing setting to 1 in constructor
20 5.6
21 >>> repr(x) # returns constructor string that reproduces object exactly
22 "FixedPoint('5.6', 1)"
23 >>>
24
25 When FixedPoint objects of different precision are combined via + - * /,
26 the result is computed to the larger of the inputs' precisions, which also
27 becomes the precision of the resulting FixedPoint object.
28
29 >>> print FixedPoint("3.42") + FixedPoint("100.005", 3)
30 103.425
31 >>>
32
33 When a FixedPoint is combined with other numeric types (ints, floats,
34 strings representing a number) via + - * /, then similarly the computation
35 is carried out using-- and the result inherits --the FixedPoint's
36 precision.
37
38 >>> print FixedPoint(1) / 7
39 0.14
40 >>> print FixedPoint(1, 30) / 7
41 0.142857142857142857142857142857
42 >>>
43
44 The string produced by str(x) (implictly invoked by "print") always
45 contains at least one digit before the decimal point, followed by a
46 decimal point, followed by exactly x.get_precision() digits. If x is
47 negative, str(x) == "-".
48
49 The FixedPoint constructor can be passed an int, long, string, float,
50 FixedPoint, or any object convertible to a float via float() or to a
51 long via long(). Passing a precision is optional; if specified, the
52 precision must be a non-negative int. There is no inherent limit on
53 the size of the precision, but if very very large you'll probably run
54 out of memory.
55
56 Note that conversion of floats to FixedPoint can be surprising, and
57 should be avoided whenever possible. Conversion from string is exact
58 (up to final rounding to the requested precision), so is greatly
59 preferred.
60
61 >>> print FixedPoint(1.1e30)
62 1099999999999999993725589651456.00
63 >>> print FixedPoint("1.1e30")
64 1100000000000000000000000000000.00
65 >>>
66
67 The following Python operators and functions accept FixedPoints in the
68 expected ways:
69
70  binary + - * / % divmod
71  with auto-coercion of other types to FixedPoint.
72  + - % divmod of FixedPoints are always exact.
73  * / of FixedPoints may lose information to rounding, in
74  which case the result is the infinitely precise answer
75  rounded to the result's precision.
76  divmod(x, y) returns (q, r) where q is a long equal to
77  floor(x/y) as if x/y were computed to infinite precision,
78  and r is a FixedPoint equal to x - q * y; no information
79  is lost. Note that q has the sign of y, and abs(r) < abs(y).
80  unary -
81  == != < > <= >= cmp
82  min max
83  float int long (int and long truncate)
84  abs
85  str repr
86  hash
87  use as dict keys
88  use as boolean (e.g. "if some_FixedPoint:" -- true iff not zero)
89
90 Methods unique to FixedPoints:
91  .copy() return new FixedPoint with same value
92  .frac() long(x) + x.frac() == x
93  .get_precision() return the precision(p) of this FixedPoint object
94  .set_precision(p) set the precision of this FixedPoint object
95
96 Provided as-is; use at your own risk; no warranty; no promises; enjoy!
97 """
98
99 # Released to the public domain 28-Mar-2001,
100 # by Tim Peters (tim.one@home.com).
101
102
103 # 28-Mar-01 ver 0.0,4
104 # Use repr() instead of str() inside __str__, because str(long) changed
105 # since this was first written (used to produce trailing "L", doesn't
106 # now).
107 #
108 # 09-May-99 ver 0,0,3
109 # Repaired __sub__(FixedPoint, string); was blowing up.
110 # Much more careful conversion of float (now best possible).
111 # Implemented exact % and divmod.
112 #
113 # 14-Oct-98 ver 0,0,2
114 # Added int, long, frac. Beefed up docs. Removed DECIMAL_POINT
115 # and MINUS_SIGN globals to discourage bloating this class instead
116 # of writing formatting wrapper classes (or subclasses)
117 #
118 # 11-Oct-98 ver 0,0,1
119 # posted to c.l.py
120
122 __author__ = "Tim Peters"
123 __version__ = 0, 1, 0
124
125 def bankersRounding(self, dividend, divisor, quotient, remainder):
126  """
127  rounding via nearest-even
128  increment the quotient if
129  the remainder is more than half of the divisor
130  or the remainder is exactly half the divisor and the quotient is odd
131  """
132  c = cmp(remainder << 1, divisor)
133  # c < 0 <-> remainder < divisor/2, etc
134  if c > 0 or (c == 0 and (quotient & 1) == 1):
135  quotient += 1
136  return quotient
137
138 def addHalfAndChop(self, dividend, divisor, quotient, remainder):
139  """
140  the equivalent of 'add half and chop'
141  increment the quotient if
142  the remainder is greater than half of the divisor
143  or the remainder is exactly half the divisor and the quotient is >= 0
144  """
145  c = cmp(remainder << 1, divisor)
146  # c < 0 <-> remainder < divisor/2, etc
147  if c > 0 or (c == 0 and quotient >= 0):
148  quotient += 1
149  return quotient
150
151 # 2002-10-20 dougfort - fake classes for pre 2.2 compatibility
152 try:
153  object
154 except NameError:
155  class object:
156  pass
157  def property(x, y):
158  return None
159
160 # The default value for the number of decimal digits carried after the
161 # decimal point. This only has effect at compile-time.
162 DEFAULT_PRECISION = 2
163
165  """Basic FixedPoint object class,
166  The exact value is self.n / 10**self.p;
167  self.n is a long; self.p is an int
168  """
169  __slots__ = ['n', 'p']
170  def __init__(self, value=0, precision=DEFAULT_PRECISION):
171  self.n = self.p = 0
172  self.set_precision(precision)
173  p = self.p
174
175  if isinstance(value, type("42.3e5")):
176  n, exp = _string2exact(value)
177  # exact value is n*10**exp = n*10**(exp+p)/10**p
178  effective_exp = exp + p
179  if effective_exp > 0:
180  n = n * _tento(effective_exp)
181  elif effective_exp < 0:
182  n = self._roundquotient(n, _tento(-effective_exp))
183  self.n = n
184  return
185
186  if isinstance(value, type(42)) or isinstance(value, type(42L)):
187  self.n = long(value) * _tento(p)
188  return
189
190  if isinstance(value, type(self)):
191  temp = value.copy()
192  temp.set_precision(p)
193  self.n, self.p = temp.n, temp.p
194  return
195
196  if isinstance(value, type(42.0)):
197  # XXX ignoring infinities and NaNs and overflows for now
198  import math
199  f, e = math.frexp(abs(value))
200  assert f == 0 or 0.5 <= f < 1.0
201  # |value| = f * 2**e exactly
202
203  # Suck up CHUNK bits at a time; 28 is enough so that we suck
204  # up all bits in 2 iterations for all known binary double-
205  # precision formats, and small enough to fit in an int.
206  CHUNK = 28
207  top = 0L
208  # invariant: |value| = (top + f) * 2**e exactly
209  while f:
210  f = math.ldexp(f, CHUNK)
211  digit = int(f)
212  assert digit >> CHUNK == 0
213  top = (top << CHUNK) | digit
214  f = f - digit
215  assert 0.0 <= f < 1.0
216  e = e - CHUNK
217
218  # now |value| = top * 2**e exactly
219  # want n such that n / 10**p = top * 2**e, or
220  # n = top * 10**p * 2**e
221  top = top * _tento(p)
222  if e >= 0:
223  n = top << e
224  else:
225  n = self._roundquotient(top, 1L << -e)
226  if value < 0:
227  n = -n
228  self.n = n
229  return
230
231  if isinstance(value, type(42-42j)):
232  raise TypeError("can't convert complex to FixedPoint: " +
233  `value`)
234
235  # can we coerce to a float?
236  yes = 1
237  try:
238  asfloat = float(value)
239  except:
240  yes = 0
241  if yes:
242  self.__init__(asfloat, p)
243  return
244
245  # similarly for long
246  yes = 1
247  try:
248  aslong = long(value)
249  except:
250  yes = 0
251  if yes:
252  self.__init__(aslong, p)
253  return
254
255  raise TypeError("can't convert to FixedPoint: " + `value`)
256
257  def get_precision(self):
258  """Return the precision of this FixedPoint.
259
260  The precision is the number of decimal digits carried after
261  the decimal point, and is an int >= 0.
262  """
263
264  return self.p
265
266  def set_precision(self, precision=DEFAULT_PRECISION):
267  """Change the precision carried by this FixedPoint to p.
268
269  precision must be an int >= 0, and defaults to
270  DEFAULT_PRECISION.
271
272  If precision is less than this FixedPoint's current precision,
273  information may be lost to rounding.
274  """
275
276  try:
277  p = int(precision)
278  except:
279  raise TypeError("precision not convertable to int: " +
280  `precision`)
281  if p < 0:
282  raise ValueError("precision must be >= 0: " + `precision`)
283
284  if p > self.p:
285  self.n = self.n * _tento(p - self.p)
286  elif p < self.p:
287  self.n = self._roundquotient(self.n, _tento(self.p - p))
288  self.p = p
289
290  precision = property(get_precision, set_precision)
291
292  def __str__(self):
293  n, p = self.n, self.p
294  i, f = divmod(abs(n), _tento(p))
295  if p:
296  frac = repr(f)[:-1]
297  frac = "0" * (p - len(frac)) + frac
298  else:
299  frac = ""
300  return "-"[:n<0] + \
301  repr(i)[:-1] + \
302  "." + frac
303
304  def __repr__(self):
305  return "FixedPoint" + `(str(self), self.p)`
306
307  def copy(self):
308  return _mkFP(self.n, self.p, type(self))
309
310  __copy__ = copy
311
312  def __deepcopy__(self, memo):
313  return self.copy()
314
315  def __cmp__(self, other):
316  xn, yn, p = _norm(self, other, FixedPoint=type(self))
317  return cmp(xn, yn)
318
319  def __hash__(self):
320  """ Caution! == values must have equal hashes, and a FixedPoint
321  is essentially a rational in unnormalized form. There's
322  really no choice here but to normalize it, so hash is
323  potentially expensive.
324  n, p = self.__reduce()
325
326  Obscurity: if the value is an exact integer, p will be 0 now,
327  so the hash expression reduces to hash(n). So FixedPoints
328  that happen to be exact integers hash to the same things as
329  their int or long equivalents. This is Good. But if a
330  FixedPoint happens to have a value exactly representable as
331  a float, their hashes may differ. This is a teensy bit Bad.
332  """
333  n, p = self.__reduce()
334  return hash(n) ^ hash(p)
335
336  def __nonzero__(self):
337  """ Returns true if this FixedPoint is not equal to zero"""
338  return self.n != 0
339
340  def __neg__(self):
341  return _mkFP(-self.n, self.p, type(self))
342
343  def __abs__(self):
344  """ Returns new FixedPoint containing the absolute value of this FixedPoint"""
345  if self.n >= 0:
346  return self.copy()
347  else:
348  return -self
349
351  n1, n2, p = _norm(self, other, FixedPoint=type(self))
352  # n1/10**p + n2/10**p = (n1+n2)/10**p
353  return _mkFP(n1 + n2, p, type(self))
354
356
357  def __sub__(self, other):
358  if not isinstance(other, type(self)):
359  other = type(self)(other, self.p)
361
362  def __rsub__(self, other):
363  return (-self) + other
364
365  def __mul__(self, other):
366  n1, n2, p = _norm(self, other, FixedPoint=type(self))
367  # n1/10**p * n2/10**p = (n1*n2/10**p)/10**p
368  return _mkFP(self._roundquotient(n1 * n2, _tento(p)), p, type(self))
369
370  __rmul__ = __mul__
371
372  def __div__(self, other):
373  n1, n2, p = _norm(self, other, FixedPoint=type(self))
374  if n2 == 0:
375  raise ZeroDivisionError("FixedPoint division")
376  if n2 < 0:
377  n1, n2 = -n1, -n2
378  # n1/10**p / (n2/10**p) = n1/n2 = (n1*10**p/n2)/10**p
379  return _mkFP(self._roundquotient(n1 * _tento(p), n2), p, type(self))
380
381  def __rdiv__(self, other):
382  n1, n2, p = _norm(self, other, FixedPoint=type(self))
383  return _mkFP(n2, p, FixedPoint=type(self)) / self
384
385  def __divmod__(self, other):
386  n1, n2, p = _norm(self, other, FixedPoint=type(self))
387  if n2 == 0:
388  raise ZeroDivisionError("FixedPoint modulo")
389  # floor((n1/10**p)/(n2*10**p)) = floor(n1/n2)
390  q = n1 / n2
391  # n1/10**p - q * n2/10**p = (n1 - q * n2)/10**p
392  return q, _mkFP(n1 - q * n2, p, type(self))
393
394  def __rdivmod__(self, other):
395  n1, n2, p = _norm(self, other, FixedPoint=type(self))
396  return divmod(_mkFP(n2, p), self)
397
398  def __mod__(self, other):
399  return self.__divmod__(other)
400
401  def __rmod__(self, other):
402  n1, n2, p = _norm(self, other, FixedPoint=type(self))
403  return _mkFP(n2, p, type(self)).__mod__(self)
404
405  def __float__(self):
406  """Return the floating point representation of this FixedPoint.
407  Caution! float can lose precision.
408  """
409  n, p = self.__reduce()
410  return float(n) / float(_tento(p))
411
412  def __long__(self):
413  """EJG/DF - Should this round instead?
414  Note e.g. long(-1.9) == -1L and long(1.9) == 1L in Python
415  Note that __int__ inherits whatever __long__ does,
416  and .frac() is affected too
417  """
418  answer = abs(self.n) / _tento(self.p)
419  if self.n < 0:
422
423  def __int__(self):
424  """Return integer value of FixedPoint object."""
425  return int(self.__long__())
426
427  def frac(self):
428  """Return fractional portion as a FixedPoint.
429
430  x.frac() + long(x) == x
431  """
432  return self - long(self)
433
434  def _roundquotient(self, x, y):
435  """
436  Divide x by y,
437  return the result of rounding
438  Developers may substitute their own 'round' for custom rounding
439  y must be > 0
440  """
441  assert y > 0
442  n, leftover = divmod(x, y)
443  return self.round(x, y, n, leftover)
444
445  def __reduce(self):
446  """ Return n, p s.t. self == n/10**p and n % 10 != 0"""
447  n, p = self.n, self.p
448  if n == 0:
449  p = 0
450  while p and n % 10 == 0:
451  p = p - 1
452  n = n / 10
453  return n, p
454
455 # 2002-10-04 dougfort - Default to Banker's Rounding for backward compatibility
456 FixedPoint.round = bankersRounding
457
458 # return 10L**n
459
460 def _tento(n, cache={}):
461  """Cached computation of 10**n"""
462  try:
463  return cache[n]
464  except KeyError:
465  answer = cache[n] = 10L ** n
467
468 def _norm(x, y, isinstance=isinstance, FixedPoint=FixedPoint,
469  _tento=_tento):
470  """Return xn, yn, p s.t.
471  p = max(x.p, y.p)
472  x = xn / 10**p
473  y = yn / 10**p
474
475  x must be FixedPoint to begin with; if y is not FixedPoint,
476  it inherits its precision from x.
477
478  Note that this method is called a lot, so default-arg tricks are helpful.
479  """
480  assert isinstance(x, FixedPoint)
481  if not isinstance(y, FixedPoint):
482  y = FixedPoint(y, x.p)
483  xn, yn = x.n, y.n
484  xp, yp = x.p, y.p
485  if xp > yp:
486  yn = yn * _tento(xp - yp)
487  p = xp
488  elif xp < yp:
489  xn = xn * _tento(yp - xp)
490  p = yp
491  else:
492  p = xp # same as yp
493  return xn, yn, p
494
495 def _mkFP(n, p, FixedPoint=FixedPoint):
496  """Make FixedPoint objext - Return a new FixedPoint object with the selected precision."""
497  f = FixedPoint()
498  #print '_mkFP Debug: %s, value=%s' % (type(f),n)
499  f.n = n
500  f.p = p
501  return f
502
503 # crud for parsing strings
504 import re
505
506 # There's an optional sign at the start, and an optional exponent
507 # at the end. The exponent has an optional sign and at least one
508 # digit. In between, must have either at least one digit followed
509 # by an optional fraction, or a decimal point followed by at least
510 # one digit. Yuck.
511
512 _parser = re.compile(r"""
513  \s*
514  (?P<sign>[-+])?
515  (
516  (?P<int>\d+) (\. (?P<frac>\d*))?
517  |
518  \. (?P<onlyfrac>\d+)
519  )
520  ([eE](?P<exp>[-+]? \d+))?
521  \s* \$
522 """, re.VERBOSE).match
523
524 del re
525
526
528  """Return n, p s.t. float string value == n * 10**p exactly."""
529  m = _parser(s)
530  if m is None:
531  raise ValueError("can't parse as number: " + `s`)
532
533  exp = m.group('exp')
534  if exp is None:
535  exp = 0
536  else:
537  exp = int(exp)
538
539  intpart = m.group('int')
540  if intpart is None:
541  intpart = "0"
542  fracpart = m.group('onlyfrac')
543  else:
544  fracpart = m.group('frac')
545  if fracpart is None or fracpart == "":
546  fracpart = "0"
547  assert intpart
548  assert fracpart
549
550  i, f = long(intpart), long(fracpart)
551  nfrac = len(fracpart)
552  i = i * _tento(nfrac) + f
553  exp = exp - nfrac
554
555  if m.group('sign') == "-":
556  i = -i
557
558  return i, exp
559
560 def _test():
561  """Unit testing framework"""
562  fp = FixedPoint
563  o = fp("0.1")
564  assert str(o) == "0.10"
565  t = fp("-20e-2", 5)
566  assert str(t) == "-0.20000"
567  assert t < o
568  assert o > t
569  assert min(o, t) == min(t, o) == t
570  assert max(o, t) == max(t, o) == o
571  assert o != t
572  assert --t == t
573  assert abs(t) > abs(o)
574  assert abs(o) < abs(t)
575  assert o == o and t == t
576  assert t.copy() == t
577  assert o == -t/2 == -.5 * t
578  assert abs(t) == o + o
579  assert abs(o) == o
580  assert o/t == -0.5
581  assert -(t/o) == (-t)/o == t/-o == 2
582  assert 1 + o == o + 1 == fp(" +00.000011e+5 ")
583  assert 1/o == 10
584  assert o + t == t + o == -o
585  assert 2.0 * t == t * 2 == "2" * t == o/o * 2L * t
586  assert 1 - t == -(t - 1) == fp(6L)/5
587  assert t*t == 4*o*o == o*4*o == o*o*4
588  assert fp(2) - "1" == 1
589  assert float(-1/t) == 5.0
590  for p in range(20):
591  assert 42 + fp("1e-20", p) - 42 == 0
592  assert 1/(42 + fp("1e-20", 20) - 42) == fp("100.0E18")
593  o = fp(".9995", 4)
594  assert 1 - o == fp("5e-4", 10)
595  o.set_precision(3)
596  assert o == 1
597  o = fp(".9985", 4)
598  o.set_precision(3)
599  assert o == fp(".998", 10)
600  assert o == o.frac()
601  o.set_precision(100)
602  assert o == fp(".998", 10)
603  o.set_precision(2)
604  assert o == 1
605  x = fp(1.99)
606  assert long(x) == -long(-x) == 1L
607  assert int(x) == -int(-x) == 1
608  assert x == long(x) + x.frac()
609  assert -x == long(-x) + (-x).frac()
610  assert fp(7) % 4 == 7 % fp(4) == 3
611  assert fp(-7) % 4 == -7 % fp(4) == 1
612  assert fp(-7) % -4 == -7 % fp(-4) == -3
613  assert fp(7.0) % "-4.0" == 7 % fp(-4) == -1
614  assert fp("5.5") % fp("1.1") == fp("5.5e100") % fp("1.1e100") == 0
615  assert divmod(fp("1e100"), 3) == (long(fp("1e100")/3), 1)
616
617 if __name__ == '__main__':
618  _test()
619
def bankersRounding(self, dividend, divisor, quotient, remainder)
Definition: fixedpoint.py:125
def _norm(x, y, isinstance=isinstance, FixedPoint=FixedPoint, _tento=_tento)
Definition: fixedpoint.py:469
def __init__(self, value=0, precision=DEFAULT_PRECISION)
Definition: fixedpoint.py:170
def addHalfAndChop(self, dividend, divisor, quotient, remainder)
Definition: fixedpoint.py:138
def _tento(n, cache={})
Definition: fixedpoint.py:460
def set_precision(self, precision=DEFAULT_PRECISION)
Definition: fixedpoint.py:266
def _mkFP(n, p, FixedPoint=FixedPoint)
Definition: fixedpoint.py:495

pyclearsilver
Author(s): Scott Noob Hassan
autogenerated on Mon Jun 10 2019 15:51:13