Polynomial synthetic division

Polynomial synthetic division is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

This page uses content from Wikipedia. The original article was at Polynomial synthetic 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 synthetic division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree in an efficient way using a clever trick involving clever manipulations of coefficients, which results in a lot less complexity than than polynomial long division.

Python

Here is an extended synthetic division algorithm, which means that it supports a divisor polynomial (instead of a monomial or a binomial). It also supports non-monic polynomials (polynomials which first coefficient is different than 1). Polynomials are represented by lists of coefficients with decreasing degree (left-most is the major degree , right-most is the constant).

Works with: Python 2.x

<lang python># -*- coding: utf-8 -*-

def extended_synthetic_division(dividend, divisor):

   Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.
   # dividend and divisor are both polynomials, which are here simply lists of coefficients. Eg: x^2 + 3x + 5 will be represented as [1, 3, 5]

   out = list(dividend) # Copy the dividend
   normalizer = divisor[0]
   for i in xrange(len(dividend)-(len(divisor)-1)):
       out[i] /= normalizer # for general polynomial division (when polynomials are non-monic),
                                # we need to normalize by dividing the coefficient with the divisor's first coefficient
       coef = out[i]
       if coef != 0: # useless to multiply if coef is 0
           for j in xrange(1, len(divisor)): # in synthetic division, we always skip the first coefficient of the divisior,
                                             # because it's only used to normalize the dividend coefficients
               out[i + j] += -divisor[j] * coef

   # The resulting out contains both the quotient and the remainder, the remainder being the size of the divisor (the remainder
   # has necessarily the same degree as the divisor since it's what we couldn't divide from the dividend), so we compute the index
   # where this separation is, and return the quotient and remainder.
   separator = -(len(divisor)-1)
   return out[:separator], out[separator:] # return quotient, remainder.

if __name__ == '__main__':

   print "POLYNOMIAL SYNTHETIC DIVISION"
   N = [1, -12, 0, -42]
   D = [1, -3]
   print "  %s / %s =" % (N,D),
   print " %s remainder %s" % extended_synthetic_division(N, D)

</lang>

Sample output:

POLYNOMIAL SYNTHETIC DIVISION
  [1, -12, 0, -42] / [1, -3] =  [1, -9, -27] remainder [-123]