0
$\begingroup$

I had an algorithms tutorial today and I realized that many of my answers were incorrect, but any time I took the DFT and then DFT^-1 to find some real roots of a polynomial, I had the correct answer.

What I'm wondering is, why does my algorithms textbook define the nth roots of unity differently than, for example wikipedia and wolfram math world define it?

My textbook: Introduction to Algorithms, 3rd Edition

nth roots of unity: $e^{2\pi i\frac{k}{n}}$

Wikiedia, Wolfram Math World:

nth roots of unity: $e^{-2\pi i\frac{k}{n}}$

My question is, would complex roots of a polynomial turn out incorrect when calculated with this slightly different definition? What else should I look for? I'm sure it's different because the textbook even offers a roots of unity circle which counts upwards in the counter-clockwise direction (eg $\omega_4^1 = i$ instead of $-i$)

Regards,

$\endgroup$
0
$\begingroup$

Note that these two choices are complex conjugates of each other, so any real result you get out of your computations at the end of the day will be the same as long as you stick to one of the choices all the way.

Also, of course, it's the same set of roots of unity they define -- just numbered differently.


I'm not sure why you think Wikipedia has a minus there. Most of the instances on the current version of the Wikipedia article go counterclockwise, except for the "3rd roots of unity" illustration which (inexplicably) numbers them clockwise.

Mathworld, too presents only the form $e^{2\pi ik/n}$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.