"""
Polynomial class
by Kirby Urner, Oregon Curriculum Network w/ thanks to
Brent Burley et al
First posted: May 1, 2001
Most recently modified: May 1, 2001
For background see:
http://www.mathforum.com/epigone/k12.ed.math/blunpharthah
http://mail.python.org/pipermail/edu-sig/2001-April/date.html
http://mail.python.org/pipermail/edu-sig/2001-May/date.html
"""
class Poly:
"""
Build a polynomial function object from coefficients
"""
def __init__(self, coeffs):
self.coeffs = []
if len(coeffs)==0: self.coeffs=[0]
else:
for c1 in range(len(coeffs)):
if coeffs[c1]<>0:
break
self.coeffs = coeffs[c1:]
self.degree = len(self.coeffs)-1
self.strview = self._express()
def __call__(self,x):
return eval(self.strview)
def __repr__(self):
return self.strview
def _express(self):
"""
Represent self as an algebraic expression
"""
expr = ""
exponent = self.degree
for coeff in self.coeffs:
if coeff <> 0:
if coeff>0: sign = " + "
else: sign = " - "
if abs(coeff) == 1: strcoeff = ""
else: strcoeff = str(abs(coeff))+ "*"
if exponent > 1:
expr = (expr+sign+strcoeff+"x**"+str(exponent))
elif exponent == 1:
expr = expr+sign+strcoeff+"x"
elif exponent == 0:
expr = expr+sign+str(abs(coeff))
exponent = exponent - 1
if len(expr)==0: expr = '0'
elif expr[1]=="-": expr = expr[1]+expr[3:]
else: expr = expr[3:]
return expr
def deriv(self):
"""
Return the derivative of self as another polynomial
"""
exponent = self.degree
newcoeffs = []
for coeff in self.coeffs[:-1]:
newcoeffs.append(coeff * exponent)
exponent = exponent - 1
return Poly(newcoeffs)
def __add__(self, other):
"""
Add self and other polynomial
"""
newcoeffs = []
exponent = self.degree
if type(other) == type(3):
other = Poly([other])
# Pad with 0s to make len(coeffs) >= len(other.coeffs)
if exponent < other.degree:
coeffs = [0]*(other.degree - exponent) + self.coeffs
exponent = other.degree
else:
coeffs = self.coeffs
for coeff in coeffs:
if exponent > other.degree:
newcoeffs.append(coeff)
else:
newcoeffs.append(coeff + other.coeffs[-(exponent+1)])
exponent = exponent - 1
return Poly(newcoeffs)
def __neg__(self):
"""
Return negative of polynomial
"""
newcoeffs = map(lambda x: -x, self.coeffs)
return Poly(newcoeffs)
def __sub__(self,other):
"""
Subtract a polynomial from self
"""
return self + (-other)
def __mul__(self, other):
"""
Multiply self and other polynomial
"""
if type(other) == type(3):
other = Poly([other])
newpoly = Poly([0])
for c1 in range(len(self.coeffs)):
newcoeffs = [0]*(self.degree + other.degree + 1)
for c2 in range(len(other.coeffs)):
newcoeffs[c1+c2]=self.coeffs[c1]*other.coeffs[c2]
newpoly = newpoly + Poly(newcoeffs)
return newpoly
def __rmul__(self, other):
"""
Multiply other polynomial and self
"""
return self * other
def __radd__(self, other):
"""
Add other polynomial and self
"""
return self + other
def __rsub__(self, other):
"""
Subtract other polynomial and self
"""
return other + (-self)
def __pow__(self, other):
"""
Raise self to a power
"""
if type(other) == type(3):
newpoly = Poly([1])
for i in range(other):
newpoly = newpoly * self
return newpoly
else:
raise TypeError
def compose(self, other):
"""
Compose self with other
"""
if type(other) == type(3):
other = Poly([other])
if type(other) != type(self):
raise TypeError
newpoly = Poly([0])
exponent = self.degree
for coeff in self.coeffs:
if coeff:
newpoly = newpoly + coeff * other**exponent
exponent = exponent - 1
return newpoly