  # An Algorithm for Computing Quotient and Remainder Polynomials

ABSTRACT

The task of dividing one polynomial by another is encountered in continuous fraction
expansion (CFE) and other engineering and systems science computations. This note
presents an efficient algorithm for performing the division. A method for constructing
synthetic division tableaus (SDT) for polynomials over any coefficient field is formulated
and the relative ease in extracting the solution from the tableau is demonstrated. The
beauty of the method lies in its simplicity even for manual calculations; and above its
efficiency, a minimal memory space is needed for program execution. While other
programs and algorithms exist for performing this task, the algorithm introduced in this
correspondence promises high efficiency and simplicity in formulation than many of the
existing methods. To demonstrate its effectiveness and efficiency, the new method is
compared to other existing methods.

I. Introduction

Polynomial long division (PLD) is often encountered in system science. It is used for
computing the greatest common divisor of two polynomials . A description of the
operations of polynomial long division can be found in many texts on algebraic
computing. Most of these descriptions are simply extensions or direct application of
Euclid’s algorithm. Also described in the literature is synthetic division algorithm for
polynomials applicable only in the case of a first order denominator (devisor)
polynomial. PLD operations have been implemented in several different algebraic
programs, over the years, with varying efficiencies and computer memory requirements.
Examples of softwares (old and new) with PLD operations include Altran, Derive,
Macsyma, MathCad , Mathematica, Maple, Reduce , SAC, and SMP.

The purpose of this correspondence is to introduce a novel algorithm for polynomial long
division which is comparable to the Euclidean in efficiency, if not superior. It is
applicable to polynomials of any degrees and over any coefficient field. This new
algorithm also requires minimal memory space and thus will be as useful as existing
operations for computer program implementation. Perhaps the most attractive features of
the proposed algorithm are its conceptual simplicity and convenience for calculations.

This paper constructs a PLD tableau based on a pattern of relationships between the
operands in a long division process. An algorithm for constructing the tableau is
described. An algorithm for constructing the tableau, the termination criterion and
interpretation of results are described. An example is used to illustrate the application of
the proposed algorithm.

II. Formulation of Algorithm

Consider two polynomials in s, and over a field, given by: Where d > or = n. It can be shown that the quotient polynomial is of the form: and the remainder polynomial is given by: A tableau can be constructed from which the coefficients of and of are
obtained. The first two rows of the tableau are formed by the coefficients, of the divisor - first row, and the coefficients of the dividend - second row;

j = 0,1,2,…d. Elements of subsequent rows of the tableau are derived from the
determinants of 2x2 matrices formed from an array of the first and last rows. In addition
to the rows formed with the coefficients of the divisor, - the Pivot row, and the
coefficients of the dividend, defined as ‘row zero’, d-n+1 rows are generated. Thus
the synthetic division tableau so formed is a matrix. This format is
illustrated in Table 1. below.

Table 1. Format for Synthetic Division Tableau

 Description j=0 j=1 j=2 … d PIVOT ROW: a n-j an 0 ROW ZERO: bb-j t=0  t=1   t=2  . . t=d-n REMAINDER COEFFICIENT ROW: t=d-n+1

Based on the above row definitions, equation (3) simply becomes Where represents the ‘row t, column zero’ element (entry) on the
tableau. Also, the entry on the tableau is given by  are calculated using the pivot row and the last row.

The following postulates are useful for determining the termination of the algorithm and
for obtaining the results from the tableau:
(i) has d-n+1 possible terms
(ii) has n terms
(iii) The coefficient of the term in is for t = j = 0,1,2,…d-n
(iv) The coefficient of the term in is for j = 0,1,2…n-1.

Thus we observe that once the tableau is constructed the quotient polynomial can easily
be assembled from the first row, j=1, and the coefficients for the remainder polynomial
are simply the elements of the last row, t=d-n+1, and in descending power of the variable .

III. Illustrative Example

To illustrate the proposed algorithm, we consider the division of the following
pair of Polynomials given by: d = 4, n = 2, the order of the order of and the number of
steps
= d-n+1 = 3; t = 0,1,2,3. Hence, and IV. Concluding Remarks

A nontrivial algorithm for finding the quotient and remainder polynomials is derived. It
will be noted that the algorithm requires an explicit division only by an the leading
coefficient of and it should also be observed that there are only d–n+1 steps required
in the computation of the coefficients of and . In these regards this algorithm is
similar to the Euclidean and since there are no loops or recursions in this algorithm it
might be more efficient than most long division process described in algebraic texts .

 Prev Next

Start solving your Algebra Problems in next 5 minutes!   Algebra Helper Download (and optional CD) Only \$39.99 Click to Buy Now: OR   2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of June 22nd you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor: Step 2 : Let Algebra Helper solve it: Step 3 : Ask for an explanation for the steps you don't understand: Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!   Algebra Helper Download (and optional CD) Only \$39.99 Click to Buy Now: OR   2Checkout.com is an authorized reseller
of goods provided by Sofmath "It really helped me with my homework.  I was stuck on some problems and your software walked me step by step through the process..." C. Sievert, KY Sofmath 19179 Blanco #105-234San Antonio, TX 78258 Phone: (512) 788-5675Fax: (512) 519-1805 Home   : :   Features   : :   Demo   : :   FAQ   : :   Order Copyright © 2004-2021, Algebra-Answer.Com.  All rights reserved.