precision problems in base conversion of rational numbers

[Raymond Hettinger]

> > For a simple example, convert both 10247448370872321 and
> > 10247448370872319 from base ten to 4 digits of hex.  The calculations
> > need to be carried out to 15 places of hex (or 17 places of decimal)
> > just to determine whether the fourth hex digit is a 7 or 8:
> >
> >     >>> hex(10247448370872321)
> >     '0x24680000000001L'
> >     >>> hex(10247448370872319)
> >     '0x2467ffffffffffL'
>
> I don't understand your simple example.
>
> log(10)/log(16) = 0.83048202372184058696757985737235
>
> Multiplying by the number of decimal digits (17) gives
>
> 14.11819440327128997844885757533
>
> Rounding up to an integer digit count, we need need 15 hex digits.
> Isn't that exactly what you concluded? Where does that 4 hex digit
> stuff come from?

It is part of the OP's problem spec.  Given a number x (which may be a
decimal, float, long integer, or rational), a base b, and a desired
precision p, compute the conversion to p-digits:

  >>> convert(x=10247448370872319L, b=16, p=4)
  '24680000000000'

He wanted to know what decimal precision he needed to set to make the
conversion accurate to the last place.  The required precision for
intermediate calculations depends on how close x is to a representable
value in the target base.  The 16 digits are not known a priori since x
may be a rational, float, or decimal.  For instance, an internal
precision of 17 digits would also be needed for other nearby values of
x:

  >>> convert(x=Decimal("10247448370872319.000000001", b=16, p=4)
  '24680000000000'

The number 17 does not just pop-out of a simple logarithm.  How many
internal digits of precision do you need for convert(math.pi, b=16,
p=5)?  If the result falls closely between reprentable values, the OP
may need to set his "magic number" to something larger than you would
have predicted.

If you want insight into why the OP's problem statement is deeper than
it appears, then ponder the mystery of why the following returns False:

  >>> x = 554459760520464551937111727196883414687442277344893869152167
  >>> float(x) == float(str(x))
  False

Hint, the two different underlying routines are trying to compute,
convert(x, b=2, p=53), without the benefit of arbitrary precision
arithmetic.


Raymond