Polynomial GCD derived through monic polynomial subtractions (Q420250)

The computation of the greatest common divisor (GCD) of a pair of polynomials is an important issue in computational mathematics and also plays a crucial role in many science and engineering fields. Several numerical methods have been proposed for the derivation of polynomial GCD. Some are based on the classical Euclidean algorithm and the others are based on the procedures involving Sylvester resultant matrix. Most of them require an algorithm of some advanced mathematics, such as the singular value decomposition and the least square iteration process. In this paper a simple and effective method to find the GCD of a pair of given polynomials is presented. The process requires only the successive subtraction of two monic polynomials. It is modified purposely from the longhand polynomial divisions employed in the classical Euclidean GCD computation. The entire computations require only simple elementary arithmetic operations, such as division and subtraction. A MATLAB code is provided, along with a typical numerical example. Amazingly, this routine gives the GCD for a pair of test polynomials of very high degree.