Instantly share code, notes, and snippets.

# tchaumeny/polynomial.py

Last active May 24, 2020 13:13
Show Gist options
• Save tchaumeny/9f1e9c311a52f61d82dd7d0843b2387a to your computer and use it in GitHub Desktop.
Polynomial type in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # 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)