

 This page uses content from Wikipedia. The original article was at Polynomial long division. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree.
Let us suppose a polynomial is represented by a vector, 



x


{\displaystyle x}

 (i.e., an ordered collection of coefficients) so that the 



i


{\displaystyle i}

th element keeps the coefficient of 




x

i




{\displaystyle x^{i}}

, and the multiplication by a monomial is a shift of the vector's elements "towards right" (injecting ones from left) followed by a multiplication of each element by the coefficient of the monomial.

Then a pseudocode for the polynomial long division using the conventions described above could be:

degree(P):
  return the index of the last non-zero element of P;
         if all elements are 0, return -∞

polynomial_long_division(N, D) returns (q, r):
  // N, D, q, r are vectors
  if degree(D) < 0 then error
  q ← 0
  while degree(N) ≥ degree(D)
    d ← D shifted right by (degree(N) - degree(D))
    q(degree(N) - degree(D)) ← N(degree(N)) / d(degree(d))
    // by construction, degree(d) = degree(N) of course
    d ← d * q(degree(N) - degree(D))
    N ← N - d
  endwhile
  r ← N
  return (q, r)

Note: vector * scalar multiplies each element of the vector by the scalar; vectorA - vectorB subtracts each element of the vectorB from the element of the vectorA with "the same index". The vectors in the pseudocode are zero-based.

 Error handling (for allocations or for wrong inputs) is not mandatory.
 Conventions can be different; in particular, note that if the first coefficient in the vector is the highest power of x for the polynomial represented by the vector, then the algorithm becomes simpler.

Example for clarification


This example is from Wikipedia, but changed to show how the given pseudocode works.

      0    1    2    3
   ----------------------
N:  -42    0  -12    1        degree = 3
D:   -3    1    0    0        degree = 1

   d(N) - d(D) = 2, so let's shift D towards right by 2:

N:  -42    0  -12    1
d:    0    0   -3    1

   N(3)/d(3) = 1, so d is unchanged. Now remember that "shifting by 2"
   is like multiplying by x2, and the final multiplication
   (here by 1) is the coefficient of this monomial. Let's store this
   into q:
                               0     1     2
                              ---------------
                          q:   0     0     1

   now compute N - d, and let it be the "new" N, and let's loop

N:  -42    0   -9    0        degree = 2
D:   -3    1    0    0        degree = 1

   d(N) - d(D) = 1, right shift D by 1 and let it be d

N:  -42    0   -9    0
d:    0   -3    1    0        * -9/1 = -9

                          q:   0    -9     1

d:    0   27   -9    0        

   N ← N - d

N:  -42  -27    0    0        degree = 1
D:   -3    1    0    0        degree = 1

   looping again... d(N)-d(D)=0, so no shift is needed; we
   multiply D by -27 (= -27/1) storing the result in d, then

                          q:  -27   -9     1

   and

N:  -42  -27    0    0        -
d:   81  -27    0    0        =
N: -123    0    0    0        (last N)

    d(N) < d(D), so now r ← N, and the result is:

       0   1  2
   -------------
q:   -27  -9  1   →  x2 - 9x - 27
r:  -123   0  0   →          -123



Related task

   Polynomial derivative


 
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
 
public class PolynomialLongDivision {
 
    public static void main(String[] args) {
        RunDivideTest(new Polynomial(1, 3, -12, 2, -42, 0), new Polynomial(1, 1, -3, 0));
        RunDivideTest(new Polynomial(5, 2, 4, 1, 1, 0), new Polynomial(2, 1, 3, 0));
        RunDivideTest(new Polynomial(5, 10, 4, 7, 1, 0), new Polynomial(2, 4, 2, 2, 3, 0));
        RunDivideTest(new Polynomial(2,7,-24,6,2,5,-108,4,3,3,-120,2,-126,0), new Polynomial(2, 4, 2, 2, 3, 0));
    }
 
    private static void RunDivideTest(Polynomial p1, Polynomial p2) {
        Polynomial[] result = p1.divide(p2);
        System.out.printf("Compute: (%s) / (%s) = %s reminder %s%n", p1, p2, result[0], result[1]);
        System.out.printf("Test:    (%s) * (%s) + (%s) = %s%n%n", result[0], p2, result[1], result[0].multiply(p2).add(result[1]));
    }
 
