I am learning about the Fast Fourier Transform, which converts a polynomial from its coefficient representation into its point-wise form using divide-and-conquer. The Fast Fourier Transform evaluates a polynomial of degree 'n' at 'n' distinct points. The 'n' distinct points are the 'nth' roots of unity.

I know that a root of unity is a complex number that when raised to some positive integer power 'n' is equal to 1. However, I am not sure what is the advantage of using roots of unity in the Fast Fourier Transform. Any insights are appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.