5
\$\begingroup\$

Background

After seeing a random coding interview question "write a program that can take the derivative of a polynomial", I decided to solve the problem using an OOP approach in Python. Then, I wanted to practice more, so built out a "fully" functioning Polynomial class. I am looking both for ways to improve my code and possible ways to expand this project. So far it can:

  • compute the value of a given Polynomial for any given float
  • perform field operations like addition, subtraction, & scalar multiplication
  • perform standard calculus operations like differentiation and integration
  • displays instances in a more aesthetic format:

    >>> print(Poly(-7, 0, 0, 12, 12, -2, 0))
    
    -7.0x⁶ + 12.0x³ + 12.0x² - 2.0x
    

Below is the main file and supporting script for the __str__ method

Polynomial.py (main)

from FormattingFuncs import mathformat


class Poly:
    """
    Polynomial(*coeffs) -> Polynomial

    Supports:
    - Computing real-valued polynomials for any given float/int
    - Field operations: can add, subtract, & scalar multiply polynomials
    - Calculus opeartions: can differentatiate & integrate polynomials
    """

    def __init__(self, *coeffs):
        """
        Creates a new Polynomial object by passing in floats/ints
        Passed in args correspond to coefficients in decreasing degree order
        """
        try:
            if coeffs[0] == 0 and len(coeffs) > 1:
                raise ValueError('First argument of non-constant Polynomial must be non-zero')

            self.coeffs = coeffs
            # self.coeffs = {degree: coeff for degree, coeff in enumerate(reversed(coeffs))}
            self.degree = len(coeffs) - 1
            self.isConst = (len(coeffs) == 1)  # P(x) = c
            self.isLinear = (len(coeffs) == 2)  # P(x) = ax + b

        except IndexError:
            raise IndexError(f'Oops! {type(self).__name__} requires atleast 1 float/int arg')

    def value(self, x):
        """Computes P(x=float/int)"""
        # Makes finding y-intercept a constant time process, since y-int := P(0) = const term
        if x == 0:
            val = self.coeffs[-1]
        else:
            val = sum(self.coeffs[i] * (x ** (self.degree - i)) for i in range(self.degree + 1))

        return val

    def differentiate(self):
        """Computes differentiated Polynomial object: dP/dx"""
        if self.isConst:
            coeffs = (0,)
        else:
            coeffs = (self.coeffs[i] * (self.degree - i) for i in range(self.degree))

        return Poly(*coeffs)

    def integrate(self, const=0):
        """Computes integrated Polynomial object given some integrating constant: ∫P(x)dx + c"""
        coeffs = [self.coeffs[i] / (self.degree + 1 - i) for i in range(self.degree + 1)]
        coeffs.append(const)

        return Poly(*coeffs)

    def __add__(self, other):
        """
        Polynomial(*coeffs1) + Polynomial(*coeffs2) -> Polynomial(*coeffs3)
        Polynomial(*coeffs4) + float/int -> Polynomial(*coeffs5)
        """
        try:
            # Prepends smaller degree polynomial with leading 0's
            diff = self.degree - other.degree
            leadingZeros = tuple(0 for _ in range(abs(diff)))

            if diff > 0:
                p1coeffs = self.coeffs
                p2coeffs = leadingZeros + other.coeffs
            else:
                p1coeffs = leadingZeros + self.coeffs
                p2coeffs = other.coeffs

            sumcoeffs = [sum(c) for c in zip(p1coeffs, p2coeffs)]

            # Finds index of first non-zero term
            leadingindex = -1
            for c in sumcoeffs:
                leadingindex += 1
                if c is not 0: break

            sumcoeffs = sumcoeffs[leadingindex:]

            return Poly(*sumcoeffs)

        # Handles case when adding a scalar -> shifts polynomial vertically
        except AttributeError:
            coeffs = list(self.coeffs)
            coeffs[-1] += other

            return Poly(*coeffs)

    def __radd__(self, other):
        """
        Polynomial(*coeffs1) + Polynomial(*coeffs2) -> Polynomial(*coeffs3)
        float/int + Polynomial(*coeffs4) -> Polynomial(*coeffs5)
        """
        return self + other

    def __mul__(self, scalar):
        """Polynomial(coeffs=tuple) * float/int -> Polynomial(coeffs=tuple2)"""
        if not isinstance(scalar, (float, int)):
            raise TypeError(f"'{type(scalar).__name__}' object cannot be multiplied"
                            f" - only supports scalar (float/int) multiplication")
        elif scalar == 0:
            coeffs = (0,)
        else:
            coeffs = (coeff * scalar for coeff in self.coeffs)

        return Poly(*coeffs)

    def __rmul__(self, other):
        """float/int * Polynomial(coeffs=tuple) -> Polynomial(coeffs=tuple2)"""
        return self * other

    def __sub__(self, other):
        """
        Polynomial(*coeffs1) - Polynomial(*coeffs2) -> Polynomial(*coeffs3)
        Polynomial(*coeffs4) - float/int -> Polynomial(*coeffs5)
        """
        return self + (-1 * other)

    def __rsub__(self, other):
        """
        Polynomial(*coeffs1) - Polynomial(*coeffs2) -> Polynomial(*coeffs3)
        float/int - Polynomial(*coeffs4) -> Polynomial(*coeffs5)
        """
        return other + (-1 * self)

    def __repr__(self):
        return f'{type(self).__name__}{self.coeffs}'

    def __str__(self):
        """
        Displays 'mathematical' representation of polynomial:
        i.e. Polynomial(-1, 0, 0, 0, -2, 0, 1) ->  -x⁶ - 2x² + 1
        """
        poly = ''.join(mathformat(k, self.coeffs) for k in range(self.degree + 1))

        return poly

