precision problems in base conversion of rational numbers

[Brian van den Broek]

Terry Hancock said unto the world upon 05/07/2005 11:49:
> On Monday 04 July 2005 06:11 am, Brian van den Broek wrote:
> 
>>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.

Thanks to Terry and mensanator for the replies.

To consolidate, I respond to Terry in-line and then add some response 
to mensanator at the end.


> Interesting, I'd like to see that.

I'd like it to be seen :-)  I will soon send my current version in a 
private email.


>>I'm pretty close but I know I am not handling the precision quite 
>>right. Nothing other than understanding hangs on it, but, that's 
>>enough :-)
> 
> 
> Okay.  You do understand that many numbers that can be exactly
> represented in one base cannot be in another?

Indeed. The original impetus for writing this was to substantiate my 
claim in an off-list conversation that whether a given rational had a 
repeating or terminating expansion was a function of the base of 
representation. In particular, that 1 / n in base n is 0.1


> E.g. in base 3, one-third is 0.1, but in base 10, it's a repeating
> decimal: 0.3333333....  And of course, there are infinitely many
> other examples.

The exact example I used in my off-list exchange :-)
(No "great minds" claim, sadly, as it is the natural example.)

<snip>



> Needless to say, the conventional floating point numbers in Python
> are actually stored as *binary*, which is why there is a "decimal"
> module (which is new).
> 
> If you're going to be converting between bases anyway, it probably
> makes little difference whether you are using the decimal module
> or not, of course.  You'll have the same problems the conventional
> float numbers do.

It may be a function of the algorithm I picked, but I am almost 
certain that I switched to employing Decimals after finding a 
substantial inaccuracy with a purely float logic. I will likely get 
around to switching back to floats late tonight to confirm my 
recollection.


> Getting back to your precision problem: I bet if you simply
> evaluate the error term as I have above, and then convert *that* into
> your base of choice, you will be able to tell how many places are
> correct in the conversion.
> 
> That is to, say, stop think about "number of places" and instead
> think about "representation error".  That number is a real property
> of the data which can be represented in any base.  Then you can
> convert it to number of places in the representation process.

A useful "cognitive correction", thanks :-)


> e.g. 0.000005 has 6 places behind the zero in decimal, how many
> does base3(0.000005)? --- that's the accuracy of the statement
> 
> 0.33333 base10 ~= 0.1 base3 +- base3(0.000005 base10)
> 
> Roughly, we know that 0.000005 = 10^-5 / 2.  The same term
> in base 3 will be 3^-x/2 = 10^5/2 places, which can be solved
> using logarithms, but I'll "leave that as an excercise for the reader",
> because I'm too lazy to go look it up, and I've forgotten the
> details. ;-)

Thanks. mensanator provided the actual formula for my case. I had a 
"magic number" in my code by which I multiplied my desired level of 
"number of places in the representation" to obtain the value for 
decimal.getcontext.prec.

mensanator wrote:

> The value you want for x is log(17)/log(10) =
> 1.2304489213782739285401698943283

where x was my "magic number". I've not had a chance to think it 
through yet, but I feel confident that given the formula, I'll be able 
to work out *why* that is the formula I need.

So, thanks for that, too.

mensanator also pointed out an inaccuracy in my posted example. I had 
345 / 756 represented in base 17 to 80 digits, and came up with a 
repeating expansion. It was pointed out that I should have rounded up 
the last 'digit' ['17-it' ? :-) ]. Indeed. I'd been concentrating on 
getting the conversion logic right before adding logic to deal with 
rounding and should have mentioned my result was not a rounded one, 
but merely a truncation of the infinite expansion. Thanks for the 
correction / reminder to add the logic.

> I hope this is helpful, though,
> Terry

Indeed, both your's and mensanator's. Thanks to both. Best to all,

Brian vdB