El mejor algoritmo que se conoce es expresar el factorial como producto de poderes primarios. Uno puede determinar rápidamente los números primos, así como la potencia correcta para cada primer utilizando un enfoque de tamiz. El cálculo de cada potencia se puede hacer de manera eficiente utilizando la cuadratura repetida, y luego los factores se multiplican juntos. Esto fue descrito por Peter B. Borwein, Sobre la complejidad de los factores de cálculo , Journal of Algorithms 6 376–380, 1985. ( PDF ) En resumen,se puede calcular en el tiempo O (n (\ log n) ^ 3 \ log \ log n) , en comparación con el tiempo \ Omega (n ^ 2 \ log n) requerido cuando se usa la definición.n!O(n(logn)3loglogn)Ω(n2logn)
Lo que tal vez significó el libro de texto fue el método de divide y vencerás. Se pueden reducir las multiplicaciones usando el patrón regular del producto.n−1
Dejardenote como una notación conveniente. Reorganizar los factores de como
Ahora suponga que para algún entero . (Esta es una suposición útil para evitar complicaciones en la siguiente discusión, y la idea puede extenderse al general ). Entoncesy al expandir esta recurrencia,
Computación1 ⋅ 3 ⋅ 5 ⋯ ( 2 n - 1 ) ( 2 n ) ! = 1 ⋅ 2 ⋅ 3 ⋯ ( 2 n ) ( 2 n ) ! = n ! ⋅ 2 n ⋅ 3 ⋅ 5 ⋅ 7 ⋯ ( 2 n - 1 ) . n = 2 k k >n?1⋅3⋅5⋯(2n−1)(2n)!=1⋅2⋅3⋯(2n)
(2n)!=n!⋅2n⋅3⋅5⋅7⋯(2n−1).
n=2kn ( 2 k ) ! = ( 2 k - 1 ) ! 2 2 k - 1 ( 2 k - 1 ) ? ( 2 k ) ! = ( 2 2 k - 1 + 2 k - 2 + ⋯ + 2 0 ) k - 1 ∏ i = 0 ( 2 i )k>0n(2k)!=(2k−1)!22k−1(2k−1)?(2k)!=(22k−1+2k−2+⋯+20)∏i=0k−1(2i)?=(22k−1)∏i=1k−1(2i)?.
(2k−1)?y multiplicar los productos parciales en cada etapa requiere multiplicaciones. Esta es una mejora de un factor de casi de las multiplicaciones simplemente usando la definición. Se requieren algunas operaciones adicionales para calcular la potencia de , pero en aritmética binaria esto se puede hacer a bajo costo (dependiendo de lo que se requiera con precisión, puede requerir agregar un sufijo de ceros).
(k−2)+2k−1−222k−222k−1
El siguiente código Ruby implementa una versión simplificada de esto. Esto no evita volver a calcularincluso donde podría hacerlo:n?
def oddprod(l,h)
p = 1
ml = (l%2>0) ? l : (l+1)
mh = (h%2>0) ? h : (h-1)
while ml <= mh do
p = p * ml
ml = ml + 2
end
p
end
def fact(k)
f = 1
for i in 1..k-1
f *= oddprod(3, 2 ** (i + 1) - 1)
end
2 ** (2 ** k - 1) * f
end
print fact(15)
Incluso este código de primer paso mejora lo trivial
f = 1; (1..32768).map{ |i| f *= i }; print f
en aproximadamente un 20% en mis pruebas.
Con un poco de trabajo, esto se puede mejorar aún más, eliminando también el requisito de que sea una potencia de (vea la discusión extensa ).n2
Tenga en cuenta que la función factorial crece tan rápido que necesitará números enteros de tamaño arbitrario para obtener cualquier beneficio de técnicas más eficientes que el enfoque ingenuo. El factorial de 21 ya es demasiado grande para caber en un 64 bits
unsigned long long int
.Hasta donde yo sé, ¡no hay un algoritmo para calcular(factorial de ) que es más rápido que hacer las multiplicaciones.n! n
Sin embargo, el orden en el que haces las multiplicaciones es importante. La multiplicación en un entero de máquina es una operación básica que lleva el mismo tiempo sin importar el valor del entero. Pero para los enteros de tamaño arbitrario, el tiempo que se necesita para multiplicar una y B depende del tamaño de una y b : un algoritmo ingenuo funciona en tiempo (en el que es el número de dígitos de - en cualquier base que desee, ya que el resultado es el mismo hasta una constante multiplicativa). Hay algoritmos de multiplicación más rápidos , pero hay un límite inferior obvio deΘ(|a|⋅|b|) |x| x Ω(|a|+|b|) ya que la multiplicación tiene que leer al menos todos los dígitos. Todos los algoritmos de multiplicación conocidos crecen más rápido que linealmente en .max(|a|,|b|)
Armado con estos antecedentes, el artículo de Wikipedia debería tener sentido.
Dado que la complejidad de las multiplicaciones depende del tamaño de los enteros que se multiplican, puede ahorrar tiempo organizando las multiplicaciones en un orden que mantenga los números pequeños. Funciona mejor si arreglas que los números sean aproximadamente del mismo tamaño. La “división por la mitad” de que su libro de texto se refiere a consiste en lo siguiente divide y vencerás enfoque para multiplicar un conjunto (multi) de enteros:
Consulte el manual de GMP para más detalles.
Hay incluso más rápido que los métodos no sólo reorganizar los factores a , pero dividen los números por descomponerlos en su descomposición en factores primos y reordenando el producto que resulta de muy largo en su mayoría de pequeños números enteros. Solo citaré las referencias del artículo de Wikipedia: "Sobre la complejidad de calcular factores" de Peter Borwein y las implementaciones de Peter Luschny .1 n
¹ ¡ Hay formas más rápidas de calcular aproximaciones de, pero eso ya no es calcular el factorial, es calcular una aproximación de él.n!
fuente
Dado que la función factorial crece tan rápido, su computadora solo puede almacenarpara relativamente pequeño . Por ejemplo, ¡un doble puede almacenar valores de hasta. Entonces, si quieres un algoritmo realmente rápido para calcular, solo use una tabla de tamaño .n! n 171! n! 171
La pregunta se vuelve más interesante si está interesado en O en la función (o en ). En todos estos casos (¡incluido ), Realmente no entiendo el comentario en su libro de texto.log(n!) Γ logΓ n!
Por otro lado, sus algoritmos iterativos y recursivos son equivalentes (hasta errores de coma flotante), ya que está utilizando la recursividad de cola.
fuente