However, in order to avoid duplication of code-since integer FFT multiplication is very similar-we implement the function generalFFTMultiply, which will be used in both cases. These ideas can be incorporated in an algorithm to do just polynomial multiplication. This is exactly what we obtained with the classical multiplication. Interpolating the result with InverseFourier and taking care of the scaling factor, we obtain the coefficients of the product polynomial. Recall, from Definition 1 and the verification following it, that what we have done here is equivalent, within a scaling factor, to evaluating each polynomial at the points (where, ) and pointwise multiplying the results. We next apply Fourier to these two lists and pointwise multiply the results. Having fixed the value of, we then form the lists of coefficients of and -padding them with zeros until their lengths equal 8. Keeping in mind that FFT works best for inputs which are powers of 2, we consider the degree of the product to be less than. We will now compute this product using FFT. Suppose we are given the two polynomials and, whose product we want to compute. The multipoint evaluation is performed with FFT as implemented by the function Fourier, whereas interpolation is performed with the inverse FFT, implemented by the function InverseFourier.Įxample 2. Namely, evaluate the two input polynomials, multiply the results pointwise, and interpolate to get the product polynomial. Therefore, a fast way of doing multipoint evaluation and interpolation leads to a fast polynomial multiplication algorithm. Hence, the cost of polynomial multiplication in the value representation is linear in the degree, whereas in the list of coefficients representation we do not know how to multiply in linear time. To wit, if and are the values of two polynomials and, evaluated at distinct points, with, then the values of the product at those points are. The reason for considering the value representation is that multiplication in that representation is easy. It is well known that a polynomial of degree less than over an integral domain, such as the integers or the rationals, can be represented either by its list of coefficients, taken in reverse order here, or by a list of its values at distinct points, where for we have is a primitive root of unity. We begin by discussing a topic that is well known and much talked about, but for which there is little, if any at all, “hands-on” experience. Note that we have reversed the order of and appended its first 3:įast Fourier Transform for Fast Polynomial and Integer Multiplication Take successive inner products of the first row of the table with each one of the following rows.Use Mathematica‘s function ListConvolve.Therefore, we obtain the same result with these three methods.
0 kommentar(er)
