_EDIT_ I'd like to do this to $d$ digits of precision.
I wonder what the fastest way to get roots of a value on the unit circle is. More specifically, if I have a fraction of naturals, $p/q$, and natural $n$, what is the fastest way to find
I'm considering using lookup tables and such. I guess that I need the answers to be in the form $a+bi$, where $a$ and $b$ are in exponential notation form. I want to know what method takes the least amount of memory and time.
To summarize, I'm interested in the best asymptoticly performing method in terms of time and memory.