    private static final class Polynomial {
 
        private List<Term> polynomialTerms;
 
        //  Format - coeff, exp, coeff, exp, (repeating in pairs) . . .
        public Polynomial(long ... values) {
            if ( values.length % 2 != 0 ) {
                throw new IllegalArgumentException("ERROR 102:  Polynomial constructor.  Length must be even.  Length = " + values.length);
            }
            polynomialTerms = new ArrayList<>();
            for ( int i = 0 ; i < values.length ; i += 2 ) {
                polynomialTerms.add(new Term(BigInteger.valueOf(values[i]), values[i+1]));
            }
            Collections.sort(polynomialTerms, new TermSorter());
        }
 
        public Polynomial() {
            //  zero
            polynomialTerms = new ArrayList<>();
            polynomialTerms.add(new Term(BigInteger.ZERO, 0));
        }
 
        private Polynomial(List<Term> termList) {
            if ( termList.size() != 0 ) {
                //  Remove zero terms if needed
                for ( int i = 0 ; i < termList.size() ; i++ ) {
                    if ( termList.get(i).coefficient.compareTo(Integer.ZERO_INT) == 0 ) {
                        termList.remove(i);
                    }
                }
            }
            if ( termList.size() == 0 ) {
                //  zero
                termList.add(new Term(BigInteger.ZERO,0));
            }
            polynomialTerms = termList;
            Collections.sort(polynomialTerms, new TermSorter());
        }
 
        public Polynomial[] divide(Polynomial v) {
            Polynomial q = new Polynomial();
            Polynomial r = this;
            Number lcv = v.leadingCoefficient();
            long dv = v.degree();
            while ( r.degree() >= dv ) {
                Number lcr = r.leadingCoefficient();
                Number s = lcr.divide(lcv);
                Term term = new Term(s, r.degree() - dv);
                q = q.add(term);
                r = r.add(v.multiply(term.negate()));
            }
            return new Polynomial[] {q, r};
        }
 
        public Polynomial add(Polynomial polynomial) {
            List<Term> termList = new ArrayList<>();
            int thisCount = polynomialTerms.size();
            int polyCount = polynomial.polynomialTerms.size();
            while ( thisCount > 0 || polyCount > 0 ) {
                Term thisTerm = thisCount == 0 ? null : polynomialTerms.get(thisCount-1);
                Term polyTerm = polyCount == 0 ? null : polynomial.polynomialTerms.get(polyCount-1);
                if ( thisTerm == null ) {
                    termList.add(polyTerm);
                    polyCount--;
                }
                else if (polyTerm == null ) {
                    termList.add(thisTerm);
                    thisCount--;
                }
                else if ( thisTerm.degree() == polyTerm.degree() ) {
                    Term t = thisTerm.add(polyTerm);
                    if ( t.coefficient.compareTo(Integer.ZERO_INT) != 0 ) {
                        termList.add(t);
                    }
                    thisCount--;
                    polyCount--;
                }
                else if ( thisTerm.degree() < polyTerm.degree() ) {
                    termList.add(thisTerm);
                    thisCount--;
                }
                else {
                    termList.add(polyTerm);
                    polyCount--;
                }
            }
            return new Polynomial(termList);
        }
 
        public Polynomial add(Term term) {
            List<Term> termList = new ArrayList<>();
            boolean added = false;
            for ( int index = 0 ; index < polynomialTerms.size() ; index++ ) {
                Term currentTerm = polynomialTerms.get(index);
                if ( currentTerm.exponent == term.exponent ) {
                    added = true;
                    if ( currentTerm.coefficient.add(term.coefficient).compareTo(Integer.ZERO_INT) != 0 ) {
                        termList.add(currentTerm.add(term));
                    }
                }
                else {
                    termList.add(currentTerm);
                }
            }
            if ( ! added ) {
                termList.add(term);
            }
            return new Polynomial(termList);
        }
 
