[Edu-sig] egyptian fractions...

[kirby urner]

Hey Jeff, your question about controlling the turtle's screen
might have been just the ticket in my attempts to control
chaos, namely G. Lingl's chaos.py, which demonstrates
sensitivity to initial conditions is a plus if you want your
algebra to stay on the same page as itself, per equalities
that won't be equal in the real world.  I'm hoping to throw
that into site-packages on the back end at OST, along with
all those baseball stats in SQL.  It's all done with turtles
(Gregor's thing) and is brilliant, here's a link:

http://www.4dsolutions.net/ocn/python/OST/chaos.py

What I've been up to lately, besides teaching Python 24/7,
is debating with the Egyptologists whether computer science
really has an algorithm for "Egyptian Fractions".  Milo is
arguing it doesn't and the consensus seems to be with
him for now.  Fibonacci published what's today often called
"the greedy algorithm" (though that's more the genre than
the specimen) and I'm including that in Python below.

At first I though my job would be to subclass the Fraction
class in fractions, delegating the nuts and bolts to an
internal Fraction but adding this .egyptian( ) method
(really pseudo).  With that in mind, I storyboarded this
science fiction session (not yet real) which is another
way of saying I applied the "agile" principle of "test
driven development":

>>> from unitfractions import Fraction
>>> p = Fraction(5,121)
>>> type(p)
<class 'unitfractions.Fraction'>
>>> p
Fraction(5, 121)
>>> r = p.egyptian( )  # pseudo-egyptian results of Fibonacci-published
algorithm
>>> r
(Fraction(1,25), Fraction(1,757), Fraction(1,763309),
Fraction(1,873960180913), Fraction(1,1527612795642093418846225))
>>> sum(r)
Fraction(5, 121)

I later decided there was no point trying to maintain the
appearance of a whole new class, and that existing
Fraction objects should just be fed to this greedy algorithm
directly, giving a tuple of Fraction outputs.

Not much code involved.  Keep it Simple (another
"agile" precept).

>From the original thread:

"""
On second thought, I think subclassing a fractions.Fraction is overkill.  As
soon
as said subclass participates in numeric relations with its fellow Fractions
(of the ordinary kind), it's going to spawn ordinary Fractions (ancestor
class).

Maintaining an entirely new type just for this one feature is not worth the
effort,
given likely arithmetic relations with peers.

Also, I'm not a huge fan of recursion where iteration is just as
straightforward.
In the case of Fibonacci's greedy algorithm, there's like nothing to it:

"""
OST Skunkworks:
Pseudo-Egyptian Fractions
See:
http://scienceblogs.com/goodmath/2006/11/egyptian_fractions.php
http://groups.google.com/group/mathfuture/browse_thread/thread/97511940cccd5016?hl=en
"""

from fractions import Fraction
from math import ceil

def greedy(q):
    """return unit fraction expansion of fractions.Fraction q,
    using Fibonacci's 'greedy algorithm' -- non-recursive"""

    results = []

    while q > 0:
        if q.numerator == 1:
            results.append(q)
            break
        x = Fraction(1,ceil(q.denominator / q.numerator))
        q = q - x
        results.append(x)
    return tuple(results)

def _test( ):
    """
    >>> greedy(Fraction(5,121))
    (Fraction(1, 25), Fraction(1, 757), Fraction(1, 763309), Fraction(1,
873960180913), Fraction(1, 1527612795642093418846225))
    >>> greedy(Fraction(4,5))
    (Fraction(1, 2), Fraction(1, 4), Fraction(1, 20))
    >>> greedy(Fraction(9,31))
    (Fraction(1, 4), Fraction(1, 25), Fraction(1, 3100))
    >>> greedy(Fraction(21,50))
    (Fraction(1, 3), Fraction(1, 12), Fraction(1, 300))
    >>> greedy(Fraction(1023, 1024))
    (Fraction(1, 2), Fraction(1, 3), Fraction(1, 7), Fraction(1, 44),
Fraction(1, 9462), Fraction(1, 373029888))
    """
    print("testing complete")

if __name__ == "__main__":
    import doctest
    doctest.testmod()
    _test()

Note that I'm calling these "pseudo Egyptian" -- not claiming there's any
simple
algorithmic solution that'll work best in all cases.  Computer scientists
and
Milo appear to be on the same side on this one.
"""

The threads on all this may be dredged up from an obscure Google
group named mathfuture, one of the Droujkova facilities, and as
usual productive.

Kirby
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/edu-sig/attachments/20110601/6c4db569/attachment.html>