¿Cuáles son algunos algoritmos rápidos para calcular la enésima potencia de un número?

Necesitamos saber si [math] x [/ math] y [math] n [/ math] son ​​enteros.

Si [math] x [/ math] es un número de punto flotante, entonces su hardware puede proporcionar una implementación lo suficientemente buena. De lo contrario, puede calcular el problema con suficiente precisión utilizando la identidad:

[matemáticas] x ^ n = e ^ {(n \ log x)} [/ matemáticas]

o quizás

[matemáticas] x ^ n = 2 ^ {(n \ log_2 x)} [/ matemáticas]

Esta es su mejor opción incluso cuando el número de bits deseado excede la precisión del hardware. Puede usar la serie Taylor para calcular el logaritmo y el exponente con suficientes dígitos de precisión. (Lamentablemente, no puedo ofrecer consejos específicos para optimizar estos cálculos numéricos).

Si tanto [math] x [/ math] como [math] n [/ math] son ​​enteros de precisión arbitraria, entonces la exponenciación mediante cuadratura repetida es el mejor método cuando se requiere una respuesta exacta. Sin embargo, se debe usar un algoritmo de multiplicación optimizado cuando los números se vuelven grandes, lo que en sí mismo es un problema de implementación no trivial.

Si observa la implementación de la biblioteca GNU Multi-Precision de exponenciación de enteros (ver aquí: 214bcc98bbab mpz / n_pow_ui.c) ¡es mucho más complicado que un solo ciclo! Hay optimizaciones para evitar la copia y la asignación de memoria, y preprocesar cualquier parte “fácil” de la computación. Pero, en última instancia, se reduce a la cuadratura repetida (pero este es solo uno de los tres bucles posibles, dependiendo de las multiplicaciones optimizadas disponibles).

  para (; i> = 0; i--)
	     {
	       TRACE (printf ("mul_2 loop i =% de = 0x% lX, rsize =% ld ralloc =% ld talloc =% ld \ n",
			      i, e, rsize, ralloc, talloc);
		      mpn_trace ("r", rp, rsize));

	       MPN_SQR (tp, talloc, rp, rsize);
	       SWAP_RP_TP;
	       if ((e & (1L << i))! = 0)
      		 MPN_MUL_2 (rp, rsize, ralloc, mult);
	     }

Esta pregunta lleva a una pequeña teoría absolutamente encantadora que todos deberían conocer (y todos sabrían si todos leen el TAOCP de Knuth de principio a fin, como todos deberían saber).

Digamos que te doy un número [matemática] x [/ matemática] y te pido que calcules [matemática] x ^ {10} [/ matemática]. A su disposición hay algunos artilugios que pueden calcular productos, pero cada cálculo de un producto le cuesta algo: un brazo, una pierna o unos pocos milisegundos. No importa, siempre que estemos de acuerdo en que su objetivo es simplemente minimizar el número de multiplicaciones .

Entonces. ¿Qué haces?

Una solución muy razonable es la siguiente: primero calcule [math] x ^ 2 [/ math] multiplicando [math] x \ times x [/ math]. Luego multiplique [math] x ^ 2 [/ math] por sí mismo para obtener [math] x ^ 4 = x ^ 2 \ times x ^ 2 [/ math]. Luego haga esto nuevamente para obtener [matemáticas] x ^ 8 = x ^ 4 \ veces x ^ 4 [/ matemáticas]. Ahora para obtener [matemáticas] x ^ {10} [/ matemáticas], todo lo que necesita es multiplicar [matemáticas] x ^ 8 [/ matemáticas] por [matemáticas] x ^ 2 [/ matemáticas], que afortunadamente ya hemos calculado . Así que logramos encontrar [matemáticas] x ^ {10} [/ matemáticas] usando cuatro multiplicaciones:

1. [matemáticas] x [/ matemáticas] (dado)
2. [matemáticas] x ^ 2 = x \ veces x [/ matemáticas]
3. [matemáticas] x ^ 4 = x ^ 2 \ veces x ^ 2 [/ matemáticas]
4. [matemáticas] x ^ 8 = x ^ 4 \ veces x ^ 4 [/ matemáticas]
5. [matemáticas] x ^ {10} = x ^ 8 \ veces x ^ 2 [/ matemáticas].

Pensemos en lo que está pasando aquí. Vemos que realmente no importa qué [matemática] x [/ matemática] sea: podría ser grande, pequeño, un número entero, un número de coma flotante, una matriz grande o cualquier otra cosa que podamos multiplicar. (Para las matrices hay atajos útiles, como diagonalizarlos primero o triangular. Pero esto está fuera de nuestra principal preocupación aquí).

Lo único que importa es la secuencia de exponentes en nuestro cálculo, donde en cada paso producimos un nuevo exponente que es la suma de dos exponentes calculados previamente. El punto de partida es simplemente [matemáticas] 1 [/ matemáticas].

