506 ARITHMETIC 4.7 *4.7. MANIPULATION OF POWER SERIES (Jetty web server)
506 ARITHMETIC 4.7 *4.7. MANIPULATION OF POWER SERIES IF WE ARE GIVEN two power series U(z) = uo + VIZ + u22 + . . . , v(z)=vo+v~z+v~z2+*.*, (1) whose coefficients belong to a field, we can form their sum, their product, their quotient, etc., to obtain new power series. A polynomial is obviously a special case of a power series, in which there are only finitely many terms. Of course, only a finite number of terms can be represented and stored within a computer, so it makes sense to ask whether power series arithmetic is even possible on computers; and if it is possible, what makes it different from polynomial arithmetic? The answer is that we work with only the first N coefficients of the power series, where N is a parameter that may in principle be arbitrarily large; instead of ordinary polynomial arithmetic, we are essentially doing polynomial arithmetic modulo .zN, and this often leads to a somewhat different point of view. Furthermore, special operations like reversion can be performed on power series but not on polynomials, since polynomials are not closed under these operations. Manipulation of power series has several applications to numerical analysis, but perhaps its greatest use is the determination of asymptotic expansions (as we have seen in Section 1.2.11.3), or the calculation of quantities defined by certain generating functions. The latter applications make it desirable to calculate the coefficients exactly, instead of with floating point arithmetic. All of the algorithms in this section, with obvious exceptions, can be done using rational operations only, so the techniques of Section 4.5.1 can be used to obtain exact results when desired. The calculation of W(z) = U(z) f V( z ) is, of course, trivial, since we have W, = U,fV, for n = 0, 1, 2, . . . . It is also easy to calculate W(z) = U(z)V(z), using the familiar Cauchy product rule : (2) The quotient W(z) = U(z)/? (z), when VO # 0, can be obtained by inter- changing U and W in (2); we obtain the rule w, = u, - c wkvn-k VO >/ ( O