7
\$\begingroup\$

(You can find multiplication algorithms in Polynomial.java - multiplication algorithms: naïve, Karatsuba, FFT.)

Intro

This post presents the main class (Polynomial) from the Polynomial.java GitHub repository.

Basically, it's a small library for dealing with polynomials. Some supported operations are:

  • Adding two polynomials,
  • Multiplying two polynomials,
  • Derivating a polynomial,
  • Integrating a polynomial.

Code

com.github.coderodde.math.Polynomial.java:

package com.github.coderodde.math;

import static com.github.coderodde.math.Utils.powerToSuperscript;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * This class implements a polynomial represented in coefficient form.
 * 
 * @version 2.1.0 (Nov 23, 2024)
 * @since 1.0.0 (Nov 21, 2024)
 */
public final class Polynomial {
    
    /**
     * The actual array storing coefficients. {@code coefficients[i]} is the 
     * coefficient of the term with degree {@code i}, so the constant term 
     * appears at {@code coefficients[0]}.
     */
    Map<Integer, BigDecimal> coefficientMap = new HashMap<>();
    
    /**
     * The degree of this polynomial, i.e., the power of the highest-order term.
     */
    private final int degree;
     
    /**
     * Constructs a polynomial with given coefficients. The coefficients of the 
     * constant term is {@code coefficients[0]} and the coefficient of the 
     * highest degree term is {@code coefficients[coefficients.length - 1]}.
     * 
     * @param coefficients the array of coefficients.
     */
    public Polynomial(final BigDecimal... coefficients) {
        if (coefficients.length == 0) {
            // Special case: the null polynomial y = 0:
            this.coefficientMap.put(0, BigDecimal.ZERO);
            this.degree = 0;
        } else {
            final Polynomial p = 
                    getPolynomialBuilder()
                            .withBigDecimals(coefficients)
                            .build();
            
            this.degree = p.degree;
            this.coefficientMap = p.coefficientMap;
        }
    }
    
    public Polynomial(final int length) {
        this.degree = length - 1;
    }
    
    private Polynomial(final int degree,
                       final Map<Integer, BigDecimal> coefficientMap) {
        this.degree = degree;
        this.coefficientMap = coefficientMap;
    }
    
    public Polynomial shrink(final int length) {
        
        final Map<Integer, BigDecimal> newCoefficientMap = 
                new HashMap<>(length);
        
        for (final Map.Entry<Integer, BigDecimal> e 
                : coefficientMap.entrySet()) {
            
            if (e.getKey() < length) {
                newCoefficientMap.put(e.getKey(),
                                      e.getValue());
            }
        }
        
        return new Polynomial(length - 1, newCoefficientMap);
    }
    
    /**
     * Evaluates this polynomial at the point {@code x} using Horner's rule.
     * 
     * @param x the argument value for this polynomial.
     * 
     * @return the value of this polynomial at the specified {@code x}
     *         coordinate.
     */
    public BigDecimal evaluate(final BigDecimal x) {
        Objects.requireNonNull(x, "The x coordinate is null");
        BigDecimal value = getCoefficient(degree);
        
        for (int i = degree - 1; i >= 0; i--) {
            value = value.multiply(x).add(getCoefficient(i));
        }
        
        return value;
    }
    
    /**
     * Evaluates this polynomial at the point {@code x} using Horner's rule.
     * 
     * @param x the argument value for this polynomial.
     * 
     * @return the value of this polynomial at the specified {@code x}
     *         coordinate.
     */
    public BigDecimal evaluate(final double x) {
        Objects.requireNonNull(x, "The x coordinate is null");
        BigDecimal value = getCoefficient(degree);
        BigDecimal xx = BigDecimal.valueOf(x);
        
        for (int i = degree - 1; i >= 0; i--) {
            value = value.multiply(xx).add(getCoefficient(i));
        }
        
        return value;
    }
    
    /**
     * Evaluates this polynomial at the point {@code x} using Horner's rule.
     * 
     * @param x the argument value for this polynomial.
     * 
     * @return the value of this polynomial at the specified {@code x}
     *         coordinate.
     */
    public BigDecimal evaluate(final long x) {
        Objects.requireNonNull(x, "The x coordinate is null");
        BigDecimal value = getCoefficient(degree);
        BigDecimal xx = BigDecimal.valueOf(x);
        
        for (int i = degree - 1; i >= 0; i--) {
            value = value.multiply(xx).add(getCoefficient(i));
        }
        
        return value;
    }
    
    /**
     * Gets the {@code coefficientIndex}th coefficient.
     * 
     * @param coefficientIndex the index of the target coefficient.
     * 
     * @return                 the target coefficient.
     */
    public BigDecimal getCoefficient(final int coefficientIndex) {
        checkCoefficientIndex(coefficientIndex);
        
        if (!coefficientMap.containsKey(coefficientIndex)) {
            return BigDecimal.ZERO;
        }
        
        return coefficientMap.get(coefficientIndex);
    }
    
    BigDecimal getCoefficientInternal(final int coefficientIndex) {
        if (!coefficientMap.containsKey(coefficientIndex)) {
            return BigDecimal.ZERO;
        }
        
        return coefficientMap.get(coefficientIndex);
    }
    
    /**
     * Gets the number of coefficients in this polynomial.
     * 
     * @return the number of coefficients.
     */
    public int length() {
        return degree + 1;
    }
    
