Paper Authors

Abstract

NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

Division (session) 65

An Algorithm for Computing Quotient and Remainder Polynomials

Alex Kalu

Department of Engineering Technology Savannah State University Savannah, Georgia 31404

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.

• Citation

• Format
  • APA
  • APA - LaTeX bibitem
  • MLA
  • MLA - LaTeX bibitem
  • Bibtex
  • EndNote - RIS

Kalu, A. O. (2000, June), An Algorithm For Computing Quotient And Remainder Polynomials Paper presented at 2000 Annual Conference, St. Louis, Missouri. 10.18260/1-2--8163