precision problems in base conversion of rational numbers
Brian van den Broek
bvande at po-box.mcgill.ca
Tue Jul 5 21:34:47 CEST 2005
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
More information about the Python-list
mailing list