Brian van den Broek wrote:
Hi all,
I guess it is more of a maths question than a programming one, but it
involves use of the decimal module, so here goes:
As a self-directed learning exercise I've been working on a script to
convert numbers to arbitrary bases. It aims to take any of whole
numbers (python ints, longs, or Decimals), rational numbers (n / m n,
m whole) and floating points (the best I can do for reals), and
convert them to any base between 2 and 36, to desired precision.
.... I've discovered empirically that I have to set getcontext.prec = 99 or
greater (i.e. x >= 1.2375) to get
0.7CF0CA7CF0CA7CF0CA7CF0CA7CF0CA7CF0CA7CF0CA7CF0CA 7CF0CA7CF0CA7CF0CA7CF0CA7CF0CA7C
(I do feel safe in assuming that is the right answer. :-)
And you are correct.
~$ repdigits 345/756 17
0.(7CF0CA)
(That's from a script I wrote a couple of years ago. For your next
self-directed learning exercise, you could get your program to produce
that output :-)
Anyhow, if you need such precise precision, perhaps you should consider
doing an exact calculation, with rational numbers.
"""Implementation of rational arithmetic."""
from __future__ import division
import decimal as _decimal
import math as _math
def _gcf(a, b):
"""Returns the greatest common factor of a and b."""
a = abs(a)
b = abs(b)
while b:
a, b = b, a % b
return a
class Rational(object):
"""
This class provides an exact representation of rational numbers.
All of the standard arithmetic operators are provided. In
mixed-type
expressions, an int or a long can be converted to a Rational
without
loss of precision, and will be done as such.
Rationals can be implicity (using binary operators) or explicity
(using float(x) or x.decimal()) converted to floats or Decimals;
this may cause a loss of precision. The reverse conversions can be
done without loss of precision, and are performed with the
from_exact_float and from_exact_decimal static methods. However,
because of rounding error in the original values, this tends to
produce "ugly" fractions. "Nicer" conversions to Rational can be
made
with approx_smallest_denominator or approx_smallest_error.
"""
def __init__(self, numerator, denominator=1):
"""Contructs the Rational object for numerator/denominator."""
if not isinstance(numerator, (int, long)):
raise TypeError('numerator must have integer type')
if not isinstance(denominator, (int, long)):
raise TypeError('denominator must have integer type')
if not denominator:
raise ZeroDivisionError('rational construction')
# Store the fraction in reduced form as _n/_d
factor = _gcf(numerator, denominator)
self._n = numerator // factor
self._d = denominator // factor
if self._d < 0:
self._n = -self._n
self._d = -self._d
def __repr__(self):
if self._d == 1:
return "Rational(%d)" % self._n
else:
return "Rational(%d, %d)" % (self._n, self._d)
def __str__(self):
if self._d == 1:
return str(self._n)
else:
return "%d/%d" % (self._n, self._d)
def __hash__(self):
try:
return hash(float(self))
except OverflowError:
return hash(long(self))
def __float__(self):
return self._n / self._d
def __int__(self):
if self._n < 0:
return -int(-self._n // self._d)
else:
return int(self._n // self._d)
def __long__(self):
return long(int(self))
def __nonzero__(self):
return bool(self._n)
def __pos__(self):
return self
def __neg__(self):
return Rational(-self._n, self._d)
def __abs__(self):
if self._n < 0:
return -self
else:
return self
def __add__(self, other):
if isinstance(other, Rational):
return Rational(self._n * other._d + self._d * other._n,
self._d * other._d)
elif isinstance(other, (int, long)):
return Rational(self._n + self._d * other, self._d)
elif isinstance(other, (float, complex)):
return float(self) + other
elif isinstance(other, _decimal.Decimal):
return self.decimal() + other
else:
return NotImplemented
__radd__ = __add__
def __sub__(self, other):
if isinstance(other, Rational):
return Rational(self._n * other._d - self._d * other._n,
self._d * other._d)
elif isinstance(other, (int, long)):
return Rational(self._n - self._d * other, self._d)
elif isinstance(other, (float, complex)):
return float(self) - other
elif isinstance(other, _decimal.Decimal):
return self.decimal() - other
else:
return NotImplemented
def __rsub__(self, other):
if isinstance(other, (int, long)):
return Rational(other * self._d - self._n, self._d)
elif isinstance(other, (float, complex)):
return other - float(self)
elif isinstance(other, _decimal.Decimal):
return other - self.decimal()
else:
return NotImplemented
def __mul__(self, other):
if isinstance(other, Rational):
return Rational(self._n * other._n, self._d * other._d)
elif isinstance(other, (int, long)):
return Rational(self._n * other, self._d)
elif isinstance(other, (float, complex)):
return float(self) * other
elif isinstance(other, _decimal.Decimal):
return self.decimal() * other
else:
return NotImplemented
__rmul__ = __mul__
def __truediv__(self, other):
if isinstance(other, Rational):
return Rational(self._n * other._d, self._d * other._n)
elif isinstance(other, (int, long)):
return Rational(self._n, self._d * other)
elif isinstance(other, (float, complex)):
return float(self) / other
elif isinstance(other, _decimal.Decimal):
return self.decimal() / other
else:
return NotImplemented
__div__ = __truediv__
def __rtruediv__(self, other):
if isinstance(other, (int, long)):
return Rational(other * self._d, self._n)
elif isinstance(other, (float, complex)):
return other / float(self)
elif isinstance(other, _decimal.Decimal):
return other / self.decimal()
else:
return NotImplemented
__rdiv__ = __rtruediv__
def __floordiv__(self, other):
truediv = self / other
if isinstance(truediv, Rational):
return truediv._n // truediv._d
else:
return truediv // 1
def __rfloordiv__(self, other):
return (other / self) // 1
def __mod__(self, other):
return self - self // other * other
def __rmod__(self, other):
return other - other // self * self
def __divmod__(self, other):
return self // other, self % other
def __cmp__(self, other):
if other == 0:
return cmp(self._n, 0)
else:
return cmp(self - other, 0)
def __pow__(self, other):
if isinstance(other, (int, long)):
if other < 0:
return Rational(self._d ** -other, self._n ** -other)
else:
return Rational(self._n ** other, self._d ** other)
else:
return float(self) ** other
def __rpow__(self, other):
return other ** float(self)
def decimal(self):
"""Return a Decimal approximation of self in the current
context."""
return _decimal.Decimal(self._n) / _decimal.Decimal(self._d)
def round(self, denominator):
"""Return self rounded to nearest multiple of 1/denominator."""
int_part, frac_part = divmod(self * denominator, 1)
round_direction = cmp(frac_part * 2, 1)
if round_direction == 0:
numerator = int_part + (int_part & 1) # round to even
elif round_direction < 0:
numerator = int_part
else:
numerator = int_part + 1
return Rational(numerator, denominator)
@staticmethod
def from_exact_float(x):
"""Returns the exact Rational equivalent of x."""
mantissa, exponent = _math.frexp(x)
mantissa = int(mantissa * 2 ** 53)
exponent -= 53
if exponent < 0:
return Rational(mantissa, 2 ** (-exponent))
else:
return Rational(mantissa * 2 ** exponent)
@staticmethod
def from_exact_decimal(x):
"""Returns the exact Rational equivalent of x."""
sign, mantissa, exponent = x.as_tuple()
sign = (1, -1)[sign]
mantissa = sign * reduce(lambda a, b: 10 * a + b, mantissa)
if exponent < 0:
return Rational(mantissa, 10 ** (-exponent))
else:
return Rational(mantissa * 10 ** exponent)
@staticmethod
def approx_smallest_denominator(x, tolerance):
"""
Returns a Rational approximation of x.
Minimizes the denominator given a constraint on the error.
x = the float or Decimal value to convert
tolerance = maximum absolute error allowed,
must be of the same type as x
"""
tolerance = abs(tolerance)
n = 1
while True:
m = int(round(x * n))
result = Rational(m, n)
if abs(result - x) < tolerance:
return result
n += 1
@staticmethod
def approx_smallest_error(x, maxDenominator):
"""
Returns a Rational approximation of x.
Minimizes the error given a constraint on the denominator.
x = the float or Decimal value to convert
maxDenominator = maximum denominator allowed
"""
result = None
minError = x
for n in xrange(1, maxDenominator + 1):
m = int(round(x * n))
r = Rational(m, n)
error = abs(r - x)
if error == 0:
return r
elif error < minError:
result = r
minError = error
return result
def divide(x, y):
"""Same as x/y, but returns a Rational if both are ints."""
if isinstance(x, (int, long)) and isinstance(y, (int, long)):
return Rational(x, y)
else:
return x / y