    /**
     * Constructs and returns an instance of {@link Polynomial} that is the 
     * summation of {@code this} polynomial and {@code othr}.
     * 
     * @param otherPolynomial the second polynomial to sum.
     * 
     * @return the sum of {@code this} and {@code othr} polynomials.
     */
    public Polynomial sum(final Polynomial otherPolynomial) {
        final int thisPolynomialLength = this.length();
        final int othrPolynomialLength = otherPolynomial.length();
        
        final int longestPolynomialLength = Math.max(thisPolynomialLength, 
                                                     othrPolynomialLength);
        
        final BigDecimal[] sumCoefficients = 
                new BigDecimal[longestPolynomialLength];
        
        // Initialize the result coefficients:
        Arrays.fill(
                sumCoefficients, 
                0, 
                sumCoefficients.length, 
                BigDecimal.ZERO);
        
        final Polynomial shortPolynomial;
        final Polynomial longPolynomial;
        
        if (thisPolynomialLength <= othrPolynomialLength) {
            shortPolynomial = this;
            longPolynomial  = otherPolynomial;
        } else {
            shortPolynomial = otherPolynomial;
            longPolynomial  = this;
        }
        
        int coefficientIndex = 0;
        
        for (; coefficientIndex < shortPolynomial.length();
               coefficientIndex++) {
            
            sumCoefficients[coefficientIndex] = 
                sumCoefficients[coefficientIndex]
                    .add(shortPolynomial.getCoefficient(coefficientIndex)
                    .add(longPolynomial .getCoefficient(coefficientIndex)));
        }
        
        for (; coefficientIndex < longPolynomial.length(); 
               coefficientIndex++) {
            
            sumCoefficients[coefficientIndex] = 
                    longPolynomial.getCoefficient(coefficientIndex);
        }
        
        return new Polynomial(sumCoefficients);
    }
    
    /**
     * Returns the scale of this polynomial. This is essentially the scale of 
     * each coefficient {@link BigDecimal} in the coefficient array.
     * 
     * @return the scale of this polynomial.
     */
    public int scale() {
        return coefficientMap.values()
                             .iterator()
                             .next()
                             .scale();
    }
    
    /**
     * Checks that all coefficients have the same scale.
     * 
     * @return {@code true} iff all the coefficients in this polynomial are 
     *         same.
     */
    public boolean isUniformlyScaled() {
        final int scale = scale();
        
        for (final BigDecimal coefficient : coefficientMap.values()) {
            if (coefficient != BigDecimal.ZERO 
                   && scale != coefficient.scale()) {
                
                return false;
            }
        }
        
        return true;
    }
    
    /**
     * Returns the degree of this polynomial.
     * 
     * @return the degree of this polynomial.
     */
    public int getDegree() {
        return degree;
    }
    
    public boolean equals(final Object o) {
        if (o == this) {
            return true;
        }
    
        if (o == null) {
            return false;
        }
        
        if (!getClass().equals(o.getClass())) {
            return false;
        }
        
        final Polynomial other = (Polynomial) o;
        
        if (getDegree() != other.getDegree()) {
            return false;
        }
        
        for (int i = 0; i < length(); i++) {
            if (!getCoefficient(i).equals(other.getCoefficient(i))) {
                return false;
            }
        }
        
        return true;
    }
    
    public boolean approximateEquals(final Polynomial other,
                                     final BigDecimal epsilon) {
        if (other == this) {
            return true;
        }
        
        if (other == null) {
            return false;
        }
        
        final int len = Math.max(this.length(), other.length());
        
        for (int i = 0; i < len; i++) {
            final BigDecimal coefficient1 = getCoefficientInternal(i);
            final BigDecimal coefficient2 = other.getCoefficientInternal(i);
            
            if (!approximatelyEquals(coefficient1,
                                     coefficient2, 
                                     epsilon)) {
                return false;
            }
        }
        
        return true;
    }

    /**
     * Copies this polynomial with the input scale applied to all coefficients 
     * in this polynomial.
     * 
     * @param scale        the next scale to use.
     * @param roundingMode the rounding mode.
     * 
     * @return a new scaled polynomial copy.
     */
    public Polynomial setScale(final int scale, 
                               final RoundingMode roundingMode) {
        
        final Map<Integer, BigDecimal> nextCoefficientMap = 
                new HashMap<>(coefficientMap.size());
        
        for (final Map.Entry<Integer, BigDecimal> entry
                : coefficientMap.entrySet()) {
            
            nextCoefficientMap.put(
                    entry.getKey(), 
                    new BigDecimal(
                            entry.getValue()
                                 .toString())
                            .setScale(scale, roundingMode));
        }
        
        return new Polynomial(degree, 
                              nextCoefficientMap);
    }
    
    public Polynomial setScale(final int scale) {
        return setScale(scale, RoundingMode.HALF_UP);
    }  
    
    /**
     * Negates this polynomial.
     * 
     * @return the negation of this polynomial.
     */
    public Polynomial negate() {
        final Map<Integer, BigDecimal> nextCoefficietMap = 
                new HashMap<>(coefficientMap.size());
        
        for (final Map.Entry<Integer, BigDecimal> entry 
                : coefficientMap.entrySet()) {
            
            nextCoefficietMap.put(entry.getKey(), entry.getValue().negate());
        }
        
        return new Polynomial(degree,
                              nextCoefficietMap);
    }
    
    /**
     * Computes and returns the derivative of this polynomial.
     * 
     * @return the derivative of this polynomial. 
     */
    public Polynomial derivate() {
        final Map<Integer, BigDecimal> nextCoefficientMap = 
                new HashMap<>(coefficientMap.size() - 1);
        
        for (int pow = 1;
                 pow < length();
                 pow++) {
            
            nextCoefficientMap.put(
                    pow - 1, 
                    getDerivateCoefficient(
                            getCoefficient(pow),
                            pow));
        }
        
        return new Polynomial(degree - 1, 
                              nextCoefficientMap);
    }
    
    /**
     * Computes and returns the integral of this polynomial. The integration 
     * constant is given as input.
     * 
     * @param integrationConstant the integration constant.
     * 
     * @return the integral of this polynomial. 
     */
    public Polynomial integrate(final BigDecimal integrationConstant) {
        Objects.requireNonNull(
                integrationConstant, 
                "The input integration constant is null");
        
        final Map<Integer, BigDecimal> nextCoefficientMap = 
                new HashMap<>(coefficientMap.size() + 1);
        
        nextCoefficientMap.put(0, integrationConstant);
        
        for (int pow = 0; 
                 pow < length(); 
                 pow++) { 
            
            nextCoefficientMap.put(
                    pow + 1,
                    integrateTerm(
                            getCoefficient(pow), 
                            pow));
        }
        
        return new Polynomial(degree + 1, nextCoefficientMap);
    }
    
