Skip to content

Instantly share code, notes, and snippets.

@tchaumeny

tchaumeny/polynomial.py

Last active May 24, 2020
Embed
What would you like to do?
Polynomial type in Python
# See https://lipsum.dev/2020-05-1-pourquoi-les-polynomes/
from numbers import Number
class Polynomial:
def __init__(self, *coefficients):
self.degree = -1
self.coefficients = tuple(coefficients)
for i, coef in enumerate(self.coefficients):
if coef != 0:
self.degree = i
self.iszero = self.degree == -1
@classmethod
def from_obj(cls, obj):
if isinstance(obj, Number):
return Polynomial(obj)
elif isinstance(obj, Polynomial):
return obj
def __getitem__(self, key):
if not isinstance(key, int):
raise TypeError
if key < 0:
raise IndexError
return self.coefficients[key] if key <= self.degree else 0
def __iter__(self):
for i in range(self.degree + 1):
yield self.coefficients[i]
def __add__(self, other):
other = Polynomial.from_obj(other)
if other is None:
return NotImplemented
return Polynomial(*(
self[i] + other[i]
for i in range(max(self.degree, other.degree) + 1)
))
def __neg__(self):
return Polynomial(*(-coeff for coeff in self))
def __mul__(self, other):
other = Polynomial.from_obj(other)
if other is None:
return NotImplemented
return Polynomial(*(
sum(self[j] * other[i-j] for j in range(i + 1))
for i in range(self.degree + other.degree + 1)
))
def __pow__(self, other):
if isinstance(other, int) and other >= 0:
# We assume small exponents
# Consider implementing fast exponentiation otherwise
prod = 1
for _ in range(other):
prod *= self
return prod
return NotImplemented
def __divmod__(self, other):
other = Polynomial.from_obj(other)
if other is None:
return NotImplemented
if other.iszero:
raise ZeroDivisionError
Q, R = 0, self
while R.degree >= other.degree:
ratio = R[R.degree] * other[other.degree]**-1
monomial = Polynomial(*([0] * (R.degree - other.degree) + [ratio]))
R -= monomial * other
Q += monomial
return (Q, R)
@classmethod
def bezout_identity(cls, A, B):
U, V = 1, 0 # Invariant: A = U*A_n + V*B_n
u, v = 0, 1 # Invariant: B = u*A_n + v*B_n
while not B.iszero:
Q, R = divmod(A, B)
A, B = B, R
# A' = B, B' = A - Q B
U, V, u, v = u, v, U - Q * u, V - Q * v
mult = A[A.degree]**-1
return (mult * U, mult * V, mult * A)
def __mod__(self, other):
return self.__divmod__(other)[1]
def __radd__(self, other):
return self + other
def __sub__(self, other):
return self + (-other)
def __rsub__(self, other):
return -self + other
def __rmul__(self, other):
return self * other
def __repr__(self):
if self.iszero:
return "0"
elif self.degree == 0:
return repr(self.coefficients[0])
return str(self.coefficients[:self.degree+1])
X = Polynomial(0, 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.