        public Polynomial multiply(Polynomial polynomial) {
            List<Term> termList = new ArrayList<>();
            for ( int i = 0 ; i < polynomialTerms.size() ; i++ ) {
                Term ci = polynomialTerms.get(i);
                for ( int j = 0 ; j < polynomial.polynomialTerms.size() ; j++ ) {
                    Term cj = polynomial.polynomialTerms.get(j);
                    Term currentTerm = ci.multiply(cj);
                    boolean added = false;
                    for ( int k = 0 ; k < termList.size() ; k++ ) {
                        if ( currentTerm.exponent == termList.get(k).exponent ) {
                            added = true;
                            Term t = termList.remove(k).add(currentTerm);
                            if ( t.coefficient.compareTo(Integer.ZERO_INT) != 0 ) {
                                termList.add(t);
                            }
                            break;
                        }
                    }
                    if ( ! added ) {
                        termList.add(currentTerm);
                    }
                }
            }
            return new Polynomial(termList);
        }
 
        public Polynomial multiply(Term term) {
            List<Term> termList = new ArrayList<>();
            for ( int index = 0 ; index < polynomialTerms.size() ; index++ ) {
                Term currentTerm = polynomialTerms.get(index);
                termList.add(currentTerm.multiply(term));
            }
            return new Polynomial(termList);
        }
 
        public Number leadingCoefficient() {
            return polynomialTerms.get(0).coefficient;
        }
 
