Decimals -> Fraction strings, my solution

[Michael Hudson]

=?ISO-8859-1?Q?Fran=E7ois_Pinard?= <pinard at iro.umontreal.ca> writes:

> Michael Hudson <mwh21 at cam.ac.uk> writes:
> 
> > You have the right approach (continued fractions), but you're
> > implementation is more complex than it needs to be.  [...]  Same numbers
> > as before, but rather less effort to get them, I think.
> 
> Thanks for sharing this.  Your solution computes a single continued
> fraction to the maximum precision, and then uses it to show the successive
> approximations up to that maximum precision.  Which surely is a good thing.
> My solution computes a single continued fraction, but stops the computation
> when some error tolerance has been reached.  I then called the whole thing
> many times to make experiments, resulting indeed in much total work.

The line that particularly stuck me in your code was:

        while residual != 0 and abs(value - float(self)) > tolerance:

from ContinuedFraction.__init__.  The call to "float(self)" calls
self.__float__ which calls self.eval, which computes the convergents
from scratch.  You don't really need to go through all that to bound
the error in the convergent.  Though quite how it works temporarily
escapes me...

One approach would be to estimate the error in P/Q by abs(P/Q-R/S)
where R/S is the next convergent.  I'm not sure how valid this would
be; fairly, I suspect.  It'll be an overestimate.

> In practice, I guess it is programmatically easier to decide of some
> tolerance in advance, and find a single solution from it, than to find
> all solutions up to the maximum precision possible, and later scan all
> these to decide which is one that should be retained.

I semi-deliberately avoided this issue; do you want "0.6667" to
produce 2/3 or 6667/10000?  To decide would seem to need some kind of
AI, or at least teleology.

WRT performance, the longest sequence cfrac will churn out is from
(1+sqrt(5))/2 (it's *that* number again!) and that's only 38 partial
quotients (all 1's).  It is possible to intermingle the calculation of
the partial quotients with the convergents, but it clutters the code
rather.

> Yours is surely more entertaining when used interactively! :-)

Yeah, continued fractions are fun...

Cheers,
M.

-- 
  Strangely enough  I saw just such a beast at  the grocery store
  last night. Starbucks sells Javachip. (It's ice cream, but that 
  shouldn't be an obstacle for the Java marketing people.)
                                         -- Jeremy Hylton, 29 Apr 1997