¿Cuál es el algoritmo más rápido para realizar la exponenciación? Asumamos bases numéricas y exponentes naturales por simplicidad.¿Cuál es el algoritmo más rápido para realizar exponenciación?
¿Qué utilizaría una biblioteca matemática eficiente?
(Cuando lo busco, acabo de recibir los resultados relativos a los algoritmos que se ejecutan en tiempo exponencial.)
Para los pequeños exponentes Python usa exponenciación binaria (un tipo de exponenciación binaria), como puede verse en la línea 2874 de http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup&pathrev=65518
Para exponentes más grandes utiliza una exponenciación de 2^5 arios (un tipo alternativo de exponenciación por cuadratura).
Si solo le importan los dígitos más significativos del resultado, puede calcular muy rápidamente x^y = exp (y * log (x)).
Si solo le importan los dígitos menos significativos del resultado (por ejemplo, para un concurso de programación), entonces puede calcular el módulo exponente con algún valor M. Por ejemplo, el comando Python pow (x, y, 1000) calcule los últimos 3 dígitos de x con la potencia de y. Lo hace mediante el método de exponenciación por cuadratura, pero tenga en cuenta que esto puede ser mucho más rápido que calcular el resultado completo porque asegura que los números intermedios nunca sean mayores que M.
Como un toque adicional (si solo interesado en los dígitos menos significativos), puede usar el teorema de Euler http://en.wikipedia.org/wiki/Euler%27s_theorem para reducir el tamaño del exponente.
Si usted tiene un número natural dado uy una entrada dada m, para calcular T^M se podría aplicar el algoritmo siguiente
q = m;
prod = 1;
current = u;
while q > 0 do
if (q mod 2) = 1 then // detects the 1s in the binary expression of m
prod = current * prod; // picks up the relevant power
q--;
endif
current = current * current; // u^i -> u^(2*i)
q = q div 2
enddo
output = prod;
Así que, básicamente, si usted tiene, digamos, u^23 se Convierte 23 en binario -> 10111 (base 2) Luego obtienes u^23 = u^16 * u^4 * u^2 * u^1 (no u^8 ya que los 2 dígitos de izquierda a derecha son 0)
La complejidad es o (log (m)) u o (n), si se tiene en cuenta que n log (m) _10 + 1
El problema con todos los métodos binarios anteriores es que están limitados a enteros solamente. Si por "exponenciación" quiere decir calcular la función e^x, lo mejor que he visto es series de potencias que convergen rápidamente, y polinomios, racionales o aproximaciones de Pade que son válidas en un rango limitado.
Una cosa segura: si encuentra un algoritmo de velocidad de rayo para e^x hasta 96 lugares decimales, también habrá encontrado una forma más rápida de calcular los registros (por Newton-Raphson). De hecho, Newton-Raphson converge cuadráticamente, por lo que duplica el número de dígitos de precisión en su registro con cada iteración. Este fue el favorito de Nate Grossman de UCLA en los días Forth.
En la época de las calculadoras de cuatro indicadores, solía usar e^x = (1 + x/1024)^10. Por supuesto que se descompone por x muy grande o muy pequeño, pero se puede ver por qué funciona. Si tiene un botón de raíz cuadrada, puede revertir esta idea para obtener logaritmos. Pero no necesita raíz cuadrada para la función exponencial.
Me pregunto si hay alguna inversión del algoritmo de AGM que podría hacer la función exponencial ... Hmmm ....
http://www.johndcook.com/blog/2008/12/10/ Rápida exponenciación/ – AakashM
Creo que esto preguntó cien veces en SO. –
¿Qué quiere decir con "exponente de un número"? – starblue