    /**
     * Integrates this polynomial with zero integration constant.
     * 
     * @return the integral of this polynomial with zero integration constant. 
     */
    public Polynomial integrate() {
        return integrate(BigDecimal.ZERO);
    }
    
    Polynomial minimizeDegree(final BigDecimal zeroEpsilon) {
        int d = degree;
        
        for (; d >= 0; d--) {
            final BigDecimal coefficient = getCoefficient(d);
            
            if (!isZero(coefficient, zeroEpsilon)) {
                break;
            } else {
                // Remove the term with zero coefficient:
                coefficientMap.remove(d);
            }
        }
        
        if (d == -1) {
            return new Polynomial();
        }
        
        return new Polynomial(d, coefficientMap);
    }
    
    BigDecimal[] toCoefficientArray(final int m) {
        final BigDecimal[] coefficientArray = new BigDecimal[m];
        
        for (int i = 0; i < m; i++) {
            final BigDecimal coefficient = coefficientMap.get(i);
            
            coefficientArray[i] = 
                    coefficient == null ?
                    BigDecimal.ZERO :
                    coefficient;
        }
        
        return coefficientArray;
    }
    
    BigDecimal[] toCoefficientArray(final int m,
                                    final int n) {
        
        final BigDecimal[] coefficientArray = new BigDecimal[n - m + 1];
        
        for (int i = m; i <= n; i++) {
            final BigDecimal coefficient = coefficientMap.get(i);
            
            coefficientArray[i - m] = 
                    coefficient == null ?
                    BigDecimal.ZERO :
                    coefficient;
        }
        
        return coefficientArray;
    }
    
    /**
     * Validates the input coefficient index.
     * 
     * @param coefficientIndex the coefficient index to validate.
     */
    private void checkCoefficientIndex(final int coefficientIndex) {
        if (coefficientIndex < 0) {
            final String exceptionMessage = 
                    String.format("Invalid coefficient index: %d",
                                  coefficientIndex);
            
            throw new IndexOutOfBoundsException(exceptionMessage);
        }
        
        if (coefficientIndex > degree) {
            final String exceptionMessage = 
                String.format(
                    "Coefficient index too large: %d, must be at most %d",
                    coefficientIndex,
                    degree);
            
            throw new IndexOutOfBoundsException(exceptionMessage);
        }
    }
    
    private BigDecimal integrateTerm(final BigDecimal coefficient, 
                                     final int pow) {
        final BigDecimal powBigDecimal = BigDecimal.valueOf(pow);
        
        return coefficient.divide(
                powBigDecimal
                        .add(BigDecimal.ONE),
                         coefficient.scale(),
                         RoundingMode.CEILING);
    }
    
    private BigDecimal getDerivateCoefficient(final BigDecimal coefficient,
                                              final int pow) {
        
        return coefficient.multiply(BigDecimal.valueOf(pow));
    }
    
    @Override
    public int hashCode() {
        return coefficientMap.hashCode();
    }
    
    @Override
    public String toString() {
        if (getDegree() == 0) {
            return String.format(
                    "%f",
                    coefficientMap
                            .values()
                            .iterator()
                            .next())
                    .replace(",", ".");
        }
        
        final StringBuilder sb = new StringBuilder();
        
        boolean first = true;
        
        for (int pow = getDegree(); pow >= 0; pow--) {
            if (first) {
                first = false;
                sb.append(getCoefficient(pow))
                  .append("x");
                
                   if (pow > 1) {
                      sb.append(powerToSuperscript(pow));
                   }
            } else {
                final BigDecimal coefficient = getCoefficient(pow);
                
                if (coefficient.compareTo(BigDecimal.ZERO) > 0) {
                    sb.append(" + ")
                      .append(coefficient);
                } else if (coefficient.compareTo(BigDecimal.ZERO) < 0.0) {
                    sb.append(" - ")
                      .append(coefficient.abs());
                } else {
                    // Once here, there is no term with degree pow:
                    continue;
                }
                
                if (pow > 0) {
                    sb.append("x");
                }
                
                if (pow > 1) {
                    sb.append(powerToSuperscript(pow));
                }
            }
        }
        
        return sb.toString().replaceAll(",", ".");
    }
    
    /**
     * Makes sure that this polynomial is {@code requestedLength} coefficients 
     * long.
     * 
     * @param requestedLength the requested length in number of coefficients.
     */
    Polynomial setLength(final int requestedLength) {
        if (requestedLength <= length()) {
            return this;
        }
        
        final Map<Integer, BigDecimal> nextCoefficientMap = 
                new HashMap<>(coefficientMap);
        
        return new Polynomial(requestedLength - 1, 
                              nextCoefficientMap);
    }
    
    private static boolean approximatelyEquals(final BigDecimal bd1,
                                               final BigDecimal bd2,
                                               final BigDecimal epsilon) {
        return bd1.subtract(bd2)
                  .abs()
                  .compareTo(epsilon) < 0;
    }
    
    /**
     * Creates a new builder and returns it.
     * 
     * @return a new polynomial builder.
     */
    public static Builder getPolynomialBuilder() {
        return new Builder();
    }
    
    /**
     * The class for building sparse polynomials.
     */
    public static final class Builder {
        
        /**
         * Maps the coefficient index to its coefficient value.
         */
        private final Map<Integer, BigDecimal> 
                mapCoefficientIndexToCoefficient = new HashMap<>();
        
        /**
         * The maximum coefficient index so far.
         */
        private int maximumDegree = 0;
        
