Estoy tratando de determinar el tiempo de ejecución asintótico de uno de mis algoritmos, que utiliza exponentes, pero no estoy seguro de cómo se calculan los exponentes programáticamente.¿Cómo se calculan los exponentes?
Estoy buscando específicamente el algoritmo pow() utilizado para números de coma flotante de doble precisión.
He tenido la oportunidad de ver la implementación de fdlibm. Los comentarios describen el algoritmo utilizado:
* n
* Method: Let x = 2 * (1+f)
* 1. Compute and return log2(x) in two pieces:
* log2(x) = w1 + w2,
* where w1 has 53-24 = 29 bit trailing zeros.
* 2. Perform y*log2(x) = n+y' by simulating muti-precision
* arithmetic, where |y'|<=0.5.
* 3. Return x**y = 2**n*exp(y'*log2)
seguido de una lista de todos los casos especiales manejado (0, 1, inf, nan).
Las secciones más intensas del código, después de todo el manejo de casos especiales, implican los cálculos log2 y 2**. Y no hay bucles en ninguno de esos. Por lo tanto, a pesar de la complejidad de las primitivas de coma flotante, parece un algoritmo de tiempo asintóticamente constante.
Los expertos en coma flotante (de los cuales no soy uno) pueden comentar. :-)
¿Cómo sabes si el paso 1 tiene un tiempo constante? ¿Leíste el código para log2? ¿Y qué tal el paso 3, es realmente exp basado en e, o es exp2, y leíste el código para ello? –
El código no llama a log2 o exp o exp2. Implementa todas esas cosas en línea. –
No puedo * entender * este pseudocódigo, pero no sé cuáles son las entradas. ¿Qué es '**'? –
El enfoque habitual, para levantar una a la B, por un exponente entero, es algo como esto:
result = 1
while b > 0
if b is odd
result *= a
b -= 1
b /= 2
a = a * a
por lo general es logarítmica en el tamaño del exponente. El algoritmo se basa en el invariante "a^b * result = a0^b0", donde a0 y b0 son los valores iniciales de a y b.
Para exponentes negativos o no enteros, se necesitan logaritmos, aproximaciones y análisis numéricos. El tiempo de ejecución dependerá del algoritmo utilizado y de la precisión con la que esté ajustada la biblioteca.
Editar: Como parece que hay algo de interés, aquí hay una versión sin la multiplicación adicional.
result = 1
while b > 0
while b is even
a = a * a
b = b/2
result = result * a
b = b - 1
Parece que hay un par de errores en su pseudo código. el resultado se actualiza solo cuando b es impar y cuando (b == 1) en la parte superior del ciclo while habrá una multiplicación adicional. –
Creo que su enfoque sería bueno para la exponenciación de bignum, pero no es tan aplicable a la exponenciación de coma flotante, para lo cual hay una manera de calcular esto a tiempo constante. –
Si estuviera escribiendo una función pow dirigida a Intel, devolvería exp2 (log2 (x) * y). El microcódigo de Intel para log2 es seguramente más rápido que cualquier cosa que pueda codificar, incluso si pudiera recordar mi primer año de cálculo y el análisis numérico de la escuela de posgrado.
A no ser que han descubierto una mejor forma de hacerlo, yo creo que los valores aproximados para trig, logarítmicas y exponenciales (para el crecimiento y el decaimiento exponencial, por ejemplo) se calculan generalmente usando reglas aritméticas y Series de Taylor expansiones para producir un resultado aproximado preciso dentro de la precisión solicitada. (Consulte cualquier libro de Cálculo para obtener detalles sobre series de potencias, series de Taylor y expansiones de funciones de la serie Maclaurin.) Tenga en cuenta que hace mucho tiempo que no hice nada de esto, así que no pude decirle, por ejemplo, exactamente cómo calcular la cantidad de términos de la serie que debe incluir garantiza un error lo suficientemente pequeño como para ser insignificante en un cálculo de doble precisión.
Por ejemplo, el desarrollo en serie de Taylor/Maclaurin para e^x es la siguiente:
+inf [ x^k ] x^2 x^3 x^4 x^5
e^x = SUM [ --- ] = 1 + x + --- + ----- + ------- + --------- + ....
k=0 [ k! ] 2*1 3*2*1 4*3*2*1 5*4*3*2*1
Si se toma todos los términos (k de 0 a infinito), esta expansión es exacta y completa (sin error).
Sin embargo, si no toma todos los términos hasta el infinito, pero se detiene después de decir 5 términos o 50 términos o lo que sea, produce resultado aproximado que difiere del valor real de la función e^x un resto que es bastante fácil de calcular.
La buena noticia para los exponenciales es que converge muy bien y los términos de su expansión polinómica son bastante fáciles de codificar de forma iterativa, por lo que fuerza (repetición, FUERZA - recuerde, ha sido un tiempo) ni siquiera necesitan calcular de antemano cuántos términos necesita para garantizar su error es menor que la precisión, ya que puede probar el tamaño de la contribución en cada iteración y detenerse cuando se acerca lo suficiente como cero. En la práctica, no sé si esta estrategia es viable o no, tendré que intentarlo. Hay detalles importantes que hace tiempo que olvidé. Cosas como: precisión de máquina, error de máquina y error de redondeo, etc.
Además, tenga en cuenta que si no está utilizando e^x, pero está haciendo crecimiento/decaimiento con otra base como 2^x o 10^x , la función polinómica aproximada cambia.
Sí, han descubierto mejores formas de hacerlo, para definiciones adecuadas de "ellos". –
Puede usar exp (n * ln (x)) para calcular x n. Tanto x como n pueden ser números de coma flotante de doble precisión. El logaritmo natural y la función exponencial se pueden calcular utilizando la serie de Taylor. Aquí puede encontrar fórmulas: http://en.wikipedia.org/wiki/Taylor_series
Después de la primera edición, esta pregunta aún no está clara. Menciona "un algoritmo que utiliza exponentes" y "el algoritmo utilizado para números de punto flotante de precisión doble". El algoritmo para hacer qué? ¿Múltiples dos de esos números? Calcule una triangulación 3D de N puntos con doble precisión x-y-z? – Eric
s/exponents/exponenciación/ –