1
$\begingroup$

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

2 Answers 2

2

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.

  • 0
    @Matt; Cool, that means that you want to avoid cosines and sines like the plague (not that I see how). And addition is much much cheaper than multiplication. By the way, you don't have to spell out my name. "@car" works just as well.2011-03-23
0

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