The manipulation of symbolic algebraic expressions is a complex
process that illustrates many of the hardest problems that occur in
the design of large-scale systems. An
algebraic expression, in
general, can be viewed as a hierarchical structure, a tree of
operators applied to operands. We can construct algebraic expressions
by starting with a set of primitive objects, such as constants and
variables, and combining these by means of algebraic operators, such
as addition and multiplication. As in other languages, we form
abstractions that enable us to refer to compound objects in simple
terms. Typical abstractions in symbolic algebra are ideas such as
linear combination, polynomial, rational function, or trigonometric
function. We can regard these as compound types, which are
often useful for directing the processing of expressions. For example, we
could describe the expression
\[ x^{2}\, \sin (y^2+1)+x\, \cos 2y+\cos (y^3 -2y^2) \]
as a polynomial in $x$ with coefficients that
are trigonometric functions of polynomials in
$y$ whose coefficients are integers.
We will not attempt to develop a complete algebraic-manipulation
system here. Such systems are exceedingly complex programs, embodying
deep algebraic knowledge and elegant algorithms. What we will do is
look at a simple but important part of algebraic manipulation: the
arithmetic of polynomials. We will illustrate the kinds of decisions
the designer of such a system faces, and how to apply the ideas of
abstract data and generic operations to help organize this effort.
Our first task in designing a system for performing arithmetic on
polynomials is to decide just what a polynomial is. Polynomials are
normally defined relative to certain variables (the
indeterminates of the polynomial). For simplicity, we will
restrict ourselves to polynomials having just one indeterminate
(univariate polynomials).
We will define a polynomial to
be a sum of terms, each of which is either a coefficient, a power of the
indeterminate, or a product of a coefficient and a power of the
indeterminate. A coefficient is defined as an algebraic expression
that is not dependent upon the indeterminate of the polynomial. For
example,
\[ 5x^2 +3x +7 \]
is a simple polynomial in $x$, and
\[ (y^2 +1)x^3 +(2y)x+1 \]
is a polynomial in $x$ whose coefficients are
polynomials in $y$.
Already we are skirting some thorny issues. Is the first of these
polynomials the same as the polynomial
$5y^2 +3y +7$, or not? A reasonable answer
might be yes, if we are considering a polynomial purely as a
mathematical function, but no, if we are considering a polynomial to be a
syntactic form. The second polynomial is algebraically equivalent
to a polynomial in $y$ whose coefficients are
polynomials in $x$. Should our system recognize
this, or not? Furthermore, there are other ways to represent a
polynomial—for example, as a product of factors, or (for a
univariate polynomial) as the set of roots, or as a listing of the values
of the polynomial at a specified set of points.
We can finesse these questions by deciding that in our
algebraic-manipulation system a polynomial will be a
particular syntactic form, not its underlying mathematical meaning.
Now we must consider how to go about doing arithmetic on polynomials.
In this simple system, we will consider only addition and
multiplication. Moreover, we will insist that two polynomials to be
combined must have the same indeterminate.
We will approach the design of our system by following the familiar
discipline of data abstraction. We will represent polynomials using a
data structure called a
poly, which consists of a variable and a
collection of terms. We assume that we have selectors
variable and
term_list
that extract those parts from a poly and a constructor
make_poly
that assembles a poly from a given variable and a term list.
A variable will be just a
string,
so we can use the
is_same_variable
function
of section 2.3.2 to compare
variables.
The following
functions
define
addition and multiplication of polys:
function add_poly(p1, p2) {
return is_same_variable(variable(p1), variable(p2))
? make_poly(variable(p1),
add_terms(term_list(p1), term_list(p2)))
: error(list(p1, p2), "polys not in same var -- add_poly");
}
function mul_poly(p1, p2) {
return is_same_variable(variable(p1), variable(p2))
? make_poly(variable(p1),
mul_terms(term_list(p1), term_list(p2)))
: error(list(p1, p2), "polys not in same var -- mul_poly");
}
To incorporate polynomials into our generic arithmetic system, we need
to supply them with type tags. We'll use the tag
"polynomial",
and install appropriate operations on tagged polynomials in the operation
table.
function install_polynomial_package() {
// internal functions
// representation of poly
function make_poly(variable, term_list) {
return pair(variable, term_list);
}
function variable(p) { return head(p); }
function term_list(p) { return tail(p); }
$\langle{}$functions is_same_variable and is_variable from section 2.3.2$\rangle$
// representation of terms and term lists
$\langle{}$functions adjoin_term...coeff from text below$\rangle$
function add_poly(p1, p2) { ... }
$\langle{}$functions used by add_poly$\rangle$
function mul_poly(p1, p2) { ... }
$\langle{}$functions used by mul_poly$\rangle$
// interface to rest of the system
function tag(p) { return attach_tag("polynomial", p); }
put("add", list("polynomial", "polynomial"),
(p1, p2) => tag(add_poly(p1, p2)));
put("mul", list("polynomial", "polynomial"),
(p1, p2) => tag(mul_poly(p1, p2)));
put("make", "polynomial",
(variable, terms) => tag(make_poly(variable, terms)));
return "done";
}
Polynomial addition is performed termwise. Terms of the same order
(i.e., with the same power of the indeterminate) must be combined.
This is done by forming a new term of the same order whose coefficient
is the sum of the coefficients of the addends. Terms in one addend
for which there are no terms of the same order in the other addend are
simply accumulated into the sum polynomial being constructed.
In order to manipulate term lists, we will assume that we have a
constructor
the_empty_termlist
that returns an empty term list and a constructor
adjoin_term
that adjoins a new term to a term list. We will also assume that we have
a predicate
is_empty_termlist
that tells if a given term list is empty, a selector
first_term
that extracts the highest-order term from a term list, and a selector
rest_terms
that returns all but the highest-order term. To manipulate terms,
we will suppose that we have a constructor
make_term
that constructs a term with given order and coefficient, and selectors
order and
coeff that return, respectively, the order
and the coefficient of the term. These operations allow us to consider
both terms and term lists as data abstractions, whose concrete
representations we can worry about separately.
note that we slightly extend the syntax of
conditional statements described in
section 1.3.2 by admitting another conditional
statement in place of the block following
else:
The most important point to note here is that we used the generic addition
function
add to add together the coefficients of the
terms being combined. This has powerful consequences, as we will see below.
In order to multiply two term lists, we multiply each term of the first
list by all the terms of the other list, repeatedly using
mul_term_by_all_terms,
which multiplies a given term by all terms in a given term list. The
resulting term lists (one for each term of the first list) are accumulated
into a sum. Multiplying two terms forms a term whose order is the sum of
the orders of the factors and whose coefficient is the product of the
coefficients of the factors:
This is really all there is to polynomial addition and multiplication.
Notice that, since we operate on terms using the generic
functions
add and mul,
our polynomial package is automatically able to handle any type of
coefficient that is known about by the generic arithmetic package.
If we include a
coercion mechanism such as one of those discussed in
section 2.5.2,
then we also are automatically able to handle operations on
polynomials of different coefficient types, such as
\[
\begin{array}{l}
{\left[3x^2 +(2+3i)x+7\right] \cdot \left[x^4 +\frac{2}{3}x^2
+(5+3i)\right]}
\end{array}
\]
Because we installed the polynomial addition and multiplication
functions
add_poly
and
mul_poly
in the generic arithmetic system as the add
and mul operations for type
polynomial, our system is also automatically
able to handle polynomial operations such as
\[
\begin{array}{l}
{\left[ (y+1)x^2 +(y^2 +1)x+(y-1)\right]\cdot \left[(y-2)x+(y^3 +7)\right]}
\end{array}
\]
The reason is that when the system tries to combine coefficients, it
will dispatch through add and
mul. Since the coefficients are themselves
polynomials (in $y$), these will be combined
using
add_poly
and
mul_poly.
The result is a kind of
data-directed recursion in which, for example, a call to
mul_poly
will result in recursive calls to
mul_poly
in order to multiply the coefficients. If the coefficients of the
coefficients were themselves polynomials (as might be used to represent
polynomials in three variables), the data direction would ensure that the
system would follow through another level of recursive calls, and so on
through as many levels as the structure of the data dictates.
Finally, we must confront the job of implementing a good
representation for term lists. A term list is, in effect, a set of
coefficients keyed by the order of the term. Hence, any of the
methods for representing sets, as discussed in
section 2.3.3, can be applied to this
task. On the other hand, our
functions
add_terms
and
mul_terms
always access term lists sequentially from highest to lowest order.
Thus, we will use some kind of ordered list representation.
How should we structure the list that represents a term list? One
consideration is the density of the polynomials we intend
to manipulate. A polynomial is said to be
dense if it has nonzero coefficients in terms of most orders.
If it has many zero terms it is said to be
sparse. For example,
\[ A:\quad x^5 +2x^4 +3x^2 -2x -5 \]
is a dense polynomial, whereas
\[ B:\quad x^{100} +2x^2 +1 \]
is sparse.
The term list of a dense polynomial is most efficiently represented
as a list of the coefficients.
For example,
the polynomial
$A$ above would be nicely represented as
list(1, 2, 0, 3, -2, -5).
The order of a term in this representation is the length of the sublist
beginning with that term's coefficient, decremented by 1.
This would be a terrible representation for a sparse polynomial such as
$B$: There would be a giant list of zeros
punctuated by a few lonely nonzero terms. A more reasonable representation
of the term list of a sparse polynomial is as a list of the nonzero terms,
where each term is a list containing the order of the term and the
coefficient for that order. In such a scheme, polynomial
$B$ is efficiently represented as
list(list(100, 1), list(2, 2), list(0, 1)).
As most polynomial manipulations are performed on sparse polynomials, we
will use this method. We will assume that term lists are represented as
lists of terms, arranged from highest-order to lowest-order term. Once we
have made this decision, implementing the selectors and constructors for
terms and term lists is straightforward:
Install
is_equal_to_zero
for polynomials in the generic arithmetic package. This will allow
adjoin_term
to work for polynomials with coefficients that are themselves polynomials.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Declare functions
that implement the term-list representation described above as
appropriate for dense polynomials.
上述の密な多項式に適した項リスト表現を実装する
関数を宣言
してください。
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Suppose we want to have a polynomial system that is efficient for both
sparse and dense polynomials. One way to do this is to allow both
kinds of term-list representations in our system. The situation is
analogous to the complex-number example of
section 2.4, where we allowed both
rectangular and polar representations. To do this we must distinguish
different types of term lists and make the operations on term lists
generic. Redesign the polynomial system to implement this generalization.
This is a major effort, not a local change.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
A univariate polynomial can be divided by another one to produce a
polynomial quotient and a polynomial remainder. For example,
\[
\begin{array}{lll}
\dfrac{x^5-1}{x^2 -1} & = & x^3 +x,\ \text{remainder }x-1
\end{array}
\]
Division can be performed via long division.
That is, divide the highest-order term of the dividend by
the highest-order term of the divisor. The result is the first term of the
quotient. Next, multiply the result by the divisor, subtract that
from the dividend, and produce the rest of the answer by recursively
dividing the difference by the divisor. Stop when the order of the
divisor exceeds the order of the dividend and declare the dividend to
be the remainder. Also, if the dividend ever becomes zero, return
zero as both quotient and remainder.
We can design a
div_poly
function
on the model of
add_poly
and
mul_poly.
The
function
checks to see if the two polys have the same variable. If so,
div_poly
strips off the variable and passes the problem to
div_terms,
which performs the division operation on term lists.
The function
div_poly
finally reattaches the variable to the result supplied by
div_terms.
It is convenient to design
div_terms
to compute both the quotient and the remainder of a division.
The function div_terms
can take two term lists as arguments and return a list of the quotient
term list and the remainder term list.
Complete the following definition of
div_terms
by filling in the missing
parts.
Use this to implement
div_poly,
which takes two polys as arguments and returns a list of the quotient and
remainder polys.
function div_terms(L1, L2) {
if (is_empty_termlist(L1)) {
return list(the_empty_termlist, the_empty_termlist);
} else {
const t1 = first_term(L1);
const t2 = first_term(L2);
if (order(t2) > order(t1)) {
return list(the_empty_termlist, L1);
} else {
const new_c = div(coeff(t1), coeff(t2));
const new_o = order(t1) - order(t2);
const rest_of_result = $\langle{}$compute rest of result recursively$\rangle$;
$\langle{}$form and return complete result$\rangle$
}
}
}
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Hierarchies of types in symbolic algebra
シンボリック代数における型の階層
Our polynomial system illustrates how objects of one type
(polynomials) may in fact be complex objects that have objects of many
different types as parts. This poses no real difficulty in defining
generic operations. We need only install appropriate generic operations
for performing the necessary manipulations of the parts of the
compound types. In fact, we saw that polynomials form a kind of
recursive data abstraction, in that parts of a polynomial may
themselves be polynomials. Our generic operations and our
data-directed programming style can handle this complication without
much trouble.
On the other hand, polynomial algebra is a system for which the data
types cannot be naturally arranged in a tower. For instance, it is
possible to have polynomials in $x$ whose
coefficients are polynomials in $y$. It is also
possible to have polynomials in $y$ whose
coefficients are polynomials in $x$. Neither of
these types is above the other in any natural way, yet it is
often necessary to add together elements from each set. There are several
ways to do this. One possibility is to convert one polynomial to the type
of the other by expanding and rearranging terms so that both polynomials
have the same principal variable. One can impose a towerlike structure on
this by ordering the variables and thus always converting any polynomial
to a
canonical form with the highest-priority variable
dominant and the lower-priority variables buried in the coefficients.
This strategy works fairly well, except that the conversion may expand
a polynomial unnecessarily, making it hard to read and perhaps less
efficient to work with. The tower strategy is certainly not natural
for this domain or for any domain where the user can invent new types
dynamically using old types in various combining forms, such as
trigonometric functions, power series, and integrals.
It should not be surprising that controlling
coercion is a serious problem in the design of large-scale
algebraic-manipulation systems. Much of the complexity of such systems is
concerned with relationships among diverse types. Indeed, it is fair to
say that we do not yet completely understand coercion. In fact, we do not
yet completely understand the concept of a data type. Nevertheless, what
we know provides us with powerful structuring and modularity principles to
support the design of large systems.
By imposing an ordering on variables, extend the polynomial package so
that addition and multiplication of polynomials works for polynomials
in different variables. (This is not easy!)
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Extended exercise: Rational functions
発展演習：有理関数
We can extend our generic arithmetic system to include rational
functions. These are fractions whose numerator and
denominator are polynomials, such as
\[
\begin{array}{l}
\dfrac{x+1}{x^3 -1}
\end{array}
\]
The system should be able to add, subtract, multiply, and divide
rational functions, and to perform such computations as
\[
\begin{array}{lll}
\dfrac{x+1}{x^3 -1}+\dfrac{x}{x^2 -1} & = & \dfrac{x^3 +2x^2 +3x +1}{x^4 +
x^3 -x-1}
\end{array}
\]
(Here the sum has been simplified by removing common factors.
Ordinary cross multiplication would have produced a
fourth-degree polynomial over a fifth-degree polynomial.)
If we modify our rational-arithmetic package so that it uses generic
operations, then it will do what we want, except for the problem
of reducing fractions to lowest terms.
Modify the rational-arithmetic package to use generic operations, but
change
make_rat
so that it does not attempt to reduce fractions to lowest terms. Test
your system by calling
make_rational
on two polynomials to produce a rational function
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
We can reduce polynomial fractions to lowest terms using the same idea
we used with integers: modifying
make_rat
to divide both the numerator and the denominator by their greatest common
divisor. The notion of
greatest common divisor makes sense for polynomials. In
fact, we can compute the GCD of two polynomials using essentially the
same Euclid's Algorithm that works for integers.
function gcd(a, b) {
return b === 0
? a
: gcd(b, a % b);
}
Using this, we could make the obvious modification to define a GCD
operation that works on term lists:
これを使って、項リストに対して機能するGCD演算を定義するための明白な修正を行うことができます。
function gcd_terms(a, b) {
return is_empty_termlist(b)
? a
: gcd_terms(b, remainder_terms(a, b));
}
where
remainder_terms
picks out the remainder component of the list returned by the term-list
division operation
div_terms
that was implemented in exercise 2.91.
Using
div_terms,
implement the
function
remainder_terms
and use this to define
gcd_terms
as above. Now write a
function
gcd_poly
that computes the polynomial GCD of two polys. (The
function
should signal an error if the two polys are not in the same variable.)
Install in the system a generic operation
greatest_common_divisor
that reduces to
gcd_poly
for polynomials and to ordinary gcd for
ordinary numbers. As a test, try
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Define $P_{1}$,
$P_{2}$, and
$P_{3}$ to be the polynomials
$P_{1}$:
$x^2 - 2x + 1$
$P_{2}$:
$11x^2 + 7$
$P_{3}$:
$13x + 5$
Now define $Q_1$ to be the product of
$P_1$ and $P_2$ and
$Q_2$ to be the product of
$P_1$ and $P_3$, and
use
greatest_common_divisor
(exercise 2.94) to compute the GCD of
$Q_1$ and $Q_2$.
Note that the answer is not the same as $P_1$.
This example introduces noninteger operations into the computation, causing
difficulties with the GCD
algorithm.
To understand what is happening, try tracing
gcd_terms
while computing the GCD or try performing the division by hand.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
We can solve the problem exhibited in
exercise 2.95 if
we use the following modification of the GCD algorithm (which really
works only in the case of polynomials with integer coefficients).
Before performing any polynomial division in the GCD computation, we
multiply the dividend by an integer constant factor, chosen to
guarantee that no fractions will arise during the division process.
Our answer will thus differ from the actual GCD by an integer constant
factor, but this does not matter in the case of reducing rational
functions to lowest terms; the GCD will be used to divide both the
numerator and denominator, so the integer constant factor will cancel
out.
More precisely, if $P$ and
$Q$ are polynomials, let
$O_1$ be the order of
$P$ (i.e., the order of the largest term of
$P$) and let $O_2$
be the order of $Q$. Let
$c$ be the leading coefficient of
$Q$. Then it can be shown that, if we multiply
$P$ by the
integerizing factor
$c^{1+O_{1} -O_{2}}$, the resulting polynomial
can be divided by $Q$ by using the
div_terms
algorithm without introducing any fractions. The operation of multiplying
the dividend by this constant and then dividing is sometimes called the
pseudodivision of $P$ by
$Q$. The remainder of the division is
called the
pseudoremainder.
Implement the
function
pseudoremainder_terms,
which is just like
remainder_terms
except that it multiplies the dividend by the integerizing factor
described above before calling
div_terms.
Modify
gcd_terms
to use
pseudoremainder_terms,
and verify that
greatest_common_divisor
now produces an answer with integer coefficients on the example in
exercise 2.95.
The GCD now has integer coefficients, but they are larger than those
of $P_1$. Modify
gcd_terms
so that it removes common factors from the coefficients of the answer
by dividing all the coefficients by their (integer) greatest common
divisor.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Thus, here is how to reduce a rational function to lowest terms:
Compute the GCD of the numerator and denominator, using
the version of
gcd_terms
from exercise 2.96.
When you obtain the GCD, multiply both numerator and
denominator by the same integerizing factor before dividing through by
the GCD, so that division by the GCD will not introduce any noninteger
coefficients. As the factor you can use the leading coefficient of
the GCD raised to the power
$1+O_{1} -O_{2}$, where
$O_{2}$ is the order of the GCD and
$O_{1}$ is the maximum of the orders of the
numerator and denominator. This will ensure that dividing the
numerator and denominator by the GCD will not introduce any fractions.
The result of this operation will be a numerator and denominator
with integer coefficients. The coefficients will normally be very
large because of all of the integerizing factors, so the last step is
to remove the redundant factors by computing the (integer) greatest
common divisor of all the coefficients of the numerator and the
denominator and dividing through by this factor.
Implement this algorithm as a
function
reduce_terms
that takes two term lists n and
d as arguments and returns a list
nn, dd,
which are n and
d reduced to lowest terms via the
algorithm given above. Also write a
function
reduce_poly,
analogous to
add_poly,
that checks to see if the two polys have the same variable. If so,
reduce_poly
strips off the variable and passes the problem to
reduce_terms,
then reattaches the variable to the two term lists supplied by
reduce_terms.
Define a
function
analogous to
reduce_terms
that does what the original
make_rat
did for integers:
このアルゴリズムを、2つの項リスト n と d を引数として受け取り、上記のアルゴリズムで既約に約分された n と d であるリスト nn、dd を返す
関数
reduce_terms
として実装してください。また、
add_poly
と同様の
関数
reduce_poly
も書いてください。これは2つの多項式が同じ変数を持つかどうかを確認します。同じであれば、
reduce_poly
は変数を取り除き、問題を
reduce_terms
に渡し、
reduce_terms
が提供する2つの項リストに変数を再び付けます。
function reduce_integers(n, d) {
const g = gcd(n, d);
return list(n / g, d / g);
}
and define
reduce as a generic operation that calls
apply_generic
to dispatch
either to
reduce_poly
(for polynomial arguments) or
to reduce_integers
(for
javascript_number
arguments). You can now easily make the rational-arithmetic package
reduce fractions to lowest terms by having
make_rat
call reduce before combining the given
numerator and denominator to form a rational number. The system now
handles rational expressions in either integers or polynomials.
To test your program, try the example at the beginning of this
extended exercise:
See if you get the correct answer, correctly reduced to lowest terms.
正しい答えが得られ、正しく既約分数に約分されているかどうか確認してください。
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
The GCD computation is at the heart of any system that does operations
on rational functions. The algorithm used above, although
mathematically straightforward, is extremely slow. The slowness is
due partly to the large number of division operations and partly to
the enormous size of the intermediate coefficients generated by the
pseudodivisions.
One of the active areas in the development of
algebraic-manipulation systems is the design of better algorithms for
computing polynomial GCDs.
On the other hand, we will
allow polynomials whose coefficients are themselves polynomials in other
variables. This will give us essentially the same representational
power as a full multivariate system, although it does lead to coercion
problems, as discussed below.
For univariate
polynomials, giving the value of a polynomial at a given set of points can
be a particularly good representation. This makes polynomial arithmetic
extremely simple. To obtain, for example, the sum of two polynomials
represented in this way, we need only add the values of the
polynomials at corresponding points. To transform back to a more
familiar representation, we can use the
Lagrange interpolation formula, which shows how to recover the coefficients
of a polynomial of degree $n$ given the values
of the polynomial at $n+1$ points.
This operation is very much like the ordered
union_set
operation we developed in exercise 2.62.
In fact, if we think of the terms of the polynomial as a set ordered
according to the power of the indeterminate, then the program that
produces the term list for a sum is almost identical to
union_set.
To
make this work completely smoothly, we should also add to our generic
arithmetic system the ability to coerce a number to a
polynomial by regarding it as a polynomial of degree zero whose coefficient
is the number. This is necessary if we are going to perform operations
such as
\[
{\left[ x^2 +(y+1)x+5\right]+ \left[ x^2 +2x+1\right]}
\]
which requires adding the coefficient $y+1$ to
the coefficient 2.
In
these polynomial examples, we assume that we have implemented the generic
arithmetic system using the type mechanism suggested in
exercise 2.78. Thus, coefficients
that are ordinary numbers will be represented as the numbers themselves
rather than as pairs whose
head
is the
string
"javascript_number".
これらの多項式の例では、演習問題 2.78で提案された型メカニズムを使ってジェネリック算術システムを実装したものと仮定しています。したがって、通常の数である係数は、
head
が
文字列
"javascript_number"
であるペアとしてではなく、数そのものとして表現されます。
Although we are assuming
that term lists are ordered, we have implemented
adjoin_term
to simply
adjoin the new term to the front of the existing term list.
We can get away with this so
long as we guarantee that the
functions
(such as
add_terms)
that use
adjoin_term
always call it with a higher-order term than appears in the list. If we
did not want to make such a guarantee, we could have implemented
adjoin_term
to be similar to the
adjoin_set
constructor for the ordered-list
representation of sets
(exercise 2.61).
The fact
that
Euclid's Algorithm works for polynomials is formalized in algebra
by saying that polynomials form a kind of algebraic domain called a
Euclidean ring. A Euclidean ring is a domain that admits
addition, subtraction, and commutative multiplication, together with a
way of assigning to each element $x$ of the
ring a positive integer
measure $m(x)$ with the
properties that $m(xy)\geq m(x)$ for any nonzero
$x$ and $y$ and that,
given any $x$ and $y$,
there exists a $q$ such that
$y=qx+r$ and either
$r=0$ or
$m(r) < m(x)$. From an abstract point of
view, this is what is needed to prove that Euclid's Algorithm works.
For the domain of integers, the measure $m$ of an
integer is the absolute value of the integer itself. For the domain of
polynomials, the measure of a polynomial is its degree.
One extremely efficient and
elegant method for computing
polynomial GCDs was discovered by
Richard Zippel (1979). The method is a probabilistic algorithm, as is the
fast test for primality that we discussed in chapter 1.
Zippel's book (1993) describes this method, together with other ways
to compute polynomial GCDs.
多項式のGCDを計算するための極めて効率的でエレガントな方法は、
Richard Zippel（1979）によって発見されました。この方法は確率的アルゴリズムであり、1章で議論した素数性の高速テストと同様です。Zippelの著書（1993）は、この方法と多項式のGCDを計算する他の方法を説明しています。