Fastest way to find (natural) roots of a value on the unit circle _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
$\sqrt[n]{e^{i(2\pi)p/q}}$
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.
 A: You always have $$ \sqrt[n]{e^{i(\theta + 2k\pi)}} = e^{i(\theta/n + 2k\pi/n)}.$$ So the answer just involves a little division and then a $\sin$ and $\cos$. I'd have a hard time believing you can do better than this.
A: (too long for a comment)
As the question of how to evaluate trigonometric functions came up in the comments, I'll sketch one useful method involving halving and doubling.
The idea is to divide the argument $z$ of your trigonometric functions by a number $2^n$, such that $z^\prime=\left|\frac{z}{2^n}\right|$ is "tiny enough" (i.e., repeated halving). But how tiny is "tiny"? Well, tiny enough such that evaluating $s^\prime=\sin\;z^\prime$ and $c^\prime=\cos\;z^\prime$ can be done very accurately either by Maclaurin series or Padé approximants! With these approximations, one can then do the "doubling" phase by using the double angle formulae $s=2c^\prime s^\prime$ and $c=2{c^\prime}^2-1$ $n$ times. You'll have to experiment with whether you should use Maclaurin series or Padé approximants (in my limited experiments, Padé approximants usually gave better results), what degree should your approximants be, and how tiny is "tiny".
