sec numerical algorithms bottom half with suitable sign changes on some rows and columns likewise for the left and right halves an efficient divide and conquer algorithm exists to perform both the evaluation and the interpolation in th( log ntime this is called the discrete fourier transform (dftit is recursive function that decomposes the matrix multiplicationstaking advantage of the symmetries made available by doing evaluation at the nth roots of unity the algorithm is as follows fourier_transform(double *polynomialint /compute the fourier transform of polynomial /with degree polynomial is list of /coefficients indexed from to - is /assumed to be power of double even[ / ]odd[ / ]list [ / ]list [ / ]if ( == return polynomial[ ]for ( = <= / - ++even[jpolynomial[ ]odd[jpolynomial[ + ]list fourier_transform(evenn/ )list fourier_transform(oddn/ )for ( = <= - ++imaginary pow( * *pi* / ) ( / )polynomial[jlist [kz*list [ ]return polynomialthusthe full process for multiplying polynomials and using the fourier transform is as follows represent an -degree polynomial as coefficients[ an- perform fourier_transform on the representations for and pairwise multiply the results to get values perform the inverse fourier_transform to get the degree polynomial ab