        /**
         * Adds a new coefficient to this builder.
         * 
         * @param coefficientIndex the index of the coefficient.
         * @param coefficient      the value of the coefficient.
         * 
         * @return this builder.
         */
        public Builder add(final int coefficientIndex,
                           final BigDecimal coefficient) {
            
            this.maximumDegree = 
                    Math.max(this.maximumDegree,
                             coefficientIndex);
            
            mapCoefficientIndexToCoefficient.put(coefficientIndex, 
                                                 coefficient);
            return this;
        }
        
        /**
         * Adds a new coefficient to this builder.
         * 
         * @param coefficientIndex the index of the coefficient.
         * @param coefficient      the value of the coefficient.
         * 
         * @return this builder.
         */
        public Builder add(final int coefficientIndex,
                           final double coefficient) {
            
            return add(coefficientIndex, 
                       BigDecimal.valueOf(coefficient));
        }
        
        /**
         * Adds a new coefficient to this builder.
         * 
         * @param coefficientIndex the index of the coefficient.
         * @param coefficient      the value of the coefficient.
         * 
         * @return this builder.
         */
        public Builder add(final int coefficientIndex,
                           final long coefficient) {
            
            return add(coefficientIndex, 
                       BigDecimal.valueOf(coefficient));
        }
        
        /**
         * Populates the least-significant coefficients with the given 
         * {@code long} values.
         * 
         * @param longs the coefficients to use.
         * 
         * @return this builder.
         */
        public Builder withLongs(final long... longs) {
            for (int i = 0; i < longs.length; i++) {
                add(i, longs[i]);
            }
            
            return this;
        }
        
        /**
         * Populates the least-significant coefficients with the given 
         * {@code double} values.
         * 
         * @param doubles the coefficients to use.
         * 
         * @return this builder.
         */
        public Builder withDoubles(final double... doubles) {
            for (int i = 0; i < doubles.length; i++) {
                add(i, doubles[i]);
            }
            
            return this;
        }
        
        /**
         * Populates the least-significant coefficients with the given 
         * {@code bigDecimals} values.
         * 
         * @param bigDecimals the coefficients to use.
         * 
         * @return this builder.
         */
        public Builder withBigDecimals(final BigDecimal... bigDecimals) {
            for (int i = 0; i < bigDecimals.length; i++) {
                add(i, bigDecimals[i]);
            }
            
            return this;
        }
        
        /**
         * Builds and returns the polynomial from this builder.
         * 
         * @return a polynomial.
         */
        public Polynomial build() {
            final Map<Integer, BigDecimal> nextCoefficientMap =
                    new HashMap<>(mapCoefficientIndexToCoefficient);
            
            return new Polynomial(maximumDegree, 
                                  nextCoefficientMap);
        }
    }
    
    private static boolean isZero(BigDecimal bd, 
                                  final BigDecimal zeroEpsilon) {
        if (bd.compareTo(BigDecimal.ZERO) < 0) {
            bd = bd.abs();
        }
        
        return bd.compareTo(zeroEpsilon) < 0;
    }
}

com.github.coderodde.math.PolynomialTest.java:

package com.github.coderodde.math;

import static com.github.coderodde.math.Utils.getRandomPolynomial;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;

public final class PolynomialTest {
    
    @Test
    public void evaluate1() {
        // 2x - 1
        Polynomial p1 = 
                Polynomial.getPolynomialBuilder().withLongs(-1, 2).build();
        
        BigDecimal value = p1.evaluate(BigDecimal.valueOf(3.0));
        value = value.setScale(1);
        assertEquals(BigDecimal.valueOf(5.0), value);
    }
    
    @Test
    public void evaluate2() {
        Polynomial p1 = 
                Polynomial.getPolynomialBuilder()
                          .withDoubles(-5.0, 3.0, 2.0)
                          .build(); // 2x^2 + 3x - 5
        
        BigDecimal value = p1.evaluate(BigDecimal.valueOf(4.0));
        value = value.setScale(1);
        assertEquals(BigDecimal.valueOf(39.0), value);
    }
    
    @Test
    public void getCoefficient() {
        Polynomial p = Polynomial.getPolynomialBuilder()
                                 .withLongs(1, 2, 3, 4)
                                 .build();
        
        assertEquals(BigDecimal.valueOf(1), p.getCoefficient(0));
        assertEquals(BigDecimal.valueOf(2), p.getCoefficient(1));
        assertEquals(BigDecimal.valueOf(3), p.getCoefficient(2));
        assertEquals(BigDecimal.valueOf(4), p.getCoefficient(3));
    }
    
    @Test
    public void length() {
        assertEquals(5, Polynomial.getPolynomialBuilder()
                                  .withLongs(3, -2, -1, 4, 2)
                                  .build()
                                  .length());
    }
    
    @Test
    public void sum() {
        Polynomial p1 = Polynomial.getPolynomialBuilder()
                                  .withLongs(3, -1, 2)
                                  .build();
        
        Polynomial p2 = Polynomial.getPolynomialBuilder()
                                  .withLongs(5, 4)
                                  .build();
        
        Polynomial sum = p1.sum(p2);
        
        Polynomial expected = Polynomial.getPolynomialBuilder()
                                        .withLongs(8, 3, 2)
                                        .build();
        
        assertEquals(expected, sum);
    }

    @Test
    public void getDegree() {
        assertEquals(3, Polynomial.getPolynomialBuilder()
                                  .withLongs(1, -2, 3, -4)
                                  .build()
                                  .getDegree());
    }
    
    @Test
    public void derivate() {
        Polynomial p = 
                Polynomial
                        .getPolynomialBuilder()
                        .add(0, BigDecimal.valueOf(4))
                        .add(1, BigDecimal.valueOf(-3))
                        .add(2, BigDecimal.valueOf(5))
                        .build();
        
        Polynomial d = p.derivate();
        
        assertEquals(2, d.length());
        
        Polynomial expected = 
                Polynomial
                    .getPolynomialBuilder()
                    .add(0, BigDecimal.valueOf(-3))
                    .add(1, BigDecimal.valueOf(10))
                    .build();
        
        assertEquals(expected, d);
    }
    
