>> Dick, if your goal is to have a routine to get the fraction with the least
>> possible error (as opposed to learing how to use Decimal), have a look at
>> this recipe from the Python Cookbook:
>>
>> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52317
>
> Terry, that is truly ingenious. Is there an explication anywhere of
> exactly how it works?
Hi Dick,
On a first glance, it looks like it's doing a binary search on the Farey
series on some order. (Actually, it's not, but we'll get to that later in
this post.) Farey sequences have an entry on Wikipedia:
http://en.wikipedia.org/wiki/Farey_number
Look at the terms of F_8, for example. If you take two points with some
other point between them, say 1/5 and 2/7, notice that:
1 3 2
- < -- < -
5 12 7
If we just do the funny thing by adding the numerators and denominators
--- by taking the "mediant" --- we end up with another term in the Farey
sequence. This is very cute.
Wait. Actually, what the algorithm is doing doesn't appear to be
searching through a particular Farey sequence of order n. Instead, what
it's doing is much simpler: it appears to be just taking advanatage of the
in-betweenness property of "mediants".
http://en.wikipedia.org/wiki/Mediant_%28mathematics%29
Oh well, that still works. The algorithm seems to be misnamed, though: I
think it should really be described as "inexact to rational via mediant
approximation."
The trick that the algorithm is really a binary-search, using the
definition of "mediant" to find "midpoints". Whenever we see something
like:
####################################################################
while we haven't found the answer:
We know that the answer's somewhere between the lower and upper
bounds. (precondition)
midpoint = some calculation combining the lower and upper bounds
if the midpoint is too big:
move the upper bound
elif the midpoint is too small:
move the lower bound
else
we've found the answer
At the end of this, we guarantee our answer's still between
the lower and upper bounds. (postcondition)
####################################################################
then we should suspect a binary search. In the case of the algorithm in
the Cookbook, we can see that it follows this structure very closely.
Concretely, when they say:
if v * mediant[1] > mediant[0]: ...
we can do simple equational reasoning to see that this is really
saying:
if v > (mediant[0] / mediant[1]): ...
aka: "if the value we're looking for is bigger than the mediant, move the
lower bound up." The mediant is being represented by a 2-tuple
(numerator, denominator), so with that, you should be able to read the
case analysis off more easily.
Best of wishes!
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
