On Wed, 3 Jan 2007, Dick Moores wrote:
> At 01:17 PM 1/2/2007, Terry Carroll wrote:
>
> > http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52317
>
> Terry, that is truly ingenious. Is there an explication anywhere of
> exactly how it works?
There is in the printed copy of the Python Cookbook. I happened to have
read it last week, which is the only reason I knew about it. I don't have
the book handy, but here's what I remember of it.
It's based on the concept of the Farey sequence of fractions. I may
explain it imperfectly, but it's basically the sequence of fractions with
integer denominators and numerators, each reduced to the lowest common
denominator, and then arranged in numerically ascending order. The
sequence has an order N, where N is the highest integer used in the
denominator.
It's easier to show an example. Here's the Farey sequence for order 4;
I'll include a decimal approximation to show the basis for the ordering:
0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1
0.0 0.25 0.33 0.50 0.67 0.75 1.00
It's been observed (by a guy named Farey, hence the name) that, for any
subsequence of three consecutive fractions in the sequence, if expressed
as A/B, C/D, E/F; then C/D = (A+E)/(B+F).
For example, in the above seqence, take the three-fraction subsequence
{1/2, 2/3, 3/4}. In this, A=1, B=2, C=2, D=3, E=3, F=4, so:
(A+E)/(B+F) = (1+3)/(2+4) = 4/6 = 2/3 = C/D.
The inner fraction (C/D) is called the mediant.
If I understand the Python algorithm correctly, it takes advantage of this
process by essentially constructing a Farey sequence of order 1 (which is
essentially {0/1, 1/1}, or {0, 1}), and then calculating the mediant
between those two points, thereby constructing a subsequence of order 2;
then another mediant between that mediant and one of its neighbors (which
neighbor is chose by considering whether the decimal fraction you seek to
approximate is greater than or less than the mediant), and then doing this
continuously, calculating subsquences of orders 3, 4, etc, until it
reaches the desired precision.
I just checked, and (big surprise) Wikipedia has an article on the Farey
sequence:
http://en.wikipedia.org/wiki/Farey_number
There's apparently more to it than I described above. They give the same
formula I use, but where I use A, B, C, D, E, F, they use A, B, P, Q, C,
D, respectively.
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
