Decimals to fraction strings

[Jeff Raven]

On 17 May 2000 11:56:51 GMT, Mark Jackson <mjackson at wc.eso.mc.xerox.com> wrote:
>=?ISO-8859-1?Q?Fran=E7ois_Pinard?= <pinard at iro.umontreal.ca> writes:
>> mjackson at wc.eso.mc.xerox.com (Mark Jackson) writes:
>> 
>> > > Yet your suggestion is straightforward, it might not always yield the
>> > > "best" answer, because of the constraint put on the denominator to
>> > > initially be an exponent of 10.
>> 
>> > <dumb look>
>> > Is not this same constraint applied by the problem itself, which starts
>> > with a [finite length] decimal representation?
>> > </dumb look>
>> 
>> Not necessarily.  0.6667 is well approximated by 1:3, for example, while
>> if you force the denominator to be an exponent of 10, you will obtain a
>> fraction which is not only uglier, but less precise.
>
>It's only less precise if the intended result was 1/3 rather than
>6667/10000, but if "0.6667" is what you're given there's no way to
>tell.  One could introduce an arbitrary tolerance within which a
>"simpler" rational fraction is accepted (as I see you have in the
>renamed thread) but in the end what you've shown is that the original
>poster's approach doesn't always yield the "best" answer to a
>*different* problem.
>

Well, in keeping with the comp.lang.python tradition of drifting
off-topic, there actually is a sense, due to Dirichlet, in which
1/3 is a better approximation to 0.6667.

Call an approximation p/q to a number alpha 'good' if
                        |p/q - alpha| < 1 / q^2
In simple terms, we don't just want to get close to alpha, but
we'd like to do it using as small a denominator as is reasonable.
Classically this makes a lot of sense, since the main reason you
wanted the fraction was to do calculations, and although you can
get as accurate a fraction as you'd like, there's a point where
larger fractions just make the calculations more difficult, even
if they would be more precise.

Dirichlet proved that given any number alpha and integer N, there
is always a 'good' approximation p/q such that q < N. This fraction
can be calculated directly using a rather clever argument, but
the method of continued fractions ought to give you the same thing.

Incidentally, under this approach, until you make N rather large,
Dirichlet's algorithm will consistently give 22/7 as the best
good approximation to pi.

Mathematics-is-just-a-matter-of-defining-good-ly,
Jeff Raven