Welcome, guest | Sign In | My Account | Store | Cart

This is a pure Python implementation of finite arithmetic.

Needs Python > 2.2

Python, 238 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
"""
A module for finite arithmetic.
"""


#Import generators.
from __future__ import generators


__version__ = '1.0'
__needs__ = '2.2'
__author__ = "G. Rodrigues"


#The stupidest prime-detection algorithm possible.
def IsPrime(n):
    if isinstance(n, int) and n >= 1:
        for i in range(2, n):
            if not n%i
                return 0
        return 1
    else:
        raise TypeError("%r is not an integer >= 1." % n)


#Auxiliary constructor functions.
def _ret_new(n):
    def _new(cls, m):
        if isinstance(m, int):
            return int.__new__(cls, m%n)
        else:
            raise TypeError("%r is not an integer." % m)
    return _new

def _ret_str():
    def _str(m):
        return int.__str__(m)
    return _str

def _ret_nonzero():
    def _nonzero(m):
        return int.__nonzero__(m)
    return _nonzero

def _ret_hash():
    def _hash(m):
        return int.__hash__(m)
    return _hash

def _ret_cmp():
    def _cmp(m, p):
        return int.__cmp__(m, p)
    return _cmp

def _ret_neg():
    def _neg(m):
        return m.__class__(int.__neg__(m))
    return _neg

def _ret_add():
    def _add(m, p):
        return p.__class__(int.__add__(m, p))
    return _add

def _ret_radd():
    def _radd(m, p):
        return p.__add__(m)
    return _radd

def _ret_sub():
    def _sub(m, p):
        return p.__class__(int.__sub__(m, p))
    return _sub

def _ret_rsub():
    def _rsub(m, p):
        return p.__sub__(m)
    return _rsub

def _ret_mul():
    def _mul(m, p):
        return p.__class__(int.__mul__(m, p))
    return _mul

def _ret_rmul():
    def _rmul(m, p):
        return p.__mul__(m)
    return _rmul

def _ret_div():
    def _div(m, p):
        if p:
            return p.__class__(int.__mul__(m, p.__invert__()))
        else:
            raise ZeroDivisionError("Cannot divide by zero.")
    return _div

def _ret_rdiv():
    def _rdiv(m, p):
        return p.__div__(m)
    return _rdiv

def _ret_inv(n):
    def _inv(m):
        if m:
            #Initialize variables.
            o = (m, n)
            ret = (0, 1)
            r = m % n
            q = m // n

            #Main loop.
            while 1:
                #Are we finished?
                if r:
                    o = o[-1], r
                    r = o[0] % o[1]
                    q = o[0] // o[1]
                    ret = ret[-1], ret[0] - q*ret[1]
                else:
                    return m.__class__(ret[0])
        else:
            raise ZeroDivisionError("Cannot invert 0 in any field.")
    return _inv

class Field(type):
    """The Finite Field metaclass.

    For each integer n > 1, Field(n) returns the finite ring of integers modulo n."""

    def __new__(cls, n):
        if isinstance(n, int) and n > 1:
            #Initialize methods dictionary and add the methods one by one.
            meth = {}
            
            meth['__new__'] = staticmethod(_ret_new(n))
            meth['__str__'] = _ret_str()
            meth['__nonzero__'] = _ret_nonzero()
            meth['__hash__'] = _ret_hash()
            meth['__cmp__'] = _ret_cmp()

            #Algebraic ring operations.
            meth['__neg__'] = _ret_neg()
            meth['__add__'] = _ret_add()
            meth['__radd__'] = _ret_radd()
            meth['__sub__'] = _ret_sub()
            meth['__rsub__'] = _ret_rsub()
            meth['__mul__'] = _ret_mul()
            meth['__rmul__'] = _ret_rmul()

            #If n is prime add division.
            if IsPrime(n):
                meth['__invert__'] = _ret_inv(n)
                meth['__div__'] = _ret_div()
                meth['__rdiv__'] = _ret_rdiv()

            return type.__new__(cls, "Z(%d)" % n, (int,), meth)
        else:
            raise TypeError("%s is not an integer > 1." % n)

    def __init__(self, n):
        #Generate docstring.
        self.__doc__ = "The Z(%d) finite field." % n

    def __str__(self):
        return self.__name__

    def __len__(self):
        return int(self.__name__[2:-1])

    def __iter__(self):
        for i in xrange(len(self)):
            yield self(i)


#Auxiliary functions that build the operation tables.
def cartesian_product(list1, list2):
    """Returns the cartesian product of the lists."""
    ret = []
    for i in list1:
        ret.append([(i, j) for j in list2])
    return ret

def build_table(ring, unboundmethod):
    """Displays the table for the given operation of the ring."""
    list_elems = list(ring)
    print "   " + " | ".join([str(i) for i in list_elems])

    #Main loop.    
    for lst in cartesian_product(list_elems, list_elems):
        temp = []
        for i, j in lst:
            temp.append(unboundmethod(i, j))
        print ("%s| " % lst[0][0]) + " | ".join([str(i) for i in temp])
    
def build_div(ring):
    """Displays the table for division in the ring."""
    list_elems = list(ring)
    print "   " + " | ".join([str(i) for i in list_elems])

    #Main loop.
    for lst in cartesian_product(list_elems, list_elems):
        temp = []
        for i, j in lst:
            try:
                result = i / j
            except ZeroDivisionError:
                temp.append('X')
            else:
                temp.append(result)
        print ("%s| " % lst[0][0]) + " | ".join([str(i) for i in temp])


#Some test code.
if __name__ == "__main__":
    #Construct rings.
    rings = [Field(i) for i in range(2, 10)]

    for ring in rings:
        #Test classes.
        print "This is the finite ring %s." % ring
        print "It has elements: %s." % list(ring)
        #Display tables.
        print "The addition table is:"
        build_table(ring, ring.__add__)
        print "The multiplication table is:"
        build_table(ring, ring.__mul__)
        if IsPrime(len(ring)):
            print "The division table is:"
            build_div(ring)
        else:
            print "The ring %s is not a Field." % ring
        print '\n'

    #Test silent conversions to int.
    ints = range(len(rings[-1]))
    for i, j in zip(ints, list(rings[-1])):
        print "%s + %s = %s with type %s." % (i, j, i + j, type(i + j))

I wanted to try my hand at metaclass programming and I thought that a metaclass whose instances are the finite rings of integers modulo n would be a nice, simple start. The strategy is as simple as possible: just build the necessary methods one by one using auxiliary constructors and then invoke the type constructor.

There are, of course, many things to improve - these are left for the benign reader.

Created by Gonçalo Rodrigues on Tue, 10 Sep 2002 (PSF)
Python recipes (4591)
Gonçalo Rodrigues's recipes (9)

Required Modules

  • (none specified)

Other Information and Tasks