    @Test
    public void integrate() {
        // 6x^2 - 8x + 4
        Polynomial p = 
                Polynomial
                        .getPolynomialBuilder()
                        .add(0, BigDecimal.valueOf(4.0))
                        .add(1, BigDecimal.valueOf(8.0))
                        .add(2, BigDecimal.valueOf(6.0))
                        .build();
        
        p = p.setScale(2);
        
        // 2x^3 - 4x^2 + 4x + 16
        Polynomial i = p.integrate(BigDecimal.valueOf(16.0));
        
        i = i.setScale(2);
        
        assertEquals(4, i.length());
        
        Polynomial expected = 
                Polynomial
                    .getPolynomialBuilder()
                    .add(0, BigDecimal.valueOf(16.0))
                    .add(1, BigDecimal.valueOf(4.0))
                    .add(2, BigDecimal.valueOf(4.0))
                    .add(3, BigDecimal.valueOf(2.0))
                    .build();
        
        expected = expected.setScale(2);
        
        assertEquals(expected, i);
    }
    
    @Test
    public void integrateDerivateTwice() {
        Polynomial p =
                Polynomial.getPolynomialBuilder()
                          .withLongs(1, -2, 3)
                          .build()
                          .setScale(3);
        
        Polynomial next = p.integrate()
                           .setScale(3)
                           .derivate()
                           .setScale(3);
        
        assertEquals(p, next);
    }
    
    @Test
    public void multiplyNaive() {
        // x^2 - 2x + 3
        Polynomial p1 = 
                Polynomial
                        .getPolynomialBuilder()
                        .add(0, BigDecimal.valueOf(3).setScale(1))
                        .add(1, BigDecimal.valueOf(-2).setScale(1))
                        .add(2, BigDecimal.valueOf(1).setScale(1))
                        .build();
        // x + 4
        Polynomial p2 = 
                Polynomial
                        .getPolynomialBuilder()
                        .add(0, BigDecimal.valueOf(4).setScale(1))
                        .add(1, BigDecimal.valueOf(1).setScale(1))
                        .build();
        
        // (x^3 - 2x^2 + 3x) + (4x^2 - 8x + 12) = x^3 + 2x^2 - 5x + 12
        Polynomial product = PolynomialMultiplier.multiplyViaNaive(p1, p2); 
        
        assertEquals(3, product.getDegree());
        
        Polynomial expected = Polynomial.getPolynomialBuilder()
                                        .withLongs(12, -5, 2, 1)
                                        .build();
        
        product  = product .setScale(2);
        expected = expected.setScale(2);
        
        assertEquals(expected, product);
    }
    
    @Test
    public void multiplyKaratsuba() {
        // x^2 - 2x + 3
        Polynomial p1 = 
                Polynomial
                        .getPolynomialBuilder()
                        .add(0, BigDecimal.valueOf(3).setScale(1))
                        .add(1, BigDecimal.valueOf(-2).setScale(1))
                        .add(2, BigDecimal.valueOf(1).setScale(1))
                        .build();
        // x + 4
        Polynomial p2 = 
                Polynomial
                        .getPolynomialBuilder()
                        .add(0, BigDecimal.valueOf(4).setScale(1))
                        .add(1, BigDecimal.valueOf(1).setScale(1))
                        .build();
        
        // (x^3 - 2x^2 + 3x) + (4x^2 - 8x + 12) = x^3 + 2x^2 - 5x + 12
        Polynomial product = PolynomialMultiplier.multiplyViaKaratsuba(p1, p2); 
        
        assertEquals(3, product.getDegree());
        
        Polynomial expected = Polynomial.getPolynomialBuilder()
                                        .withLongs(12, -5, 2, 1)
                                        .build();
        
        product  = product .setScale(2);
        expected = expected.setScale(2);
        
        assertEquals(expected, product);
    }
    
    @Test
    public void multiplyFFT() {
        Polynomial a = // 2x + 3
                Polynomial
                        .getPolynomialBuilder()
                        .withLongs(3, 2)
                        .build();
        Polynomial b = // 4x - 5
                Polynomial
                        .getPolynomialBuilder()
                        .withLongs(-5, 4)
                        .build();
        
        // (2x + 3) (4x - 5) = 8x^2 - 10x + 12x - 15
        // = 8x^2 + 2x - 15
        Polynomial r = 
                PolynomialMultiplier
                        .multiplyViaFFT(a, b)
                        .setScale(2, RoundingMode.HALF_EVEN)
                        .minimizeDegree(BigDecimal.valueOf(0.01));
        
        Polynomial expected = 
                PolynomialMultiplier.multiplyViaNaive(a, b)
                          .setScale(2, RoundingMode.HALF_EVEN)
                          .minimizeDegree(BigDecimal.valueOf(0.01));
        
        assertEquals(expected, r);
    }
    
    @Test
    public void multiplyFFT2() {
        // x^2 - 2x + 3
        Polynomial p1 = 
                Polynomial
                        .getPolynomialBuilder()
                        .add(0, BigDecimal.valueOf(3).setScale(1))
                        .add(1, BigDecimal.valueOf(-2).setScale(1))
                        .add(2, BigDecimal.valueOf(1).setScale(1))
                        .build();
        // x + 4
        Polynomial p2 = 
                Polynomial
                        .getPolynomialBuilder()
                        .add(0, BigDecimal.valueOf(4).setScale(1))
                        .add(1, BigDecimal.valueOf(1).setScale(1))
                        .build();
        
        // (x^3 - 2x^2 + 3x) + (4x^2 - 8x + 12) = x^3 + 2x^2 - 5x + 12
        Polynomial product = 
                PolynomialMultiplier
                        .multiplyViaFFT(p1, p2)
                        .setScale(2, RoundingMode.HALF_UP)
                        .minimizeDegree(BigDecimal.valueOf(0.01));
        
        Polynomial expected =
                PolynomialMultiplier
                        .multiplyViaNaive(p1, p2)
                        .setScale(2, RoundingMode.HALF_UP)
                        .minimizeDegree(BigDecimal.valueOf(0.01));
        
        product  = product .setScale(2);
        expected = expected.setScale(2);
        
        assertEquals(3, product.getDegree());
        
        assertEquals(expected, product);
    }
    
