La forma más rápida de encontrar las raíces (naturales) de un valor en el círculo unitario

Question

_ EDITAR _ Me gustaría hacer esto a $d$ dígitos de precisión.

Me pregunto cuál es la forma más rápida de obtener las raíces de un valor en la circunferencia unitaria. Más concretamente, si tengo una fracción de naturales, $p/q$ y natural $n$ ¿Cuál es la forma más rápida de encontrar

$\sqrt[n]{e^{i(2\pi)p/q}}$

Estoy considerando usar tablas de búsqueda y demás. Supongo que necesito que las respuestas sean de la forma $a+bi$ , donde $a$ y $b$ están en forma de notación exponencial. Quiero saber qué método requiere la menor cantidad de memoria y tiempo.

Resumiendo, me interesa el método que mejor funcione asintóticamente en términos de tiempo y memoria.

Answer 1

Siempre tienes $$ \sqrt[n]{e^{i(\theta + 2k\pi)}} = e^{i(\theta/n + 2k\pi/n)}.$$ Así que la respuesta sólo implica una pequeña división y luego una $\sin$ y $\cos$ . Me cuesta creer que puedas hacerlo mejor que esto.

Answer 2

(demasiado largo para un comentario)

Como la cuestión de cómo evaluar las funciones trigonométricas surgió en los comentarios, voy a esbozar un método útil que implica la reducción a la mitad y la duplicación.

La idea es dividir el argumento $z$ de sus funciones trigonométricas por un número $2^n$ , de tal manera que $z^\prime=\left|\frac{z}{2^n}\right|$ es lo suficientemente "diminuto" (es decir, la repetición de la mitad). Pero, ¿cómo de pequeño es "pequeño"? Bueno, lo suficientemente pequeño como para evaluar $s^\prime=\sin\;z^\prime$ y $c^\prime=\cos\;z^\prime$ puede hacerse con mucha precisión mediante series de Maclaurin o aproximaciones de Padé. Con estas aproximaciones, se puede hacer la fase de "duplicación" utilizando las fórmulas del ángulo doble $s=2c^\prime s^\prime$ y $c=2{c^\prime}^2-1$ $n$ tiempos. Tendrás que experimentar si debes usar series de Maclaurin o aproximaciones de Padé (en mis limitados experimentos, las aproximaciones de Padé suelen dar mejores resultados), qué grado deben tener tus aproximaciones y cuán diminuto es "diminuto".