FormattingFuncs.py

# File includes 3 support functions for Poly.__str__ method


def mathformat(term, coeffs):
    """Returns formatted term of Polynomial according to coefficient's parity and value"""
    # Booleans used for control flow to exhaust all cases
    isLeadingTerm = (term == 0)
    isConstTerm = (term == len(coeffs) - 1)

    # Handles case where polynomial is constant
    if isLeadingTerm and isConstTerm: return str(coeffs[0])

    c = float(coeffs[term])

    # Handles formatting the highest order term's coefficient
    if c == 1:
        leadingstr = ''
    elif c == -1:
        leadingstr = '-'
    else:
        leadingstr = f'{c:.03}'

    # Formats coefficient accordingly; superscripts degree unless it's the linear term
    coeff = leadingstr if isLeadingTerm else formatcoeff(term, coeffs)
    degree = f'{superscript(len(coeffs) - 1 - term)}'
    formattedterm = f'{coeff}x' + degree * (degree != '¹')

    polyformat = formatcoeff(term, coeffs) if (isConstTerm or c == 0) else formattedterm

    return polyformat


def formatcoeff(term, coeffs):
    """Transforms coefficient into appropriate str"""
    c = float(coeffs[term])

    isConstTerm = (term == len(coeffs) - 1)
    isUnitary = (abs(c) == 1)  # checks if c = 1 or -1

    coeff = '' if (isUnitary and not isConstTerm) else abs(c)

    if c > 0:
        formatted = f' + {coeff:.03}'
    elif c < 0:
        formatted = f' - {coeff:.03}'
    else:
        formatted = ''

    return formatted


def superscript(value, reverse=False):
    """
    Returns a str with any numbers superscripted: H2SO4 -> H²SO⁴
    Change reverse param to 'True' to subscript: H2SO4 -> H₂SO₄
    """
    digits = ('⁰¹²³⁴⁵⁶⁷⁸⁹', '₀₁₂₃₄₅₆₇₈₉')[reverse]
    transtable = str.maketrans("0123456789", digits)
    formatted = str(value).translate(transtable)

    return formatted
\$\endgroup\$
  • \$\begingroup\$ Numpy also has a polynomial class, located at numpy/polynomial/polynomial.py. You may want to have a look at that for further inspiration or see how they approached it. \$\endgroup\$ – Reti43 Nov 18 '17 at 1:44
1
\$\begingroup\$
  • It looks strange that you all right with constant zero polynomial (e.g. differentiate may produce one), yet you don't allow to construct one explicitly.

  • value can benefit from a Horner schedule, both in time complexity and precision. Along the same line, case x == 0 seems like a premature optimization.

  • You seem to assume that AttributeError in __add__ implies that other is of a numeric type. Unfortunately it only means that other doesn't have coeffs, and you may end up with very strangely looking coeffs[-1].

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.