[1] 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.
[2] 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.
[3] 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.
[4] 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.
[5] 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 symbol javascript_number .
[6] Although we are assuming that term lists are ordered, we have implemented adjoin_term to simply pair the new term onto 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).
[7] 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.
[8] 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.
2.5.3 Example: Symbolic Algebra