Mercurial > cpython-lru_cache-weakref

annotate Lib/lib-old/poly.py @ 25838:8540887bcec6 2.2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Backport of 2.183: Fix memory leak in add_subclass() found by NealN with valgrind.
author Guido van Rossum <guido@python.org>
date Fri, 18 Oct 2002 13:42:21 +0000
parents e83f676d15c2
children c3a096bfbd6b
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
9473
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
1 # module 'poly' -- Polynomials
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
2
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
3 # A polynomial is represented by a list of coefficients, e.g.,
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
4 # [1, 10, 5] represents 1*x**0 + 10*x**1 + 5*x**2 (or 1 + 10x + 5x**2).
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
5 # There is no way to suppress internal zeros; trailing zeros are
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
6 # taken out by normalize().
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
7
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
8 def normalize(p): # Strip unnecessary zero coefficients
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
9 n = len(p)
10262
e83f676d15c2 Dang. Even though this is obsolete code, somebody found a bug, and I
Guido van Rossum <guido@python.org>
parents: 9473
diff changeset
10 while n:
9473
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
11 if p[n-1]: return p[:n]
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
12 n = n-1
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
13 return []
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
14
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
15 def plus(a, b):
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
16 if len(a) < len(b): a, b = b, a # make sure a is the longest
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
17 res = a[:] # make a copy
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
18 for i in range(len(b)):
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
19 res[i] = res[i] + b[i]
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
20 return normalize(res)
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
21
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
22 def minus(a, b):
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
23 neg_b = map(lambda x: -x, b[:])
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
24 return plus(a, neg_b)
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
25
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
26 def one(power, coeff): # Representation of coeff * x**power
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
27 res = []
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
28 for i in range(power): res.append(0)
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
29 return res + [coeff]
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
30
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
31 def times(a, b):
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
32 res = []
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
33 for i in range(len(a)):
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
34 for j in range(len(b)):
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
35 res = plus(res, one(i+j, a[i]*b[j]))
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
36 return res
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
37
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
38 def power(a, n): # Raise polynomial a to the positive integral power n
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
39 if n == 0: return [1]
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
40 if n == 1: return a
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
41 if n/2*2 == n:
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
42 b = power(a, n/2)
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
43 return times(b, b)
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
44 return times(power(a, n-1), a)
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
45
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
46 def der(a): # First derivative
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
47 res = a[1:]
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
48 for i in range(len(res)):
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
49 res[i] = res[i] * (i+1)
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
50 return res
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
51
3f717342f0a3 Declaring zmod and poly obsolete. They have problems.
Guido van Rossum <guido@python.org>
parents:
diff changeset
52 # Computing a primitive function would require rational arithmetic...