Cómo implementar la fórmula de de Moivre en matemáticas enteras

Answer 1

Me sorprendió un poco caracterizar la fórmula de De Moivre como una aceleración en el cálculo; veamos si podemos calcular la cantidad de multiplicaciones que está guardando.

Si [math] z [/ math] es un número complejo, entonces podemos escribirlo como [math] r (\ cos \ theta + i \ sin \ theta) [/ math], entonces [math] z ^ n = r ^ n (\ cos \ theta + i \ sin \ theta) ^ n = r ^ n (\ cos n \ theta + i \ sin n \ theta) [/ math].

Multiplicar dos números complejos requiere tres multiplicaciones (ver Multiplicar dos números complejos usando solo tres multiplicaciones de números reales) No creo que la cuadratura pueda reducir esto aún más. Entonces, el cálculo directo a una [matemática] n [/ matemática] que es una potencia de 2 toma multiplicaciones de [matemática] 3 \ log_2 n [/ matemática] a través de la cuadratura repetida. (Para la no potencia de dos, agregue otras 3 multiplicaciones por cada bit adicional en [matemáticas] n [/ matemáticas] que se establece …)

¿Cuántas multiplicaciones se necesitan para convertir [matemáticas] a + bi [/ matemáticas] en [matemáticas] (r, \ theta) [/ matemáticas]? Si tenemos tablas de búsqueda súper eficientes para el arcotangente, entonces todavía se requiere cuadrar [matemáticas] a [/ matemáticas] y [matemáticas] b [/ matemáticas], y dividirlas. Luego tomamos multiplicaciones [math] \ log_2 [/ math] para elevar r a la potencia correcta, y tenemos que multiplicar [math] \ theta [/ math] por [math] n [/ math] también, más otras multiplicaciones después de nuestra búsqueda supuestamente súper rápida [math] \ sin [/ math] y [math] \ cos [/ math].

Entonces, las multiplicaciones [math] 3 \ log_2 n [/ math] son ​​definitivamente más lentas que las multiplicaciones [math] \ log_2 n + 5 [/ math] + una división + tres funciones trigonométricas de tiempo constante si dejamos [math] n [/ las matemáticas] se vuelven lo suficientemente grandes. Pero si [math] n [/ math] es grande, entonces estamos perdiendo precisión en nuestras funciones trigonométricas rápidas basadas en la búsqueda de tablas. ¿Cuánto cuesta hacerlo con precisión calculando tantos bits de las funciones trigonométricas como necesitemos?

Si usamos un algoritmo como CORDIC – Wikipedia, entonces tenemos que hacer dos multiplicaciones por iteración (más algunos cambios y sumas) y necesitamos tantas iteraciones como bits en [math] r ^ n [/ math]. Este es un impuesto pesado, porque ese número de iteraciones puede estimarse como [math] \ log_2 r ^ n [/ math] [math] = n \ log_2 r [/ math] y [math] O (n) [/ matemáticas] multiplicaciones es mucho peor que [matemáticas] O (\ log n) [/ matemáticas].

Entonces, de Moivre realmente solo nos da una aceleración si estamos satisfechos con que los “pocos” bits superiores sean correctos. (Tal vez hasta 64 usando la implementación incorporada de un procesador Intel.) Si esa es toda la precisión entera que necesitamos, entonces la conversión a punto flotante y viceversa seguido de redondeo también funcionará para los enteros gaussianos. Pero los intentos de calcular suficientes bits de precisión en [matemática] \ sen n \ theta [/ matemática] y [matemática] \ cos n \ theta [/ matemática] frustrarán cualquier intento de obtener una aceleración para grandes [matemática] n [/ matemáticas].

Answer 2

[matemáticas] \ def \ cis {\ textrm {cis} \,} e ^ {i \ theta} = \ cis \ theta = \ cos \ theta + i \ sin \ theta [/ math]

La forma [matemática] \ cis [/ matemática] es interesante porque son esencialmente coordenadas polares, [matemática] \ theta [/ matemática] en el círculo unitario, pero escrita como una conversión abreviada a coordenadas rectangulares [matemática] \ cos \ theta + i \ sin \ theta. [/ math]

De Moivre dice

[matemáticas] (\ cos \ theta + i \ sin \ theta) ^ n = \ cos (n \ theta) + i \ sin (n \ theta) [/ math]

[matemáticas] \ cis ^ n \ theta = \ cis (n \ theta) [/ matemáticas]

Escrito en notación exponencial, no es tan impresionante:

[matemáticas] (e ^ {i \ theta}) ^ n = e ^ {i (n \ theta)} [/ matemáticas]

De todos modos, como dije, [matemáticas] \ cis [/ matemáticas] es realmente coordenadas polares, un ángulo en el círculo unitario. Para usarlo para hacer una exponenciación de números complejos expresados ​​rectangularmente, necesitamos tomar el arcotangente de cuatro cuadrantes, que no es trivial computacionalmente y, en general, solo dará una aproximación a algo que tiene una respuesta entera exacta. En otras palabras, no es particularmente útil.

Probablemente la mejor manera de calcular [matemáticas] z ^ n [/ matemáticas], una gran potencia entera de un entero gaussiano, es formar la tabla [matemáticas] (k, z ^ {2 ^ k}) [/ matemáticas] por cuadratura repetida, [matemáticas] z, z ^ 2, (z ^ 2) ^ 2 = z ^ 4, z ^ 8, z ^ {16}… [/ matemáticas] hasta [matemáticas] k = \ log_2 n. [ / math] Eso requiere [math] \ log n [/ math] multiplicaciones complejas. Luego multiplicamos los que corresponden a cada bit en la representación binaria de [math] n [/ math] para obtener [math] z ^ n, [/ math] hasta [math] \ log n [/ math] más Se utilizan multiplicaciones. En total, tenemos un algoritmo de exponenciación complejo [matemático] O (\ log n) [/ matemático] eficiente.

Por supuesto, los enteros pueden crecer, por lo que no podemos suponer un tiempo constante para su aritmética si queremos precisión.

Answer 3

¿Estás suponiendo que la exponenciación de los enteros es O (1)? Esto es necesariamente una abstracción; los enteros pueden ser arbitrariamente grandes y, por lo tanto, incluso el tiempo para escribirlos también lo hace …

Si la exponenciación o algo así no se da como una primitiva mágica, entonces incluso si la multiplicación se considera O (1), x ^ n toma tiempo proporcional a log (n) para calcular, mediante “cuadratura repetida” o similar.

Y de la misma manera, también podemos calcular (a + bi) ^ n en tiempo proporcional a log (n), mediante “cuadratura repetida” o similar.

Si la exponenciación de enteros se da como una primitiva mágica, dudo que sea posible usarla para acelerar este cálculo, pero aún no tengo una prueba de esto.