From e0fbe1c26de5fde580912b80d3667ade05bbba5f Mon Sep 17 00:00:00 2001 From: Guido van Rossum Date: Mon, 2 Nov 1998 15:38:51 +0000 Subject: Declaring zmod and poly obsolete. They have problems. --- Lib/lib-old/poly.py | 52 +++++++++++++++++++++++++++++ Lib/lib-old/zmod.py | 94 +++++++++++++++++++++++++++++++++++++++++++++++++++++ Lib/poly.py | 52 ----------------------------- Lib/zmod.py | 94 ----------------------------------------------------- 4 files changed, 146 insertions(+), 146 deletions(-) create mode 100644 Lib/lib-old/poly.py create mode 100644 Lib/lib-old/zmod.py delete mode 100644 Lib/poly.py delete mode 100644 Lib/zmod.py 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) diff --git a/Lib/poly.py b/Lib/poly.py deleted file mode 100644 index 57bd203..0000000 --- a/Lib/poly.py +++ /dev/null @@ -1,52 +0,0 @@ -# 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/zmod.py b/Lib/zmod.py deleted file mode 100644 index 4f03626..0000000 --- a/Lib/zmod.py +++ /dev/null @@ -1,94 +0,0 @@ -# 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) -- cgit v0.12