{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 33 "Evaluation of a polynomial points" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "N:=6;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "f:=randpoly(x,degree=N-1,dense);" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "fh:=convert(f,horner);" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "subs(x=3,fh);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "subs(x=4,fh);" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 298 "If we have a polynomial f of degree < N, then we \+ can evaluate it at a point x=P with O(N) additions and O(N) multiplica tions if we first bring the polynomial in Horner form. Now we will con sider a polynomial of degree " 0 "" {MPLTEXT 1 0 34 "Points:=[seq(ithprime(i),i=1..N)];" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 118 "To evaluate f at all of these points would cos t: there are O(N) points, and each point costs O(N), so it costs O(N^2 )." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "Values:=[seq(subs(x=i ,fh),i=Points)];" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 112 "Now we will \+ keep Points the same for a while, and we'll consider how the Values de pend on the coefficients of f." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "Coeffs:=[seq(coeff(f,x,i),i=0..N-1)];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "A:=linalg[vandermonde]([p1,p2,p3]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "A:=linalg[vandermonde](Points);" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "evalm(A &* Coeffs);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 123 "So, we can get the Values at the Points from the Coeffs \+ by a linear map A, where A is the Vandermonde matrix of the Points." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 124 "The mat rix A is the map that, given the vector of coefficients of f, produces the vector of values of f at the given Points." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 59 "We'll think of matrix A a s \"evaluation of f at the points\"." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 245 "Then the inverse of A is then of cours e: \"interpolation at the points\". For example, if a polynomial g of \+ degree " 0 "" {MPLTEXT 1 0 26 "Values:=[seq(i^2,i=1..N )];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "B:=evalm(A^(-1)):" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "Coeffs:=evalm(B &* Values) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "g:=add(Coeffs[i+1]*x^i ,i=0..N-1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "[seq(subs(x= i,g),i=Points)];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 112 "So, if we keep the Points fixed, \+ and we've computed A and B:=A^(-1) then we can evaluate at the points \+ by doing:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "Values:=evalm(A &* Coeffs);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 162 "And, when we are given the Values at the Points, then we can interpolate, i.e. find the corresponding polynomi al that takes these values at those points by doing:" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "Coeffs:=evalm(B &* Valu es);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 337 " When A and B are known then this matrix*vector product costs O(N^2) . \+ So, we are lead to believe that evaluating or interpolating a polynomi al of degree < N at N points costs O(N^2). However, when the Points ar e chosen in a very special way, we will see that it can be done faster ! That is what is called FFT, the Fast Fourier Transform." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "The idea is the fo llowing:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "f_even := add(c oeff(f,x,2*i)*x^(2*i),i=0..iquo(N,2));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "f_odd := add(coeff(f,x,2*i+1)*x^(2*i+1),i=0..iquo(N,2 ));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f0:=f_even;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "f1:=expand(f_odd/x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "F0:=rem(f0,x^2-X,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "F1:=rem(f1,x^2-X,x);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 266 "Now we have to evaluate f_even an d f_odd at the points Points=[p1,p2,...], then add them, and we get th e values of f at those points. We're almost done once we have computed the values of f0 and f1 at those points (the values of f1 still need \+ to be multiplied by x)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "Now f0 and f1 are even functions, f0(p)=f0(-p)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 259 "Lets ass ume for now that N is even, N=2*n, and that the set \{ p.(n+1)..p.(2*n ) \} is the set you get from \{p.1 .. p.n\} when you multiply everythi ng by -1 (this does not hold for the Points we took in our example ab ove, so that is not a good choice of points)." }}{PARA 0 "" 0 "" {TEXT -1 155 "In that case we only need to evaluate f0 and f1 at half \+ of the points, namely p1..pn. This is the same as evaluating F0 and F1 at the points p1^2 ... pn^2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 373 "To gain more than a factor of 2 in speed up, we should be able to do the same trick again, we should be able to evaluate F0 and F1 very fast at the points p1^2 .. pn^2. In order to \+ do this fast, we want that again n is a multiple of 2, say n=2*m, and \+ that the second half of the points equals -1 times the first half of t he points. This can be achieved in the following way:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 123 "Let N be a power of 2 . Let omega be a primitive root of unity, so N is the smallest integer such that omega^N=1. Then take:" }}{PARA 0 "" 0 "" {TEXT -1 39 " Poi nts := [seq( omega^i , i=0..N-1)];" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 151 "By doing the tricks mentioned above, a p olynomial f of degree " 0 "" {MPLTEXT 1 0 481 "FFT:=proc(f, omega, N,x)\n # f must have degree " 0 "" {MPLTEXT 1 0 5 "N:=8;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "omega:=evalf(exp(2*Pi*I/N));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "f:=randpoly(x,degree=N-1,dense);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "FFT(f,omega,N,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "Points:=[seq(omega^i,i=0..N-1)];" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "[seq(subs(x=i,f),i=Points)]; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 150 "inverse_FFT:=proc(L, o mega, N, x)\n local i,Coeffs;\n Coeffs:=FFT(add(L[i]*x^(i-1),i=1..N) , 1/omega, N, x);\n 1/N * add(Coeffs[i]*x^(i-1),i=1..N)\nend;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "FFT(f,omega,N,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "inverse_FFT(%,omega,N,x);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 11 "evalf(%-f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "`The error is`=max(op(map(abs,\{coeffs(%,x)\})));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 311 "We see that computing an inverse FFT is \+ the same as computing an FFT with 1/omega instead of omega, and you ha ve to divide the result by N. The reason that this works is the follow ing. Recall that FFT is evaluation at Points=[omega^0,omega^1,...], an d that this corresponds to the linear map given by the matrix" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "A=vanderm onde(Points)=vandermonde([omega^0,omega^1,...])." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 136 "Now inverse_FFT is inter polation and corresponds to A^(-1). It is not hard to show that if ome ga is a primitive N'th root of unity then:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 129 "A^(-1) = 1/N * vandermonde([ ( 1/omega)^0, (1/omega)^1, ... ]) (for a proof see the book, but first try to prove this yourself!)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 94 "This formula for A^(-1) tells you precise ly how to do the inverse FFT. Let's do some examples." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "f:=randpoly(x,degree=50,dense);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "g:=randpoly(x,degree=70,dense);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "N:=128;" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 40 "Digits:=15; # set accuracy at 15 digits." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "omega:=evalf( exp(2*Pi*I/N) \+ );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "values_f := FFT(f,ome ga,N,x):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "values_g := FFT (g,omega,N,x):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 80 "These are the v alues of f and g at the Points [omega^0,omega^1,...,omega^(N-1)]." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "values_pr := [seq(values_f[i ]*values_g[i],i=1..N)]:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " pr:=inverse_FFT(values_pr,omega,N,x):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 102 "Now pr should be approximately equal to f*g. Lets comput e the largest error in the coefficients of pr." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 43 "max(op(map(abs,[coeffs(expand(pr-f*g))])));" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 190 "Note that we do not need such high accuracy, as long a s we are certain that the errors are smaller than 0.5 then we can alwa ys obtain the product f*g from pr by rounding of the coefficients." }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "Digits:=10; # the default \+ value." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "f:=randpoly(x,deg ree=250,dense):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "g:=randp oly(x,degree=250,dense):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " N:=512;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "omega:=evalf( ex p(2*Pi*I/N) );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "values_f: =FFT(f,omega,N,x):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "value s_g:=FFT(g,omega,N,x):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "v alues_pr:=[seq(values_f[i]*values_g[i],i=1..N)]:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "pr:=inverse_FFT(values_pr,omega,N,x):" } {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 187 "The following co mmand applies the command round (=round to nearest integer) to all coe fficients, and since our approximation of the product has errors < 1/2 we will get the exact product." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "PR:=collect(pr,x,round):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "evalb( PR = expand(f*g) );" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 270 "Maple also has the commands FFT and iFFT (inverse FFT) . You can combine these commands with the Maple command \"evalhf\" (EV ALuate with Hardware Floatinging point computations). Then the computa tion will use machine floating points and the computation will be much faster." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 815 "We have seen that FFT can be used for multiplying polynomials in \+ Z[x]. The complexity is better than the O(N^2) for the usual multiplic ation or the O(N^(log(3)/log(2))) for Karatsuba multiplication. So eve ntually, if the degree is high enough, the FFT multiplication method s hould be faster than Karatsuba. The difficulty in making FFT fast is i n the number omega. The integers Z or rational numbers Q do not contai n primitive N'th roots of unity for N>2. Therefore we need to compute \+ not in Z or Q but in a field that does contain these N'th roots, such \+ as the complex numbers C, approximated by floating point numbers. To g et a complete implementation of multiplication in Z[x] based on FFT is not easy, one needs know for example with how many Digits the computa tion should be done for the result to be reliable." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 110 "Now C is not the only fi eld that contains N'th roots of unity where N is a large power of 2. T ake for example:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "p:=2^16 +1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "isprime(p);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "N:=2; prim_root[N]:=-1 mod p ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "v:=( Factors(x^2-prim _root[N]) mod p )[2];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 352 " while nops(v)=2 do\n # Apparantly prim_root[N] is a square in Fp, so \n # we can compute a square root using the Factors mod p\n # comm and.\n N:=N*2;\n # Pick the smallest root alpha (the other one is \+ -alpha\n # which is equivalent to p-alpha).\n prim_root[N] := min( x-v[1][1],x-v[2][1]) mod p;\n v:=( Factors(x^2-prim_root[N]) mod p \+ )[2];\nod;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "N;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "omega:=prim_root[N];" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "Power(omega,N/2) mod p;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "Power(omega,N) mod p;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 395 "FFT_modp:=proc(f, omega, N, x,p)\n local Even,Odd,Powers,i;\n if N=1 then RETURN([f]) fi;\n Eve n:=procname( add(coeff(f,x,2*i )*x^i,i=0..N/2),omega^2 mod p,N/2,x,p) ;\n Odd :=procname( add(coeff(f,x,2*i+1)*x^i,i=0..N/2),omega^2 mod p, N/2,x,p);\n Powers := powers_omega(omega,N,p);\n Odd := [seq(Odd[i]* Powers[i],i=1..N/2)];\n [seq(Even[i]+Odd[i],i=1..N/2),seq(Even[i]-Odd [i],i=1..N/2)] mod p\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 106 "powers_omega:=proc(omega,N,P)\n local i;\n options remember;\n \+ [seq(Power(omega,i) mod p,i=0..N/2-1)]\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 176 "inverse_FFT_modp:=proc(L, omega, N, x,p)\n loc al i,Coeffs;\n Coeffs:=FFT_modp(add(L[i]*x^(i-1),i=1..N), 1/omega mod p, N, x,p);\n 1/N * add(Coeffs[i]*x^(i-1),i=1..N) mod p\nend;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "f:=randpoly(x,degree=200,den se) mod p:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "g:=randpoly(x ,degree=300,dense) mod p:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 122 "To \+ compute the product pr = f*g we need to have N=some power of 2 and N>d egree(pr,x). We can do that in the following way:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 59 "N:=2^ceil(simplify(log(degree(f,x)+degree(g, x)+1)/log(2)));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "values_f :=FFT_modp(f,prim_root[N],N,x,p):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "values_g:=FFT_modp(g,prim_root[N],N,x,p):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "values_pr:=[seq(values_f[i]*values_ g[i],i=1..N)] mod p:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "pr: =inverse_FFT_modp(values_pr,prim_root[N],N,x,p):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "Expand(f*g - pr) mod p; # This should be 0." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 345 "In principle the method sketch ed above is very fast. We still don't beat the speed of Expand mod p i n this example though. We probably have quite a bit of overhead in han dling our lists and polynomials. To make it faster one would have to i mplement this more carefully, avoiding the unnecessary construction of so many new polynomials and lists." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 841 "One other remark about the efficiency h ere is that all our integers are of the type longint, they're the type of integers that can get arbitrarily many digits. Integers that could be of arbitrary size are complicated datastructures, and therefore th ey are not as fast as the integers one has in a computer language such as C. In C and most other languages the integers have some a priori b ound (so they're not really integers, they're in fact integers modulo \+ some power of 2), making them much easier (read: faster) to handle. H owever, since we're computing modulo p we know a priori that the integ ers never get larger than p. So it would be better to use a faster dat atype for our integers in this code. Maple has a special datastructure for polynomials with coefficients modulo p, but the syntax is rather \+ awkward so I won't go into that." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 134 "The conclusion is that with FFT we can i n principle multiply polynomials very fast, if you would implement it \+ in a language such as C." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 172 "Note that multiplication in Z[x] and in Z are rel ated problems. I'll illustrate that with an example. Let's say we have some large number, and we write it out on base beta." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "beta:=1000;" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 13 "A:=123456789;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "B:=987654321;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "FA:=123*x^2+456*x+789;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "FB:=987*x^2+654*x+321;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "A*B;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "expand(FA*FB );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "subs(x=1000,%);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "As you can see, the problem of mul tiplying A and B can be reduced to multiplying polynomials." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "The converse is also true, you can reduce multiplying polynomials to multiplying inte gers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "f:=12*x^3 + 23*x^2 + 34*x + 45;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "g:=54*x^3 \+ + 43*x^2 + 32*x + 21;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "If := 12002300340045;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "Ig : = 54004300320021;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "If*Ig; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "sort(expand(f*g),x);" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 339 "So if you have an asymptoticall y fast algorithm for multiplication in Z[x] (i.e. an algorithm with \+ a good complexity O(f(n)) where f(n) is a function that grows slowly) \+ then you have an asymptotically fast algorithm for multiplication in Z , and vice versa. The FFT method for multiplying integers is called th e Schonhage-Strassen method." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 71 "Read section 3.3 in the book for more details a nd complexity estimates." }}}}{MARK "110 2 0" 71 }{VIEWOPTS 1 1 0 1 1 1803 }