Decimals -> Fraction strings, my solution

[Tim Peters]

[Michael Hudson]
> ...
> 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.

The convergents are alternately larger and smaller than the value they're
converging to, so adjacent convergents bracket the target, so this is
certainly valid.  Note too that abs(P*S-Q*R) == 1 (see earlier reply), so
abs(P/Q-R/S) = 1/(Q*S) (that is, P and R are irrelevant).  Then, so long as
the sequence is beyond the trivial initial convergents, S > Q, so 1/(Q*S) <
1/Q**2.  So when you get to P/Q, you know the absolute error is < 1/Q**2.
Stopping on 1/(Q*S) is often more satisfying, though!  That is, when "the
next" partial quotient is large, S is much larger than Q, so 1/Q**2 grossly
overestimates the error.  A nice compromise is to go on until 1/Q**2 is
small enough, then compute the exact error for just the last few convergents
(going back until the exact error is too large).

> ...
> Yeah, continued fractions are fun...

Heresy!  Python is fun.

continued-fractions-are-just-an-excuse-to-use-python<wink>-ly y'rs  - tim