80 lines
No EOL
2.6 KiB
Python
80 lines
No EOL
2.6 KiB
Python
# Polynomial class on Z or Z_p
|
|
|
|
from collections import defaultdict
|
|
|
|
class Poly:
|
|
'Polynomial class.'
|
|
def __init__(self, coeffs = None):
|
|
self.coeffs = defaultdict(int, isinstance(coeffs, int) and {0:coeffs} or coeffs or {})
|
|
self.deg = int(len(self.coeffs) and max(self.coeffs.keys()))
|
|
|
|
def __call__(self, val):
|
|
'Evaluate polynomial for a given value.'
|
|
res = 0
|
|
for i in xrange(self.deg, -1, -1):
|
|
res = res * val + self.coeffs[i]
|
|
return res
|
|
|
|
def __str__(self):
|
|
def term(coeff, expt):
|
|
if coeff == 1 and expt == 0:
|
|
return '1'
|
|
return ' * '.join(([] if coeff == 1 else [str(coeff)]) + \
|
|
([] if expt == 0 else ['X'] if expt == 1 else ['X ** %d' % expt]))
|
|
|
|
return ' + '.join(term(self.coeffs[i], i) for i in self.coeffs if self.coeffs[i] != 0)
|
|
def __repr__(self):
|
|
return str(self)
|
|
|
|
# arithmetic
|
|
def __neg__(self):
|
|
return Poly({(i, -self.coeffs[i]) for i in self.coeffs})
|
|
def __add__(self, other):
|
|
if not isinstance(other, Poly):
|
|
other = Poly(other)
|
|
res = Poly()
|
|
res.deg = max(self.deg, other.deg)
|
|
for i in xrange(res.deg+1):
|
|
res.coeffs[i] = self.coeffs[i] + other.coeffs[i]
|
|
return res
|
|
def __radd__(self, other):
|
|
if not isinstance(other, Poly):
|
|
other = Poly(other)
|
|
return other.__add__(self)
|
|
def __sub__(self, other):
|
|
if not isinstance(other, Poly):
|
|
other = Poly(other)
|
|
return self.__add__(other.__neg__())
|
|
def __rsub__(self, other):
|
|
if not isinstance(other, Poly):
|
|
other = Poly(other)
|
|
return other.__add__(self.__neg__())
|
|
|
|
def __mul__(self, other):
|
|
if not isinstance(other, Poly):
|
|
other = Poly(other)
|
|
res = Poly()
|
|
res.deg = self.deg + other.deg # consider case where other is 0
|
|
for i in xrange(res.deg+1):
|
|
for j in xrange(i+1):
|
|
res.coeffs[i] += self.coeffs[j] * other.coeffs[i - j]
|
|
return res
|
|
def __rmul__(self, other):
|
|
if not isinstance(other, Poly):
|
|
other = Poly(other)
|
|
return other.__mul__(self)
|
|
|
|
def __pow__(self, other):
|
|
if not isinstance(other, int) or other < 0:
|
|
raise ValueError("Exponent %d is not a natural number" % other)
|
|
res = Poly(1)
|
|
while other:
|
|
res *= self
|
|
other -= 1
|
|
return res
|
|
|
|
X = Poly({1:1})
|
|
|
|
def derivative(p):
|
|
'Return derivative of polynomial.'
|
|
return Poly({(i - 1, i * p.coeffs[i]) for i in p.coeffs if i != 0}) |