1. [matemáticas] 1 [/ matemáticas] (dado)
2. [matemáticas] 2 = 1 + 1 [/ matemáticas]
3. [matemáticas] 4 = 2 + 2 [/ matemáticas]
4. [matemáticas] 8 = 4 + 4 [/ matemáticas]
5. [matemáticas] 10 = 8 + 2 [/ matemáticas]

La secuencia [matemáticas] 1,2,4,8,10 [/ matemáticas] se llama una cadena de adición que termina en [matemáticas] 10 [/ matemáticas]. Una cadena de suma es solo una secuencia de números, comenzando con [math] 1 [/ math], donde cada número es la suma de dos (no necesariamente distintos) números anteriores en la secuencia. La longitud de la cadena es cuántos números tiene, excluyendo el [math] 1 [/ math] al principio (ya que lo tenemos gratis). En otras palabras, la longitud es solo el número de pasos de suma que debemos seguir (o pasos de multiplicación en el cálculo de [matemáticas] x ^ n [/ matemáticas]).

El desafío de calcular la eficiencia [matemática] x ^ n [/ matemática] ahora se ve simplemente como esto: encontrar la cadena de suma más corta posible que termine en [matemática] n [/ matemática]. La longitud de esta cadena óptima se llama [math] l (n) [/ math].

El número [matemática] 10 [/ matemática] también se puede lograr a través de [matemática] 1,2,4,5,10 [/ matemática], donde en lugar de doblar con avidez la [matemática] 4 [/ matemática] para obtener [matemática] ] 8 [/ math] hemos agregado [math] 4 [/ math] y [math] 1 [/ math] para obtener [math] 5 [/ math]; este “sacrificio” se pagó en el siguiente paso donde pudimos duplicar [math] 5 [/ math] para aterrizar directamente en [math] 10 [/ math]. Puedes convencerte de que no hay forma de llegar a [matemáticas] 10 [/ matemáticas] con menos pasos. Entonces [matemáticas] l (10) = 4 [/ matemáticas].

Pero, ¿cuál es la cadena más corta posible para [matemáticas] 23 [/ matemáticas]? Para [matemáticas] 191 [/ matemáticas]? Para [matemáticas] 3 ^ {1729} [/ matemáticas]?

El paso más eficiente en una cadena de suma es duplicar , que es simplemente multiplicar el elemento anterior por [math] 2 [/ math]. Las secuencias para [math] 10 [/ math] contienen principalmente duplicaciones, y hay una manera fácil de usar la representación binaria de un número para crear una cadena de suma para ese número que tenga muchas duplicaciones: escriba el número en binario; quite el “1” más a la izquierda; reemplace cada “1” con una “D1” y cada “0” con una “D”; e interpretar el resultado como una cadena donde “D” significa “doble” y “1” significa “sumar 1”.

Por ejemplo, para hacer [matemática] 21 [/ matemática], escriba [matemática] 21 = 10101_2 [/ matemática], borre la [matemática] 1 [/ matemática] para obtener [matemática] 0101 [/ matemática] e interprete esto como [matemática] D D1 D D1 [/ matemática] que significa “doble, doble, agregue uno, doble, doble, agregue uno”. De hecho, [matemáticas] 1,2,4,5,10,20,21 [/ matemáticas] es una cadena de adición para [matemáticas] 21 [/ matemáticas], y es la mejor posible.

Este “método binario” es bastante eficiente, y Knuth señala que algunas personas realmente afirmaron que siempre produce la cadena de adición más eficiente. Pero esto es falso. Ya es falso para [math] 15 = 1111_2 [/ math], donde el método binario lleva a [math] 1,2,3,6,7,14,15 [/ math] pero puedes hacerlo mejor: [math ] 1,2,3,6,12,15 [/ matemáticas].

(Buen ejercicio de codificación: escriba un programa que calcule una cadena de suma de la longitud más corta posible para un número dado [matemáticas] n [/ matemáticas] ).

Las cadenas de adición son increíblemente sutiles. Aquí hay algunas sorpresas mencionadas por Knuth:

