Puede encontrar un conjunto de páginas aquí (incluidas implementaciones de muestra de varios algoritmos) que proporcionan mucha más profundidad de la que soy capaz: Funciones factoriales rápidas Debe leer particularmente el documento que introduce el cálculo a través de “factoriales oscilantes”: http: // www .luschny.de / math / facto …
Demostraré un algoritmo más simple, descrito por Peter Borwein en 1983. Primero calcule todos los números primos hasta [math] n [/ math]. Esto se puede hacer fácilmente a tiempo [math] O (n \ log \ log n) [/ math] usando un tamiz.
Luego, para cada primo, podemos calcular la mayor potencia de [math] p [/ math] que aparece en [math] n! [/ Math], es
- ¿Cuál es el plan de estudios que debe seguir un estudiante universitario en el MIT para graduarse con un título de matemática pura?
- Si b es la proporción media entre a y c, ¿cuál es la proporción media entre [matemáticas] (a ^ 2 + b ^ 2) \ text {y} (b ^ 2 + c ^ 2) [/ matemáticas]?
- ¿Con qué facilidad podría un matemático aplicado aprender el procesamiento de señales (digital), la teoría de control y / o la visión por computadora?
- Cómo abordar el dibujo de la curva para x ^ 3 + y ^ 3-3axy = 0 (folium de Descartes)
- ¿Cuál es el truco matemático más interesante?
[matemáticas] s_p (n!) = \ lfloor n / p \ rfloor + \ lfloor n / p ^ 2 \ rfloor + \ lfloor n / p ^ 3 \ rfloor + \ lfloor n / p ^ 4 \ rfloor +… [/ matemáticas]
Para p = 2, esto puede realizarse utilizando solo desplazamiento de bits y suma, pero tendrá que hacer algunas divisiones para primos más grandes. Pero todas las operaciones matemáticas hasta ahora son “pequeñas” (es decir, menores que n.)
Ahora queremos calcular [matemática] 2 ^ {s_2 (n!)} 3 ^ {s_3 (n!)} 5 ^ {s_5 (n!)}… [/ Matemática] Podríamos usar la cuadratura repetida en cada término, pero eso realmente no proporciona suficientes beneficios, sino que dividimos y conquistamos de una manera menos obvia.
Considere la representación binaria de los exponentes [math] s_p (n!) [/ Math]. Para cada valor posicional 1, 2, 4, etc., multiplique los primos juntos que tengan un ‘1’ en [math] s_p (n!) [/ Math] para ese lugar, y los eleve al poder de ese lugar valor.
Entonces, por ejemplo, identifique todos los primos [math] p_a, p_b, p_c [/ math] donde el exponente es impar (tiene un 1 en el último dígito binario) y calcule [math] (p_a p_b p_c) ^ {2 ^ 0} [/ matemáticas]. Luego identifique los primos [math] p_d, p_e, p_f [/ math] (algunos podrían ser los mismos) cuyos exponentes tienen un ‘1’ en el dígito del 2. Calcule [matemática] (p_d p_e p_f) ^ {2 ^ 1} [/ matemática], y así sucesivamente. Cada uno de estos poderes se puede calcular con cuadratura repetida.
Como fórmula matemática, esto parece
[matemáticas] \ displaystyle x_i = \ left (\ prod_ {s_p (n!) \ mathrm {\ has \ binary \ digit \} 2 ^ i} p \ right) ^ {2 ^ i} [/ math]
Entonces, el producto de todos los [math] x_i [/ math] da el factorial deseado. Tenga en cuenta que cada primo aparece [math] s_p (n!) [/ Math] veces, según lo deseado, simplemente agrupamos los primos de tal manera que nos permitimos hacer una cuadratura repetida en un montón de primos a la vez.
Análisis de tiempo del trabajo de Borwein: http://www.cecm.sfu.ca/personal/…
