This is a pure Python implementation of finite arithmetic.
Needs Python > 2.2
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.