• Una “cadena de estrellas” es aquella en la que cada número utiliza su predecesor inmediato. Esto parece algo muy razonable de hacer, y es natural suponer que siempre hay una cadena de estrellas que alcanza la longitud mínima. Pero esto no es verdad. El primer contraejemplo que conozco es [matemática] 2 ^ {6106} + 2 ^ {3048} + 2 ^ {2032} + 2 ^ {1016} +1 [/ matemática], un número bastante monstruoso. Esto fue descubierto por Hansen en 1958.
• Si ha encontrado la mejor cadena de suma para [matemática] n [/ matemática], es razonable esperar que la mejor cadena para [matemática] 2n [/ matemática] sea la mejor cadena para [matemática] n [/ matemática ] seguido de una duplicación. Una duplicación es, después de todo, el paso más eficiente. En otras palabras, la conjetura es que [matemáticas] l (2n) = l (n) +1 [/ matemáticas]. Pero esto no es verdad. La cadena de suma más corta posible para [matemática] 191 [/ matemática] tiene [matemática] 11 [/ matemática] pasos, entonces [matemática] l (191) = 11 [/ matemática], y sorprendentemente, [matemática] l (382) = 11 [/ matemáticas] también. Puede llegar a [matemáticas] 382 [/ matemáticas] en el mismo (!) Número de pasos que puede llegar a [matemáticas] 191 [/ matemáticas].

(Use su código para verificar esos reclamos).

Sección 4.6.3 en vol. 2 de “El arte de la programación de computadoras” de Knuth contiene un análisis muy detallado de la teoría de las cadenas de adición, como una excursión fuera del cálculo eficiente de [matemáticas] x ^ n [/ matemáticas]. Esas excursiones profundas y sorprendentes son una de las maravillas de esta increíble secuencia de libros.

Todavía hay varios problemas abiertos sobre las cadenas de adición y algunos algoritmos asociados muy inteligentes. Es sorprendente cómo un problema simple como calcular [matemáticas] x ^ n [/ matemáticas] de la manera más eficiente conduce a profundidades tan inesperadas.

Las respuestas existentes dan soluciones O (log (n)).

Sugeriría una solución rápida de O (1).
Muchas arquitecturas de CPU (y casi todas las arquitecturas de coprocesador matemático) tienen instrucciones para calcular logaritmos a base 2 (oe o 10) y exponenciación de 2 (oe o 10) en estándares de punto flotante IEEE.

Entonces, si desea calcular A = x ^ n, todo lo que tiene que hacer es calcular B = log (x), calcular C = n * B y luego calcular A = exp (C).
Esto es O (1) siempre que la CPU tenga el soporte.

Sugeriría cuadratura recursiva, es así:

[matemáticas] f (x) = x ^ n = \ left \ {
\ begin {array} {ll}
(x ^ {n / 2}) (x ^ {n / 2}) & \ quad n = 0 (mod 2) \\
x (x ^ {\ frac {n-1} {2}}) (x ^ {\ frac {n-1} {2}}) & \ quad n \ neq0 (mod 2)
\ end {array}
\ right. [/ math]

Cada ronda, el tamaño del problema disminuye a la mitad, lo que hace que la complejidad .

Ya existen algunas buenas respuestas en esta pregunta: ¿Cuáles son algunos algoritmos rápidos para calcular la enésima potencia de un número?

Esto, exponenciación por cuadratura.

PD: Corre aquí Página en ideone.com

Aquí está mi propuesta para mi propia pregunta, aunque no sé si es correcta:

Hay varias formas de hacerlo, obviamente, utilizando, por ejemplo, bucles o una función recursiva que se llama a sí misma. Una buena respuesta podría ser:

potencia de función (x, n)

si n == 0 entonces

potencia (x, n) = 1

si n% 2 == 0 entonces

potencia (x, n) = potencia (x, n / 2) * potencia (x, n / 2)

si n% 2 == 1 entonces

potencia (x, n) = x * potencia (x, n-1)

La sintaxis aquí simplemente tiene sentido para cualquier persona y no refleja ningún idioma. La idea es utilizar conjuntos de dos elementos.

– – – – – – = (- -) (- -) (- -)

¿Pero no podríamos usar menos conjuntos? ¿Y cómo afectaría eso a la complejidad?

– – – – – – = (- – -) (- – -)

Por ejemplo :

potencia de función (x, n)

si n == 0 entonces

potencia (x, n) = 1

si n% 3 == 0 entonces

potencia (x, n) = potencia (x, n / 3) * potencia (x, n / 3) * potencia (x, n / 3)

si n% 3 == 1 entonces

potencia (x, n) = x * potencia (x, n / 3)

si n% 3 == 2 entonces

potencia (x, n) = x * x * potencia (x, n / 3)

¿Es esto efectivo?

potencia de def (x, n):
si n == 0:
volver 1
elif n == 1:
volver x
elif n% 2 == 0:
potencia de retorno (x * x, n // 2)
más:
return x * power (x * x, (n-1) // 2)

Es posible que haya muchos bucles anidados con tal complejidad de tiempo. Vea si puede evitar el anidamiento y modificar la lógica del programa.

Un problema exponencial se puede optimizar a un algoritmo polinomial utilizando la memorización. Búscalo. Es parte integrante de las técnicas de programación dinámica.

Para todos los valores positivos de x:

Se busca: x ^ n

Buscar registro (x)

Calcular nLog (x)

Encuentra Antilog (nLog (x))