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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment