Declaring zmod and poly obsolete. They have problems.

2 files changed, 146 insertions, 0 deletions

diff --git a/Lib/lib-old/poly.py b/Lib/lib-old/poly.py
new file mode 100644
index 0000000..57bd203
--- /dev/null
+++ b/Lib/lib-old/poly.py
@@ -0,0 +1,52 @@
+# module 'poly' -- Polynomials
+
+# A polynomial is represented by a list of coefficients, e.g.,
+# [1, 10, 5] represents 1*x**0 + 10*x**1 + 5*x**2 (or 1 + 10x + 5x**2).
+# There is no way to suppress internal zeros; trailing zeros are
+# taken out by normalize().
+
+def normalize(p): # Strip unnecessary zero coefficients
+	n = len(p)
+	while p:
+		if p[n-1]: return p[:n]
+		n = n-1
+	return []
+
+def plus(a, b):
+	if len(a) < len(b): a, b = b, a # make sure a is the longest
+	res = a[:] # make a copy
+	for i in range(len(b)):
+		res[i] = res[i] + b[i]
+	return normalize(res)
+
+def minus(a, b):
+	neg_b = map(lambda x: -x, b[:])
+	return plus(a, neg_b)
+
+def one(power, coeff): # Representation of coeff * x**power
+	res = []
+	for i in range(power): res.append(0)
+	return res + [coeff]
+
+def times(a, b):
+	res = []
+	for i in range(len(a)):
+		for j in range(len(b)):
+			res = plus(res, one(i+j, a[i]*b[j]))
+	return res
+
+def power(a, n): # Raise polynomial a to the positive integral power n
+	if n == 0: return [1]
+	if n == 1: return a
+	if n/2*2 == n:
+		b = power(a, n/2)
+		return times(b, b)
+	return times(power(a, n-1), a)
+
+def der(a): # First derivative
+	res = a[1:]
+	for i in range(len(res)):
+		res[i] = res[i] * (i+1)
+	return res
+
+# Computing a primitive function would require rational arithmetic...
diff --git a/Lib/lib-old/zmod.py b/Lib/lib-old/zmod.py
new file mode 100644
index 0000000..4f03626
--- /dev/null
+++ b/Lib/lib-old/zmod.py
@@ -0,0 +1,94 @@
+# module 'zmod'
+
+# Compute properties of mathematical "fields" formed by taking
+# Z/n (the whole numbers modulo some whole number n) and an 
+# irreducible polynomial (i.e., a polynomial with only complex zeros),
+# e.g., Z/5 and X**2 + 2.
+#
+# The field is formed by taking all possible linear combinations of
+# a set of d base vectors (where d is the degree of the polynomial).
+#
+# Note that this procedure doesn't yield a field for all combinations
+# of n and p: it may well be that some numbers have more than one
+# inverse and others have none.  This is what we check.
+#
+# Remember that a field is a ring where each element has an inverse.
+# A ring has commutative addition and multiplication, a zero and a one:
+# 0*x = x*0 = 0, 0+x = x+0 = x, 1*x = x*1 = x.  Also, the distributive
+# property holds: a*(b+c) = a*b + b*c.
+# (XXX I forget if this is an axiom or follows from the rules.)
+
+import poly
+
+
+# Example N and polynomial
+
+N = 5
+P = poly.plus(poly.one(0, 2), poly.one(2, 1)) # 2 + x**2
+
+
+# Return x modulo y.  Returns >= 0 even if x < 0.
+
+def mod(x, y):
+	return divmod(x, y)[1]
+
+
+# Normalize a polynomial modulo n and modulo p.
+
+def norm(a, n, p):
+	a = poly.modulo(a, p)
+	a = a[:]
+	for i in range(len(a)): a[i] = mod(a[i], n)
+	a = poly.normalize(a)
+	return a
+
+
+# Make a list of all n^d elements of the proposed field.
+
+def make_all(mat):
+	all = []
+	for row in mat:
+		for a in row:
+			all.append(a)
+	return all
+
+def make_elements(n, d):
+	if d == 0: return [poly.one(0, 0)]
+	sub = make_elements(n, d-1)
+	all = []
+	for a in sub:
+		for i in range(n):
+			all.append(poly.plus(a, poly.one(d-1, i)))
+	return all
+
+def make_inv(all, n, p):
+	x = poly.one(1, 1)
+	inv = []
+	for a in all:
+		inv.append(norm(poly.times(a, x), n, p))
+	return inv
+
+def checkfield(n, p):
+	all = make_elements(n, len(p)-1)
+	inv = make_inv(all, n, p)
+	all1 = all[:]
+	inv1 = inv[:]
+	all1.sort()
+	inv1.sort()
+	if all1 == inv1: print 'BINGO!'
+	else:
+		print 'Sorry:', n, p
+		print all
+		print inv
+
+def rj(s, width):
+	if type(s) <> type(''): s = `s`
+	n = len(s)
+	if n >= width: return s
+	return ' '*(width - n) + s
+
+def lj(s, width):
+	if type(s) <> type(''): s = `s`
+	n = len(s)
+	if n >= width: return s
+	return s + ' '*(width - n)