St. Louis, Missouri
June 18, 2000
June 18, 2000
June 21, 2000
5.86.1 - 5.86.4
Division (session) 65
An Algorithm for Computing Quotient and Remainder Polynomials
Department of Engineering Technology Savannah State University Savannah, Georgia 31404
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.
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.
Kalu, A. O. (2000, June), An Algorithm For Computing Quotient And Remainder Polynomials Paper presented at 2000 Annual Conference, St. Louis, Missouri. https://peer.asee.org/8163
ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2000 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015