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 | import operator
Number = (int, float, long, complex)
#sum_v = lambda *a: sum(a)
class SimplePolynomial(object):
def __init__(self, terms=[0,1]):
try:
while terms[-1] == 0:
del terms[-1]
except IndexError:
pass
self.terms = terms
def __add__(self, other):
if len(self.terms) == 0:
return other
if isinstance(other, Number):
terms = self.terms[:]
terms[0] += other
elif len(self.terms) <= len(other.terms):
terms = self.terms[:]
terms.extend([0]*(len(other.terms) - len(self.terms)))
terms = map(operator.add, other.terms, terms)
else:
return other + self
return SimplePolynomial(terms)
def __radd__(self, other):
"addition is commutative, so we can just switch the arguments"
return self + other
def __neg__(self):
return SimplePolynomial([-c for c in self.terms])
def __sub__(self, other):
return self + -other
def __rsub__(self, other):
return -self + other
def __mul__(self, other):
if isinstance(other, Number):
return SimplePolynomial([other*c for c in self.terms])
terms = [0]*(len(self.terms)+len(other.terms))
for i1, c1 in enumerate(self.terms):
for i2, c2 in enumerate(other.terms):
terms[i1+i2] += c1*c2
return SimplePolynomial(terms)
def __rmul__(self, other):
"multiplication is commutative, so we can just switch the arguments"
return self * other
def copy(self):
return SimplePolynomial(self.terms[:])
def __pow__(self, exponent):
"uses the Russian Peasant Multiplication algorithm"
if not isinstance(exponent, int):
raise NotImplementedError
tmp = self.copy()
result = SimplePolynomial([1])
while exponent > 0:
if exponent & 1:
result *= tmp
tmp *= tmp
exponent >>= 1
return result
def __str__(self):
"needs some work, but adequate"
l = len(self.terms)
if l == 0:
return '0'
if l == 1:
return str(self.terms[0])
result = []
for i, c in reversed(list(enumerate(self.terms))):
if c == 0:
continue
if c < 0:
result.append('-')
c = - c
else:
result.append('+')
if c == 1:
if i == 0:
result.append('1')
elif i == 1:
result.append('X')
else:
result.append('X**%g' % i)
else:
if i == 0:
result.append('%g' % c)
elif i == 1:
result.append('%g*X' % c)
else:
result.append('%g*X**%d' % (c, i))
if len(result) == 0:
return '0'
if result[0] == '-':
result[1] = '-'+result[1]
del result[0]
return ' '.join(result)
def __call__(self, x):
"evaluate the polynomial for the given value using the Horner scheme"
result = 0
for c in reversed(self.terms):
result = result*x + c
return result
def derivative(self):
terms = [i*c for i, c in enumerate(self.terms)]
return SimplePolynomial(terms[1:])
def integrate(self, const=0):
terms = [const]
terms.extend([c/float(i+1) for i, c in enumerate(self.terms)])
return SimplePolynomial(terms)
if __name__ == '__main__':
print 'testing...'
x = SimplePolynomial()
for expression in 'x', 'x+1', '1+x', 'x+x', '-x', 'x-1', '1-x', '2*x', 'x*2', 'x*x', '(x+1)*(x-1)':
print expression, '\t=>', eval(expression)
print 'testing exponentiation...'
for i in range(4):
print '(x+1)**%d' % i, '\t=>', (x+1)**i
|
Download
Copy to clipboard
Very nice recipe!!! Just a few notes:
you might replace
sum_vbyoperator.addI noticed you very carefully avoided sharing
self.termsbetween instances, but forgot to do so incopy().also, complex coefficients appear to be supported, but
integral()usesfloat(c)and may fail in such cases.c/float(i+1)is enough to avoid integer division (or usefrom __future__ import division)To evaluate the polynomial, Ruffini's Rule usually gives better results (but is slightly more complex than your very straightforward code)
also, itertools seems to be a leftover from earlier attempts...
Thanks for the feedback. I've implemented all of your suggestions. In the case of
copy(), I'd convinced myself that the sharing was harmless, but it's probably better to be safe than sorry. Thefloat(c)was left over from earlier debugging; after integration my coefficients all appeared to be integers. (It turned out that I was using'%d'in__str__().) At some point I'll probably add synthetic division.