algorithm - que - factorial de un numero algoritmo

Rápidos algoritmos para calcular el factorial.

Question

Encontré esta página que describe una serie de algoritmos para calcular el factorial. Desafortunadamente, las explicaciones son breves y no tengo ganas de revisar línea tras línea de código fuente para comprender los principios básicos de los algoritmos.

¿Alguien puede indicarme descripciones más detalladas de estos (u otros algoritmos rápidos) para calcular el factorial?

Edición: esta página describe el método de factorización principal, la técnica común a todos los algoritmos factoriales de mejor rendimiento. También contiene un buen código de ejemplo en Python. El autor enlaza con una descripción de la división binaria y hace referencia a un artículo en el Journal of Algorithms ("Sobre la complejidad de los factoriales de cálculo") que parece prometedor, si solo pudiera ponerlo en mis manos.

Answer 1

Echa un vistazo a este documento (enlace PDF) por Richard Fateman. Los ejemplos de código están en Lisp, pero en cualquier caso, gran parte del secreto se reduce a minimizar el número de cálculos bignum (entero arbitrario de precisión) que tiene que hacer.

Naturalmente, si no necesitas / tienes bignums, es trivial; una tabla de búsqueda o un simple bucle estarán bien.

EDITAR: Si puede usar una respuesta aproximada, puede calcular el logaritmo del factorial directamente sumando el log(k) para k = 2 ... n , o usando la aproximación venerable de Stirling . Desea trabajar con el logaritmo siempre que sea posible para evitar el desbordamiento; en particular, una aplicación ingenua de la aproximación de Stirling se desbordará en muchos lugares donde no tiene que hacerlo.

Answer 2

También hay otro método. Este método se detalla here que reduce a la mitad la cantidad de multiplicación para un poco de suma y resta. Probablemente desee que se muestre el primer método, y el segundo método que se muestra es una lectura interesante si puede entenderlo.