[Edu-sig] Pythonic eToyz

[kirby urner]

>  In a first pass, we provide the code below as scaffolding, explaining
>  as we go, *not* requiring students to write it all from scratch
>  (though some might -- plus there's room for improvement (see
>  comments)).

Just a small refinement, slightly more advanced:

"""
Special to edu-sig by K. Urner:

see previous post for M class on which Mx is
based.  Just adding a better way for finding
multiplicative inverses modulo M using
Euclid's Extended Algorithm (ee).

See also:
Algorithms: A Bit of Math by Andrew Kuchling
http://pythonjournal.cognizor.com/pyj1/AMKuchling_algorithms-V1.html
Copyright (c) 1998 Andrew Kuchling
"""

from chicago2 import M

def ee(a, b):
    """Euclid extended by Alexandru Scvortov
    http://snippets.dzone.com/posts/show/4192
    """
    if b == 0:
        return a, 1, 0
    dd, xx, yy = ee(b, a % b)
    d, x, y = dd, yy, xx - (a // b) * yy
    return d, x, y

class Mx(M):

    """
    Adds extended Euclidean (ee) for finding
    multiplicative inverses
    """

    def __init__(self, val):
        self.val = val % M.modulus
        self.recip = ee(self.val, M.modulus)[1] % M.modulus

    # everything else the same as M-type