¿Cómo se calculan los exponentes?

Question

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 mediante programación.

Estoy buscando específicamente el algoritmo pow () utilizado para los números de punto flotante de doble precisión.

Answer 1

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 manejados (0, 1, inf, nan).

Las secciones más intensas del código, después de todo el manejo de casos especiales, involucran los cálculos de log2 y 2 ** . Y no hay bucles en ninguno de esos. Por lo tanto, a pesar de la complejidad de las primitivas de punto flotante, parece un algoritmo de tiempo constante asintóticamente.

Los expertos en puntos flotantes (de los cuales no soy uno) pueden hacer comentarios. :-)

Answer 2

A menos que hayan descubierto una mejor manera de hacerlo, creo que los valores aproximados para funciones trigonométricas, logarítmicas y exponenciales (por ejemplo, para el crecimiento exponencial y la decadencia) generalmente se calculan utilizando reglas aritméticas y Taylor Series expansiones para producir un resultado aproximado exacto dentro de la precisión solicitada. (Consulte cualquier libro de cálculo para obtener detalles sobre la serie de potencias, la serie de Taylor y la serie de funciones Maclaurin). Tenga en cuenta que ha pasado un tiempo desde que hice todo esto, por lo que no pude decirle exactamente cómo calcular. El número de términos en 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, la expansión de la serie 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 toma todos los términos (k desde 0 hasta el infinito), esta expansión es exacta y completa (sin error).

Sin embargo, si no toma todos los términos que van al infinito, pero se detiene después de decir 5 términos o 50 términos o lo que sea, produce un resultado aproximado que difiere del e real Valor de la función x por un resto que es bastante fácil de calcular.

La buena noticia para las exponenciales es que converge bien y los términos de su expansión polinómica son bastante fáciles de codificar de forma iterativa, por lo que podría (repita, MIGHT - recuerde , ha pasado un tiempo) ni siquiera es necesario realizar un cálculo previo de cuántos términos necesita para garantizar que su error sea menor que la precisión, ya que puede probar el tamaño de la contribución en cada iteración y detenerse cuando se acerque a cero. En la práctica, no sé si esta estrategia es viable o no, tendría que intentarlo. Hay detalles importantes que hace tiempo que he olvidado. Cosas como: precisión de la máquina, error de la máquina y error de redondeo, etc.

También, 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 polinomial aproximada cambia.

Answer 3

El enfoque habitual, elevar a a b, para 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

Generalmente es logarítmico 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 los exponentes negativos o no enteros, se necesitan logaritmos, aproximaciones y análisis numérico. El tiempo de ejecución dependerá del algoritmo utilizado y de la precisión con la que se sintonice la biblioteca.

Editar: como parece haber cierto 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

Answer 4

Si estuviera escribiendo una función pow orientada 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 el primer cálculo de año y el análisis numérico de la escuela de posgrado.

Answer 5

Puedes usar exp (n * ln (x)) para calcular x ⁿ . Tanto x como n pueden ser números de punto flotante de precisión doble. 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