1
$\begingroup$

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.

$\endgroup$

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.