An abstraction commonly used in algebra, calculus, and their applications is the polynomial. This is a sum of terms, each of which is the product of a real number, and a cardinal power of some variable. Thus,

3, 4x^{2}, 15y^{7}, and 23.45t^{9} are all terms and also are all one-term polynomials or monomials

4m - 7, 3x^{3}+5x, 7t^{2} - 2t are all two term polynomials or binomials

2x^{4} - 5x + 7 and 3d^{6} + 4d^{5} - 2d^{4} are three term polynomials or trinomials.

*In the polynomial term 4,7x ^{2}, the number 4.7 is called the coefficient, the letter x is called the (independent) variable, and the exponent 2 is called the degree of the term. The highest exponent in a polynomial is called the degree of the polynomial. Two terms that have the same variable and the same exponent are called like.*

A polynomial can be multiplied by a scalar simply by multiplying each of its coefficients by the scalar. Thus

4 (7x - 2) = 28x - 8

6 (x^{2 }+ 3x) = 12x^{2} + 18x

Two terms can be combined into one by addition only if they are like. Thus:

3x^{2} + 7x^{2} = 10x^{2}

2x - 6x + 5x = x

x^{2} + 6x - 5 cannot be further combined.

The sum of two polynomials are added (subtracted) by adding (subtracting) the coefficients of their mutual like terms:

(4x - 7) + (7x - 2) = 11x - 9

(3x^{2} + 4x) + (2x^{2} - 5) = 5x^{2} + 4x - 5

(5t - 8) - (2t - 7) = 3t - 1

Two monomials (terms) are multiplied by multiplying their coefficient factors and their variable factors. For instance,

(3x) ( 5x^{2}) = 15x^{3}

(3.2y^{7}) ( 5y^{4}) = 16y^{11}

If one wishes to multiply two longer polynomials, each term of the multiplier must be multiplied by each term of the multiplicand and the result added.

(7x - 5) (2x^{2} + 4) = (7x)(2x^{2}) + (7x)(4) + (-5)(2x^{2}) + (-5)(4) = 14x^{3} + 28x - 10x^{2} -20

(3x - 2) (4x + 5) = 12x^{2} + 15x -8x - 10 = 12x^{2} - 7x -10

For practical reasons (such as graphing the polynomial) one often wishes to evaluate a polynomial at a particular value of the variable. In such cases, the polynomial function is usually denoted P(x) and the evaluation using a particular number, say, c, by P(c). This is done by substituting. Thus if

P(x) = 3x^{2} + 2x - 7

P(2) = 3(2^{2}) + 2(2) - 7 = 9

P(5) = 3(5^{2}) + 2(5) - 7 = 78

With this little review of elementary algebra, it is not difficult to define a Polynomial ADT in Modula-2. One possibility would be:

DEFINITIONMODULEPolynomials; (* specification by R. Sutcliffe 1996 11 07 *)TYPEPolynomial;PROCEDUREInit (VARp : Polynomial); (* creates a polynomial and sets it to equal to zero *)PROCEDUREDestroy (VARp : Polynomial); (* gives back any dynamic memory: the result is an invalid polynomial*)PROCEDUREUpdateTerm (p : Polynomial; exp :CARDINAL; coef :REAL); (* sets the coeficient of the term of degree exp in a valid polynomial to coef *)PROCEDUREDegree (p: Polynomial) :CARDINAL; (* returns the degree of the specified polynomial *)PROCEDURENumTerms (p: Polynomial) :CARDINAL; (* returns the number of terms of the specified polynomial *)PROCEDURECoefficient (p: Polynomial; degree :CARDINAL) :REAL; (* returns the coefficient of the term of specified degree in the given polynomial *) (* The valid form of a string representation of a polynomial is [+|-term] and the valid string representation of a term is realnumbercoefficient, "charactervariablename", ["^" cardinalnumberexponent] *)PROCEDUREPolyToString (source : Polynomial;VARdest :ARRAYOFCHAR);PROCEDUREStringToPoly (source :ARRAYOFCHAR;VARdest : Polynomial);PROCEDUREValue (p : Polynomial; at :REAL) :REAL; (* evaluate the given polynomial at the specified value of the variable *)PROCEDUREAdd (p, q : Polynomial;VARres : Polynomial);PROCEDURESub (p, q : Polynomial;VARres : Polynomial);PROCEDUREMul (p, q : Polynomial;VARres : Polynomial);PROCEDUREScalarMul (VARp : Polynomial; scalar :REAL); (* 5(4x^2) for example *)ENDPolynomials.

A few observations are in order. The actual representation could be done in a number of ways. One would be to define a term, then define the *Polynomial* ADT as a linked list of terms. The latter could be done using an earlier and relatively generic linked list module, or the necessary apparatus could be customized within this module. For instance, the types could be:

TYPETermPoint =POINTERTOTerm; Term =RECORDcoefficient :REAL; exponent :CARDINAL; nextTerm, lastTerm : TermPoint;END; Polynomial =POINTERTOPolyDataNode; PolyDataNode =RECORDfirstTerm : Term; numTerms, degree :CARDINAL;END;

The string representation for a polynomial uses a fairly common notation that employs the caret symbol ^ to denote that the number following is an exponent. Thus 7x^{3} - 3x^{2} + 4 is represented by the string "7x^3 - 3.4x^2 + 4". The spaces are not relevant and can be ignored on input strings, but should be present for legibility on output strings. A full implementation will not be done here, and is left as a challenge to the reader.