    @Test
    public void negate() {
        Polynomial p = 
                Polynomial
                        .getPolynomialBuilder()
                        .withLongs(2, -3, 4, -5)
                        .build();
        
        Polynomial expected = 
                Polynomial
                        .getPolynomialBuilder()
                        .withLongs(-2, 3, -4, 5)
                        .build();
        
        assertEquals(expected, p.negate());
    }
    
    @Test
    public void testConstructEmptyPolynomial() {
        Polynomial p = new Polynomial();
        
        assertEquals(1, p.length());
        assertEquals(0, p.getDegree());
        assertEquals(BigDecimal.ZERO, p.getCoefficient(0));
        assertEquals(BigDecimal.ZERO, p.evaluate(BigDecimal.valueOf(4.0)));
        assertEquals(BigDecimal.ZERO, p.evaluate(BigDecimal.valueOf(-3.0)));
    }
    
    @Test
    public void builder() {
        final Polynomial p = Polynomial.getPolynomialBuilder()
                                       .add(10, BigDecimal.valueOf(10))
                                       .add(5000, BigDecimal.valueOf(5000))
                                       .build();
        
        assertEquals(5000, p.getDegree());  
        assertEquals(BigDecimal.valueOf(10),   p.getCoefficient(10));
        assertEquals(BigDecimal.valueOf(5000), p.getCoefficient(5000));
    }
    
