Ertor
Páginas: 5 (1196 palabras)
Publicado: 29 de agosto de 2012
Stirling al descubierto
Juan Ignacio Go˜i n
Resumen En este art´ ıculo se analiza la precisi´n de la aproximaci´n de Stirling o o para el c´lculo del factorial de un n´mero. a u
1.
Indroducci´n o
1
Hist´ricamente, Abraham Moivre descubri´ √ f´rmula n! ≈ Cnn+ 2 e−n . o o la o Luego, Stirling descubri´ que la constante C es 2π, debido a dicha contribuo ci´n, la f´rmula recibi´ sunombre. Es usualmente utilizada para el c´lculo en o o o a lculos estad´ ısticos. la teor´ cu´ntica y ca´ ıa a Se sabe que la f´rmula de Stirling, es una aproximaci´n al factorial de un o o n´mero, pero lo interesante es saber qu´ error se est´ cometiendo, en qu´ casos u e a e conviene utilizarla y en cu´les es mejor realizar el c´lculo iterativo o recursivo a a de n!. En las distintas secciones delart´ ıculo se analizan las t´ ıpicas preguntas que surgen ante la posibilidad de usarla. En la secci´n 2, se muestra el c´lculo o a del factorial a partir de la f´rmula de Stirling. En la secci´n 3, se analiza en o o qu´ casos conviene utilizarla, frente a los m´todos comunes. En la secci´n 4, se e e o muestran los beneficios que trae su uso. Finalmente, en la secci´n 5, se obtienen o conclusiones. Seutiliza un breve programa en C para el c´lculo num´rico y octave para el a e gr´fico de los resultados. a
2.
¿C´mo funciona? o
El c´lculo del factorial de √ n´mero se define como n! = (n − 1)!n y la a un u f´rmula de Stirling n! ≈ nn e−n 2πn. Lo primero que se observa es la definici´n o o recursiva de n! donde se necesita (n − 1)!, para el c´mputo de n!, y en la versi´n o o de Stirling, elc´lculo es directo. a Usando como herramienta un breve programa codificado en C, Figura 1, se computan el valor de n!, la f´rmula de Stirling, el error absoluto y el error relativo o para distintos valores de n y se obtiene el Cuadro 1. El programa realiza el c´mputo de n! de forma iterativa y calcula los errores de utilizar la aproximaci´n o o de la f´rmula de Stirling. o Utilizando octave, seobtiene el gr´fico del error relativo al utilizar la f´rmula a o de Stirling frente al c´mputo de n!, Figura 2. o
1
Figura 1: C´digo en C que computa el valor de n!, la f´rmula de Stirling, el o o error absoluto y el error relativo para distintos valores de n
Figura 2: Error relativo entre n! y la f´rmula de Stirling para distintos valores o de n
2
3.
¿Cu´ndo conviene usarla? aComo se observa en el Cuadro 1, a medida que n se vuelve m´s grande, el a error relativo es cada vez m´s peque˜o. Para n´meros cercanos al 1, el error es a n u menor al 7 %, y ya para valores que superiores a 10 se vuelve despreciable frente a la magnitud de n!.
4.
¿Qu´ beneficios trae? e
Un factor a la hora de elegir alg´n algoritmo para el c´lculo de n!, es el u a tiempo que tarda encomputar dicho valor. Para realizar la medici´n se usan o los c´digos de la Figura 3, tomando el tiempo de ejecuci´n de un ciclo de 10000 o o iteraciones de llamadas a la funci´n de la f´rmula de Stirling, la implementaci´n o o o iterativa y recursiva para el c´lculo del factorial, para el c´lculo del factorial de a a 1 a 140, se obtiene el Cuadro 2, que muestra las notables diferencias entre losalgoritmos.
5.
Conclusiones
Debido a las grandes diferencias de tiempo de ejecuci´n entre los distintos o algoritmos y frente al bajo error relativo que se obtiene, es bueno tener en cuenta que se existe la f´rmula de Stirling como aproximaci´n de n!. Es aproximadao o mente 4 veces m´s r´pida que una implementaci´n recursiva de n! y 1,7 veces a a o m´s r´pida que una implementaci´n iterativade n!. ¿Y el precio que se debe a a o pagar? S´lo un error relativo menor al 1 % para 9! y menor al 0,098 % a partir o de 85!.
3
Figura 3: C´digo en C para el c´lculo del tiempo de c´mputo de los distintos o a o algoritmos
4
n 1 2 3 4 5 6 7 8 9 10 . . . 45 46 47 48 49 50 . . . 80 81 82 83 84 85 . . . 135 136 137 138 139 140
n! 1 2 6 24 120 720 5040 40320 362880 3628800 . . ....
Juan Ignacio Go˜i n
Resumen En este art´ ıculo se analiza la precisi´n de la aproximaci´n de Stirling o o para el c´lculo del factorial de un n´mero. a u
1.
Indroducci´n o
1
Hist´ricamente, Abraham Moivre descubri´ √ f´rmula n! ≈ Cnn+ 2 e−n . o o la o Luego, Stirling descubri´ que la constante C es 2π, debido a dicha contribuo ci´n, la f´rmula recibi´ sunombre. Es usualmente utilizada para el c´lculo en o o o a lculos estad´ ısticos. la teor´ cu´ntica y ca´ ıa a Se sabe que la f´rmula de Stirling, es una aproximaci´n al factorial de un o o n´mero, pero lo interesante es saber qu´ error se est´ cometiendo, en qu´ casos u e a e conviene utilizarla y en cu´les es mejor realizar el c´lculo iterativo o recursivo a a de n!. En las distintas secciones delart´ ıculo se analizan las t´ ıpicas preguntas que surgen ante la posibilidad de usarla. En la secci´n 2, se muestra el c´lculo o a del factorial a partir de la f´rmula de Stirling. En la secci´n 3, se analiza en o o qu´ casos conviene utilizarla, frente a los m´todos comunes. En la secci´n 4, se e e o muestran los beneficios que trae su uso. Finalmente, en la secci´n 5, se obtienen o conclusiones. Seutiliza un breve programa en C para el c´lculo num´rico y octave para el a e gr´fico de los resultados. a
2.
¿C´mo funciona? o
El c´lculo del factorial de √ n´mero se define como n! = (n − 1)!n y la a un u f´rmula de Stirling n! ≈ nn e−n 2πn. Lo primero que se observa es la definici´n o o recursiva de n! donde se necesita (n − 1)!, para el c´mputo de n!, y en la versi´n o o de Stirling, elc´lculo es directo. a Usando como herramienta un breve programa codificado en C, Figura 1, se computan el valor de n!, la f´rmula de Stirling, el error absoluto y el error relativo o para distintos valores de n y se obtiene el Cuadro 1. El programa realiza el c´mputo de n! de forma iterativa y calcula los errores de utilizar la aproximaci´n o o de la f´rmula de Stirling. o Utilizando octave, seobtiene el gr´fico del error relativo al utilizar la f´rmula a o de Stirling frente al c´mputo de n!, Figura 2. o
1
Figura 1: C´digo en C que computa el valor de n!, la f´rmula de Stirling, el o o error absoluto y el error relativo para distintos valores de n
Figura 2: Error relativo entre n! y la f´rmula de Stirling para distintos valores o de n
2
3.
¿Cu´ndo conviene usarla? aComo se observa en el Cuadro 1, a medida que n se vuelve m´s grande, el a error relativo es cada vez m´s peque˜o. Para n´meros cercanos al 1, el error es a n u menor al 7 %, y ya para valores que superiores a 10 se vuelve despreciable frente a la magnitud de n!.
4.
¿Qu´ beneficios trae? e
Un factor a la hora de elegir alg´n algoritmo para el c´lculo de n!, es el u a tiempo que tarda encomputar dicho valor. Para realizar la medici´n se usan o los c´digos de la Figura 3, tomando el tiempo de ejecuci´n de un ciclo de 10000 o o iteraciones de llamadas a la funci´n de la f´rmula de Stirling, la implementaci´n o o o iterativa y recursiva para el c´lculo del factorial, para el c´lculo del factorial de a a 1 a 140, se obtiene el Cuadro 2, que muestra las notables diferencias entre losalgoritmos.
5.
Conclusiones
Debido a las grandes diferencias de tiempo de ejecuci´n entre los distintos o algoritmos y frente al bajo error relativo que se obtiene, es bueno tener en cuenta que se existe la f´rmula de Stirling como aproximaci´n de n!. Es aproximadao o mente 4 veces m´s r´pida que una implementaci´n recursiva de n! y 1,7 veces a a o m´s r´pida que una implementaci´n iterativade n!. ¿Y el precio que se debe a a o pagar? S´lo un error relativo menor al 1 % para 9! y menor al 0,098 % a partir o de 85!.
3
Figura 3: C´digo en C para el c´lculo del tiempo de c´mputo de los distintos o a o algoritmos
4
n 1 2 3 4 5 6 7 8 9 10 . . . 45 46 47 48 49 50 . . . 80 81 82 83 84 85 . . . 135 136 137 138 139 140
n! 1 2 6 24 120 720 5040 40320 362880 3628800 . . ....
Leer documento completo
Regístrate para leer el documento completo.