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, 4x2, 15y7, and 23.45t9 are all terms and also are all one-term polynomials or monomials
4m - 7, 3x3+5x, 7t2 - 2t are all two term polynomials or binomials
2x4 - 5x + 7 and 3d6 + 4d5 - 2d4 are three term polynomials or trinomials.
In the polynomial term 4,7x2, 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 (x2 + 3x) = 12x2 + 18x
Two terms can be combined into one by addition only if they are like. Thus:
3x2 + 7x2 = 10x2
2x - 6x + 5x = x
x2 + 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
(3x2 + 4x) + (2x2 - 5) = 5x2 + 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) ( 5x2) = 15x3
(3.2y7) ( 5y4) = 16y11
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) (2x2 + 4) = (7x)(2x2) + (7x)(4) + (-5)(2x2) + (-5)(4) = 14x3 + 28x - 10x2 -20
(3x - 2) (4x + 5) = 12x2 + 15x -8x - 10 = 12x2 - 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) = 3x2 + 2x - 7
P(2) = 3(22) + 2(2) - 7 = 9
P(5) = 3(52) + 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:
DEFINITION MODULE Polynomials; (* specification by R. Sutcliffe 1996 11 07 *) TYPE Polynomial; PROCEDURE Init (VAR p : Polynomial); (* creates a polynomial and sets it to equal to zero *) PROCEDURE Destroy (VAR p : Polynomial); (* gives back any dynamic memory: the result is an invalid polynomial*) PROCEDURE UpdateTerm (p : Polynomial; exp : CARDINAL; coef : REAL); (* sets the coeficient of the term of degree exp in a valid polynomial to coef *) PROCEDURE Degree (p: Polynomial) : CARDINAL; (* returns the degree of the specified polynomial *) PROCEDURE NumTerms (p: Polynomial) : CARDINAL; (* returns the number of terms of the specified polynomial *) PROCEDURE Coefficient (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] *) PROCEDURE PolyToString (source : Polynomial; VAR dest : ARRAY OF CHAR); PROCEDURE StringToPoly (source : ARRAY OF CHAR; VAR dest : Polynomial); PROCEDURE Value (p : Polynomial; at : REAL) : REAL; (* evaluate the given polynomial at the specified value of the variable *) PROCEDURE Add (p, q : Polynomial; VAR res : Polynomial); PROCEDURE Sub (p, q : Polynomial; VAR res : Polynomial); PROCEDURE Mul (p, q : Polynomial; VAR res : Polynomial); PROCEDURE ScalarMul (VAR p : Polynomial; scalar : REAL); (* 5(4x^2) for example *) END Polynomials.
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:
TYPE
TermPoint = POINTER TO Term;
Term =
RECORD
coefficient : REAL;
exponent : CARDINAL;
nextTerm, lastTerm : TermPoint;
END;
Polynomial = POINTER TO PolyDataNode;
PolyDataNode =
RECORD
firstTerm : 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 7x3 - 3x2 + 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.