    @Test
    public void emptyPolynomial() {
        Polynomial p = new Polynomial();
        
        assertEquals(1, p.length());
        assertEquals(0, p.getDegree());
        
        assertEquals(BigDecimal.ZERO, p.getCoefficient(0));
        assertEquals(BigDecimal.ZERO, p.evaluate(BigDecimal.valueOf(10.0)));
        assertEquals(BigDecimal.ZERO, p.evaluate(BigDecimal.valueOf(-7.0)));
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void throwDoubleBuilderOnNanCoefficient() {
        Polynomial.getPolynomialBuilder().add(3, Double.NaN);
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void throwDoubleBuilderOnInfiniteCoefficient() {
        Polynomial.getPolynomialBuilder()
                  .add(4, Double.NEGATIVE_INFINITY);
    }
    
    @Test
    public void getDegree2() {
        Polynomial p = 
                Polynomial.getPolynomialBuilder()
                          .add(0, BigDecimal.ZERO)
                          .add(0, BigDecimal.ZERO)
                          .add(0, BigDecimal.ZERO)
                          .build();
        
        assertEquals(0, p.getDegree());
        
        p = Polynomial.getPolynomialBuilder()
                      .add(0, BigDecimal.ZERO)
                      .add(0, BigDecimal.ZERO)
                      .build();
        
        assertEquals(0, p.getDegree());
        
        p = Polynomial.getPolynomialBuilder()
                      .add(0, BigDecimal.ZERO)
                      .build();
        
        assertEquals(0, p.getDegree());
        
        p = Polynomial.getPolynomialBuilder()
                      .build();
        
        assertEquals(0, p.getDegree());
        
        p = Polynomial.getPolynomialBuilder()
                      .add(1, BigDecimal.ONE)
                      .add(2, BigDecimal.ZERO)
                      .build();
        
        assertEquals(2, p.getDegree());
        
        p = Polynomial.getPolynomialBuilder()
                      .add(1, BigDecimal.ONE)
                      .add(2, BigDecimal.ZERO.setScale(4))
                      .add(4, BigDecimal.ZERO.setScale(1))
                      .build();
        
        assertEquals(4, p.getDegree());
        
        p = Polynomial.getPolynomialBuilder()
                      .add(1, BigDecimal.ONE)
                      .add(2, BigDecimal.ZERO.setScale(4))
                      .add(4, BigDecimal.ZERO.setScale(1))
                      .add(5, BigDecimal.valueOf(4.0).setScale(10))
                      .add(7, BigDecimal.ZERO)
                      .build();
        
        assertEquals(7, p.getDegree());
    }
    
    @Test
    public void karatsuba() {
        // -2x + 3
        final Polynomial p1 = Polynomial.getPolynomialBuilder()
                                        .add(0, BigDecimal.valueOf(3))
                                        .add(1, BigDecimal.valueOf(-2))
                                        .build()
                                        .setScale(3);
        
        // 5x - 1
        final Polynomial p2 = Polynomial.getPolynomialBuilder()
                                        .add(0, BigDecimal.valueOf(-1))
                                        .add(1, BigDecimal.valueOf(5))
                                        .build()
                                        .setScale(3);
        
        // (-2x + 3)(5x - 1) = -10x^2 + 2x + 15x - 3 = -10x^2 + 17x - 3
        final Polynomial expected = Polynomial.getPolynomialBuilder()
                                              .add(0, BigDecimal.valueOf(-3))
                                              .add(1, BigDecimal.valueOf(17))
                                              .add(2, BigDecimal.valueOf(-10))
                                              .build();
        
        final Polynomial naive = PolynomialMultiplier.multiplyViaNaive(p1, p2);
        final Polynomial karat = PolynomialMultiplier.multiplyViaKaratsuba(p1, 
                                                                           p2);
        
        assertTrue(expected.approximateEquals(naive, BigDecimal.valueOf(0.01)));
        assertTrue(expected.approximateEquals(karat, BigDecimal.valueOf(0.01)));
    }
    
    @Test
    public void karatsuba2() {
        
        // -2x^2 + 3x + 4 
        final Polynomial p1 = Polynomial.getPolynomialBuilder()
                                        .add(0, BigDecimal.valueOf(4))
                                        .add(1, BigDecimal.valueOf(3))
                                        .add(2, BigDecimal.valueOf(-2))
                                        .build();
        
        // 5x - 1
        final Polynomial p2 = Polynomial.getPolynomialBuilder()
                                        .add(0, BigDecimal.valueOf(-1))
                                        .add(1, BigDecimal.valueOf(5))
                                        .build();
        
        // (-2x^2 + 3x + 4)(5x - 1) = 
        // (-10x^3 + 15x^2 + 20x) - (-2x^2 + 3x + 4) =
        // -10x^3 + 17x^2 + 17x - 4
        final Polynomial expected = Polynomial.getPolynomialBuilder()
                                              .add(0, BigDecimal.valueOf(-4))
                                              .add(1, BigDecimal.valueOf(17))
                                              .add(2, BigDecimal.valueOf(17))
                                              .add(3, BigDecimal.valueOf(-10))
                                              .build();
        
        final Polynomial naive = PolynomialMultiplier.multiplyViaNaive(p1, p2);
        final Polynomial karat = PolynomialMultiplier.multiplyViaKaratsuba(p1, 
                                                                           p2);
        assertEquals(expected, naive);
        assertEquals(expected, karat);
    }
    
    @Test
    public void equals() {
        Polynomial p1 = Polynomial.getPolynomialBuilder().add(0, -2)
                                                         .add(1, 4)
                                                         .build()
                                                         .setScale(3);
        
        Polynomial p2 = Polynomial.getPolynomialBuilder().add(0, -2)
                                                         .add(1, 4)
                                                         .build()
                                                         .setScale(3);
        
        assertTrue(p1.equals(p2));
    }
    
    @Test
    public void bruteForceKaratsubaVsNaive() {
        final Random random = new Random(13L);
        final BigDecimal epsilon = BigDecimal.valueOf(0.01);
        
        for (int iter = 0; iter < 100; iter++) {
            final Polynomial p1 = getRandomPolynomial(random).setScale(4);
            final Polynomial p2 = getRandomPolynomial(random).setScale(4);
            
            final Polynomial product1 = 
                    PolynomialMultiplier
                            .multiplyViaNaive(p1,
                                              p2).setScale(2);
            
            final Polynomial product2 = 
                    PolynomialMultiplier
                            .multiplyViaKaratsuba(p1,
                                                  p2).setScale(2);
            
            assertTrue(product1.approximateEquals(product2, epsilon));
        }
    }
    
    @Test
    public void bruteForceNaiveVsFFT() {
        final Random random = new Random(13L);
        final BigDecimal epsilon = BigDecimal.valueOf(0.01);
        
        for (int iter = 0; iter < 100; iter++) {
            final Polynomial p1 = getRandomPolynomial(random).setScale(4);
            final Polynomial p2 = getRandomPolynomial(random).setScale(4);
            
            final Polynomial product1 = 
                    PolynomialMultiplier
                            .multiplyViaNaive(p1,
                                              p2).setScale(2);
            
            final Polynomial product2 = 
                    PolynomialMultiplier
                            .multiplyViaFFT(p1,
                                            p2)
                            .minimizeDegree(BigDecimal.valueOf(0.01))
                            .setScale(2);
            
            assertTrue(product1.approximateEquals(product2, epsilon));
        }
    }
}

Critique request

As always, I am eager to receive any commentary about my work.

\$\endgroup\$
5
  • \$\begingroup\$ It seems you switched the internal coefficients implementation, from array to Map. Why? To me, an array seems more natural and efficient \$\endgroup\$ Commented Nov 29, 2024 at 12:34
  • \$\begingroup\$ @leonbloy Wanna guess what happens when we construct a polynomial x^100000000000? \$\endgroup\$ Commented Nov 29, 2024 at 13:28
  • 2
    \$\begingroup\$ Good luck calling your constructor in that case. \$\endgroup\$ Commented Nov 29, 2024 at 16:32
  • 1
    \$\begingroup\$ If you really want to support "sparse" polynomials (few non-zero coefficients, perhaps with very high degree), so that your storage and computation is not proportional to the degree, you need to rethink your design. Elsewhere, my point above stands. \$\endgroup\$ Commented Nov 29, 2024 at 16:36
  • \$\begingroup\$ I think the constructor calling the builder which calls another constructor is un-necessary confusing \$\endgroup\$ Commented Nov 30, 2024 at 19:58

3 Answers 3

Reset to default
8
\$\begingroup\$

Polynomial

  • Broken equals() / hashCode() contract

One of the requirements of the general contract of hashCode() is:

  • If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.

But it's not the case with your implementation because of the way you treat zero coefficients.

Example:

var p1 = Polynomial.getPolynomialBuilder()
    .add(1, BigDecimal.ONE)
    .add(3, BigDecimal.ZERO)
    .build();
        
var p2 = Polynomial.getPolynomialBuilder()
    .add(1, BigDecimal.ONE)
    .add(2, BigDecimal.ZERO)
    .add(3, BigDecimal.ZERO)
    .build();

assertThat(p1).isEqualTo(p2);         // succeeds
assertThat(p1).hasSameHashCodeAs(p2); // fails

And if we try to add polynomials p1 and p2 into a HashSet both will be accepted (despite the fact that they are equal):

Set<Polynomial> set = new HashSet<>();
        
set.add(p1);
set.add(p2);
        
assertThat(set).hasSize(1); // fails Expected size: 1 but was: 2

In case if you're wondering, assertThat is coming from the fluent assertion library AssertJ, which widely used in the Java ecosystem. For instance, it's one of the testing tools included in Spring Boot Test starter dependency

Also, checking getClass() equality is not correct since you didn't prohibit to extend Polynomial (it's not final and has public constructors). You should either use instanceof check, make this class final.

  • Broken getDegree()

Please, correct me if I'm wrong, but it looks like the way you're calculating the degree of a polynomial is incorrect.

In my opinion, the following polynomial has a degree of 1:

0 * x3 + 0 * x2 + x = x

And that is the polynomial which p1 and p2 from the example above are meant to represent. But both p1.getDegree() and p2.getDegree() will yield 3, not 1.

This issue would not arise (as well as the problem with equals / hashCode) if you were ignoring zero coefficients while building a polynomial.

