[Tutor] Need help with rewriting script to use Decimal module

[Danny Yoo]

>> 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!