# 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.

-

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.

-
@Paul: I didn't think about this very much. I'm wondering, in this case, what the fastest numerical methods for sine and cosine are, when needing a high precision. – Matt Groff Mar 23 '11 at 0:55
If you need to do this in arbitrary precision (so you can't just rely on the sin and cos instructions built into your FPU), the Maclaurin series is probably your best bet; run it out to 20 terms and your remaining error is on the order of $1/39!$, which is probably small enough for whatever you're doing. – Paul Z Mar 23 '11 at 1:07
@Paul: Thanks! I want to be certain, though... I'm really interested in extreme cases, so perhaps someone knows some special method for this... – Matt Groff Mar 23 '11 at 1:11
@Matt; How many digits do you want? – Carl Brannen Mar 23 '11 at 1:42
@Carl Brannen: I'm working on an algorithm, trying to determine the asymptotic limits - so really, as many as I can get - the extreme example! (even realistically, I may need at least millions) – Matt Groff Mar 23 '11 at 1:45

(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".

-