  • Map.getOrDefault()

You can slightly improve the readability of getCoefficient()

public BigDecimal getCoefficient(final int coefficientIndex) {
    checkCoefficientIndex(coefficientIndex);
    
    if (!coefficientMap.containsKey(coefficientIndex)) {
        return BigDecimal.ZERO;
    }
    
    return coefficientMap.get(coefficientIndex);
}

It can be simplified to:

public BigDecimal getCoefficient(final int coefficientIndex) {
    checkCoefficientIndex(coefficientIndex);
    
    return coefficientMap.getOrDefault(coefficientIndex, BigDecimal.ZERO);
}

Tests

  • Don't use numeric suffixes in test method names

Test method names such as evaluate1(), evaluate2(), getDegree(), getDegree2() does not communicate to the code reader what is the difference between these tests. Are they related to different use cases, or to the same use case?

The purpose of each test should be completely clear from the test name and an (optional) elaborate description provided through @DisplayName annotation.

Instead of writing a bloated test method repeating the same assertion over and over after processing different variations of input (or instead of writing multiple test methods for the same use case with multiple input variations), you should leverage parameterized tests.

E.g., your getDegree2() contains 7 semantically identical assertions:

@Test
public void getDegree2() {
    Polynomial p = Polynomial.getPolynomialBuilder()
                      .add(0, BigDecimal.ZERO)
                      .add(0, BigDecimal.ZERO)
                      .add(0, BigDecimal.ZERO)
                      .build();
    
    assertEquals(0, p.getDegree());
    
    // ... five more omitted for brevity
    
    p = Polynomial.getPolynomialBuilder()
                  .add(1, BigDecimal.ONE)
                  .add(2, BigDecimal.ZERO.setScale(4))
                  .add(4, BigDecimal.ZERO.setScale(1))
                  .add(5, BigDecimal.valueOf(4.0).setScale(10))
                  .add(7, BigDecimal.ZERO)
                  .build();
    
    assertEquals(7, p.getDegree());
}

You can replace it with a method containing a single assertion and annotated with @ParameterizedTest and @MethodSource (which is used to refer to a method providing the input arguments).

@ParameterizedTest
@MethodSource("degreeAndPolynomial")
@DisplayName("""
    [ getDegree ] Should return the the highest of the
     degrees of the terms of this Polynomial""")
void getDegree_ShouldReturnHighestDegreeOfPolynomial(int expectedDegree, Polynomial polynomial) {
    assertEquals(expectedDegree, polynomial.getDegree());
}

static Stream<Arguments> degreeAndPolynomial() {
    return Stream.of(
        Arguments.of(0, Polynomial.getPolynomialBuilder()
            .add(0, BigDecimal.ZERO)
            .build()
        ),
        // ... other arguments
    );
}
  • Exhaustiveness of tests

For instance, equals() method is far from being tested exhaustively. You can change the implementation to { return true } and no tests will fail.

Naming

Polynomial.getPolynomialBuilder() is unnecessarily verbose, Polynomial.builder() effectively communicates the same intent.

coefficientMap - incorporating faceless generic purpose types (such as strings and collections) usually doesn't add information about the purpose of the field. Java is a statically typed language and the Java compiler will never allow you to treat this field as something different from a Map, not to mention that any modern IDE will help you out with types.

coefficientByIndex, indexToCoeffient - are more expressive options.

\$\endgroup\$
4
\$\begingroup\$
  • equals treats new Polynomial(1, 2) and new Polynomial(1, 2, 0) (ie "2x+1" and "0x²+2x+1") as different, which to me is unexpected. Should those not be equivalent?
  • On a related note, while it makes sense why getCoefficient fails for negative inputs, it isn't obvious that it should fail for inputs larger than the polynomial's stated degree - surely such a coefficient is the same as any other missing coefficient, namely zero?
  • Storing degree independently from the coefficients seems like the two may risk becoming mismatched. Computing the degree from the coefficient map may be more robust, and can be done quite efficiently using NavigableMap.lastKey().
  • On a related note, the sum of "x²+3" and "-x²+x" is "x+3" but reports a degree of 2, which I'm not sure is right.
  • It feels like having some methods working in terms of length and others working in terms of degree could easily lead to mix-ups. I'd suggest consistently using the degree instead.
  • While I'm not sure why we care about the BigDecimals scales, I still want to point out that we aren't rigorous about it - isUniformlyScaled() acknowledges that different coefficients might have different scales, yet scale() assumes (without checking) that they all have the same scale.
\$\endgroup\$
4
\$\begingroup\$

The initialization of coefficientMap with an empty map seems unnecessary to me. The only place where this is used is when the null polynomial is initialized.

I'd remove it and instead of

this.coefficientMap.put(0, BigDecimal.ZERO);

use

this.coefficientMap = Map.of(0, BigDecimal.ZERO);

Speaking of the null polynomial, it would make sense to declare it as constant similar to BigDecimal.ZERO.

I'm not sure degree should be a separate constructor parameter or even a property. The degree of the polynomial can directly be calculated from the coefficients, just you do in minimizeDegree. Also I believe in most (if not all) places where you use the property degree it's unnecessary. In that context I don't see the point of the constructor Polynomial(final int length).

And what is the use case for the method shrink?

The three evaluate methods repeat code. The method evaluate(BigDecimal) should be called by the other two.

Also, while I get why you use degree in there, this is one of the places where it's unnecessary to me. Instead you simply could iterate over the coefficientMap entries:

return coefficientMap.entrySet().stream()
    .map(e -> x.pow(e.getKey()).multiply(e.getValue())) 
    .reduce(BigDecimal.ZERO, BigDecimal::add);

In checkCoefficientIndex I don't see why it should throw an exception in case of a too large index. I'd just have getCoefficientIndex() return ZERO. That would also make getCoefficientIndexInternal() unnecessary.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.