Package edu.princeton.cs.algs4

Class Polynomial

  • public class Polynomial
extends Object
    The Polynomial class represents a polynomial with integer coefficients. Polynomials are immutable: their values cannot be changed after they are created. It includes methods for addition, subtraction, multiplication, composition, differentiation, and evaluation.

    This computes correct results if all arithmetic performed is without overflow.

    For additional documentation, see Section 9.9 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • Polynomial

        public Polynomial​(int a,
                  int b)
        Initializes a new polynomial a x^b
        Parameters:
        a - the leading coefficient
        b - the exponent
        Throws:
        IllegalArgumentException - if b is negative

    • Method Detail

      • degree

        public int degree()
        Returns the degree of this polynomial.
        Returns:
        the degree of this polynomial, -1 for the zero polynomial.

      • plus

        public Polynomial plus​(Polynomial that)
        Returns the sum of this polynomial and the specified polynomial.
        Parameters:
        that - the other polynomial
        Returns:
        the polynomial whose value is (this(x) + that(x))

      • minus

        public Polynomial minus​(Polynomial that)
        Returns the result of subtracting the specified polynomial from this polynomial.
        Parameters:
        that - the other polynomial
        Returns:
        the polynomial whose value is (this(x) - that(x))

      • times

        public Polynomial times​(Polynomial that)
        Returns the product of this polynomial and the specified polynomial. Takes time proportional to the product of the degrees. (Faster algorithms are known, e.g., via FFT.)
        Parameters:
        that - the other polynomial
        Returns:
        the polynomial whose value is (this(x) * that(x))

      • compose

        public Polynomial compose​(Polynomial that)
        Returns the composition of this polynomial and the specified polynomial. Takes time proportional to the product of the degrees. (Faster algorithms are known, e.g., via FFT.)
        Parameters:
        that - the other polynomial
        Returns:
        the polynomial whose value is (this(that(x)))

      • equals

        public boolean equals​(Object other)
        Compares this polynomial to the specified polynomial.
        Overrides:
        equals in class Object
        Parameters:
        other - the other polynomial
        Returns:
        true if this polynomial equals other; false otherwise

      • differentiate

        public Polynomial differentiate()
        Returns the result of differentiating this polynomial.
        Returns:
        the polynomial whose value is this'(x)

      • evaluate

        public int evaluate​(int x)
        Returns the result of evaluating this polynomial at the point x.
        Parameters:
        x - the point at which to evaluate the polynomial
        Returns:
        the integer whose value is (this(x))

      • compareTo

        public int compareTo​(Polynomial that)
        Compares two polynomials by degree, breaking ties by coefficient of leading term.
        Parameters:
        that - the other point
        Returns:
        the value 0 if this polynomial is equal to the argument polynomial (precisely when equals() returns true); a negative integer if this polynomial is less than the argument polynomial; and a positive integer if this polynomial is greater than the argument point

      • toString

        public String toString()
        Return a string representation of this polynomial.
        Overrides:
        toString in class Object
        Returns:
        a string representation of this polynomial in the format 4x^5 - 3x^2 + 11x + 5

      • main

        public static void main​(String[] args)
        Unit tests the polynomial data type.
        Parameters:
        args - the command-line arguments (none)