        public long degree() {
            return polynomialTerms.get(0).exponent;
        }
 
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            boolean first = true;
            for ( Term term : polynomialTerms ) {
                if ( first ) {
                    sb.append(term);
                    first = false;
                }
                else {
                    sb.append(" ");
                    if ( term.coefficient.compareTo(Integer.ZERO_INT) > 0 ) {
                        sb.append("+ ");
                        sb.append(term);
                    }
                    else {
                        sb.append("- ");
                        sb.append(term.negate());
                    }
                }
            }
            return sb.toString();
        }
    }
 
    private static final class TermSorter implements Comparator<Term> {
        @Override
        public int compare(Term o1, Term o2) {
            return (int) (o2.exponent - o1.exponent);
        }        
    }
 
    private static final class Term {
        Number coefficient;
        long exponent;
 
        public Term(BigInteger c, long e) {
            coefficient = new Integer(c);
            exponent = e;
        }
 
        public Term(Number c, long e) {
            coefficient = c;
            exponent = e;
        }
 
        public Term multiply(Term term) {
            return new Term(coefficient.multiply(term.coefficient), exponent + term.exponent);
        }
 
        public Term add(Term term) {
            if ( exponent != term.exponent ) {
                throw new RuntimeException("ERROR 102:  Exponents not equal.");
            }
            return new Term(coefficient.add(term.coefficient), exponent);
        }
 
        public Term negate() {
            return new Term(coefficient.negate(), exponent);
        }
 
        public long degree() {
            return exponent;
        }
 
        @Override
        public String toString() {
            if ( coefficient.compareTo(Integer.ZERO_INT) == 0 ) {
                return "0";
            }
            if ( exponent == 0 ) {
                return "" + coefficient;
            }
            if ( coefficient.compareTo(Integer.ONE_INT) == 0 ) {
                if ( exponent == 1 ) {
                    return "x";
                }
                else {
                    return "x^" + exponent;
                }
            }
            if ( exponent == 1 ) {
                return coefficient + "x";
            }
            return coefficient + "x^" + exponent;
        }
    }
 
    private static abstract class Number {
        public abstract int compareTo(Number in);
        public abstract Number negate();
        public abstract Number add(Number in);
        public abstract Number multiply(Number in);
        public abstract Number inverse();
        public abstract boolean isInteger();
        public abstract boolean isFraction();
 
        public Number subtract(Number in) {
            return add(in.negate());
        }
 
        public Number divide(Number in) {
            return multiply(in.inverse());
        }
    }
 
    public static class Fraction extends Number {
 
        private final Integer numerator;
        private final Integer denominator;
 
        public Fraction(Integer n, Integer d) {
            numerator = n;
            denominator = d;
        }
 
        @Override
        public int compareTo(Number in) {
            if ( in.isInteger() ) {
                Integer result = ((Integer) in).multiply(denominator);
                return numerator.compareTo(result);
            }
            else if ( in.isFraction() ) {
                Fraction inFrac = (Fraction) in;
                Integer left = numerator.multiply(inFrac.denominator);
                Integer right = denominator.multiply(inFrac.numerator);
                return left.compareTo(right);
            }
            throw new RuntimeException("ERROR:  Unknown number type in Fraction.compareTo");
        }
 
        @Override
        public Number negate() {
            if ( denominator.integer.signum() < 0 ) {
                return new Fraction(numerator, (Integer) denominator.negate());
            }
            return new Fraction((Integer) numerator.negate(), denominator);
        }
 
        @Override
        public Number add(Number in) {
            if ( in.isInteger() ) {
                //x/y+z = (x+yz)/y
                return new Fraction((Integer) ((Integer) in).multiply(denominator).add(numerator), denominator);
            }
            else if ( in.isFraction() ) {
                Fraction inFrac = (Fraction) in;
                //  compute a/b + x/y
                //  Let q = gcd(b,y)
                //  Result = ( (a*y + x*b)/q ) / ( b*y/q )
                Integer x = inFrac.numerator;
                Integer y = inFrac.denominator;
                Integer q = y.gcd(denominator);
                Integer temp1 = numerator.multiply(y);
                Integer temp2 = denominator.multiply(x);
                Integer newDenom = denominator.multiply(y).divide(q);
                if ( newDenom.compareTo(Integer.ONE_INT) == 0 ) {
                    return temp1.add(temp2);
                }
                Integer newNum = (Integer) temp1.add(temp2).divide(q);
                Integer gcd2 = newDenom.gcd(newNum);
                if ( gcd2.compareTo(Integer.ONE_INT) == 0 ) {
                    return new Fraction(newNum, newDenom);
                }
                newNum = newNum.divide(gcd2);
                newDenom = newDenom.divide(gcd2);
                if ( newDenom.compareTo(Integer.ONE_INT) == 0 ) {
                    return newNum;
                }
                else if ( newDenom.compareTo(Integer.MINUS_ONE_INT) == 0 ) {
                    return newNum.negate();
                }
                return new Fraction(newNum, newDenom);
            }
            throw new RuntimeException("ERROR:  Unknown number type in Fraction.compareTo");
        }
 
        @Override
        public Number multiply(Number in) {
            if ( in.isInteger() ) {
                //x/y*z = x*z/y
                Integer temp = numerator.multiply((Integer) in);
                Integer gcd = temp.gcd(denominator);
                if ( gcd.compareTo(Integer.ONE_INT) == 0 || gcd.compareTo(Integer.MINUS_ONE_INT) == 0 ) {
                    return new Fraction(temp, denominator);
                }
                Integer newTop = temp.divide(gcd);
                Integer newBot = denominator.divide(gcd);
                if ( newBot.compareTo(Integer.ONE_INT) == 0 ) {
                    return newTop;
                }
                if ( newBot.compareTo(Integer.MINUS_ONE_INT) == 0 ) {
                    return newTop.negate();
                }
                return new Fraction(newTop, newBot);
            }
            else if ( in.isFraction() ) {
                Fraction inFrac = (Fraction) in;
                //  compute a/b * x/y
                Integer tempTop = numerator.multiply(inFrac.numerator);
                Integer tempBot = denominator.multiply(inFrac.denominator);
                Integer gcd = tempTop.gcd(tempBot);
                if ( gcd.compareTo(Integer.ONE_INT) == 0 || gcd.compareTo(Integer.MINUS_ONE_INT) == 0 ) {
                    return new Fraction(tempTop, tempBot);
                }
                Integer newTop = tempTop.divide(gcd);
                Integer newBot = tempBot.divide(gcd);
                if ( newBot.compareTo(Integer.ONE_INT) == 0 ) {
                    return newTop;
                }
                if ( newBot.compareTo(Integer.MINUS_ONE_INT) == 0 ) {
                    return newTop.negate();
                }
                return new Fraction(newTop, newBot);
            }
            throw new RuntimeException("ERROR:  Unknown number type in Fraction.compareTo");
        }
 
        @Override
        public boolean isInteger() {
            return false;
        }
 
        @Override
        public boolean isFraction() {
            return true;
        }
 
        @Override
        public String toString() {
            return numerator.toString() + "/" + denominator.toString();
        }
 
        @Override
        public Number inverse() {
            if ( numerator.equals(Integer.ONE_INT) ) {
                return denominator;
            }
            else if ( numerator.equals(Integer.MINUS_ONE_INT) ) {
                return denominator.negate();
            }
            else if ( numerator.integer.signum() < 0 ) {
                return new Fraction((Integer) denominator.negate(), (Integer) numerator.negate());            
            }
            return new Fraction(denominator, numerator);
        }
    }
 
    public static class Integer extends Number {
 
        private BigInteger integer;
        public static final Integer MINUS_ONE_INT = new Integer(new BigInteger("-1"));
        public static final Integer ONE_INT = new Integer(new BigInteger("1"));
        public static final Integer ZERO_INT = new Integer(new BigInteger("0"));
 
        public Integer(BigInteger number) {
            this.integer = number;
        }
 
        public int compareTo(Integer val) {
            return integer.compareTo(val.integer);
        }
 
        @Override
        public int compareTo(Number in) {
            if ( in.isInteger() ) {
                return compareTo((Integer) in);
            }
            else if ( in.isFraction() ) {
                Fraction frac = (Fraction) in;
                BigInteger result = integer.multiply(frac.denominator.integer);
                return result.compareTo(frac.numerator.integer);
            }
            throw new RuntimeException("ERROR:  Unknown number type in Integer.compareTo");
        }
 
        @Override
        public Number negate() {
            return new Integer(integer.negate()); 
        }
 
        public Integer add(Integer in) {
            return new Integer(integer.add(in.integer));
        }
 
        @Override
        public Number add(Number in) {
            if ( in.isInteger() ) {
                return add((Integer) in);
            }
            else if ( in.isFraction() ) {
                Fraction f = (Fraction) in;
                Integer top = f.numerator;
                Integer bot = f.denominator;
                return new Fraction((Integer) multiply(bot).add(top), bot);
            }
            throw new RuntimeException("ERROR:  Unknown number type in Integer.add");
        }
 
        @Override
        public Number multiply(Number in) {
            if ( in.isInteger() ) {
                return multiply((Integer) in);
            }
            else if ( in.isFraction() ) {
                //  a * x/y = ax/y
                Integer x = ((Fraction) in).numerator;
                Integer y = ((Fraction) in).denominator;
                Integer temp = (Integer) multiply(x);
                Integer gcd = temp.gcd(y);
                if ( gcd.compareTo(Integer.ONE_INT) == 0 || gcd.compareTo(Integer.MINUS_ONE_INT) == 0 ) {
                    return new Fraction(temp, y);
                }
                Integer newTop = temp.divide(gcd);
                Integer newBot = y.divide(gcd);
                if ( newBot.compareTo(Integer.ONE_INT) == 0 ) {
                    return newTop;
                }
                if ( newBot.compareTo(Integer.MINUS_ONE_INT) == 0 ) {
                    return newTop.negate();
                }
                return new Fraction(newTop, newBot);
            }
            throw new RuntimeException("ERROR:  Unknown number type in Integer.add");
        }
 
        public Integer gcd(Integer in) {
            return new Integer(integer.gcd(in.integer));
        }
 
        public Integer divide(Integer in) {
            return new Integer(integer.divide(in.integer));
        }
 
        public Integer multiply(Integer in) {
            return new Integer(integer.multiply(in.integer));
        }
 
        @Override
        public boolean isInteger() {
            return true;
        }
 
        @Override
        public boolean isFraction() {
            return false;
        }
 
        @Override
        public String toString() {
            return integer.toString();
        }
 
        @Override
        public Number inverse() {
            if ( equals(ZERO_INT) ) {
                throw new RuntimeException("Attempting to take the inverse of zero in IntegerExpression");
            }
            else if ( this.compareTo(ONE_INT) == 0 ) {
                return ONE_INT;
            }
            else if ( this.compareTo(MINUS_ONE_INT) == 0 ) {
                return MINUS_ONE_INT;
            }
            return new Fraction(ONE_INT, this);
        }
 
    }
}
 