math - potenciacion - potencias propiedades

¿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 programáticamente.

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

Answer 1

A menos que hayan descubierto una mejor manera de hacerlo, creo que los valores aproximados de las funciones trigonométricas, logarítmicas y exponenciales (para el crecimiento y la disminución exponencial, por ejemplo) generalmente se calculan utilizando reglas aritméticas y expansiones de la serie Taylor 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 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, la expansión de la serie Taylor / Maclaurin para e ^ x es esta:

      +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 de 0 a infinito), esta expansión es exacta y completa (sin error).

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

Las buenas noticias para exponenciales es que convergen muy 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 (repetir, PODRÍA recordar, ha pasado un tiempo) ni siquiera tener que calcular previamente cuántos términos Es necesario 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 detener cuando se acerque lo suficiente a 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á creciendo / disminuyendo con otra base como 2 ^ x o 10 ^ x, la función polinómica aproximada cambia.

Answer 2

El enfoque habitual, para elevar a la 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 exponentes negativos o no enteros, se necesitan logaritmos y 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

Answer 3

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, 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 que no soy uno) pueden comentar. :-)

Answer 4

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.

Answer 5

Puede usar exp (n * ln (x)) para calcular x ⁿ . 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