Cómo calcular óptimamente grandes factoriales de orden 10 ^ 5 para operaciones repetidas (por ejemplo, encontrar permutaciones)

El cálculo de factoriales de números más grandes está incluso más allá del rango de tipo de datos largo y largo. Entonces, en tales casos, lo que hacemos es almacenar dígitos individuales del resultado.

El siguiente es un algoritmo detallado para encontrar factorial.

factorial (n)
1) Cree una matriz ‘res []’ de tamaño MAX donde MAX es el número de dígitos máximos en la salida.
2) Inicialice el valor almacenado en ‘res []’ como 1 e inicialice ‘res_size’ (tamaño de ‘res []’) como 1.
3) Haga lo siguiente para todos los números de x = 2 a n.
…… a) Multiplique x con res [] y actualice res [] y res_size para almacenar el resultado de la multiplicación.

¿Cómo multiplicar un número ‘x’ con el número almacenado en res []?
La idea es utilizar las matemáticas escolares simples. Uno por uno multiplicamos x con cada dígito de res []. El punto importante a tener en cuenta aquí es que los dígitos se multiplican del dígito más a la derecha al más a la izquierda. Si almacenamos dígitos en el mismo orden en res [], entonces se hace difícil actualizar res [] sin espacio adicional. Es por eso que res [] se mantiene en forma inversa, es decir, los dígitos de derecha a izquierda se almacenan.

multiplicar (res [], x)
1) Inicializar carry como 0.
2) Haga lo siguiente para i = 0 para res_size – 1
… .A) Encuentre el valor de res [i] * x + carry. Deje que este valor sea prod.
… .B) Actualice res [i] almacenando el último dígito de producción en él.
… .C) Actualice el carry almacenando los dígitos restantes en el carry.
3) Ponga todos los dígitos de carry en res [] y aumente res_size por el número de dígitos en carry.

Ejemplo para mostrar el funcionamiento de multiplicar (res [], x)
Un número 5189 se almacena en res [] como sigue.
res [] = {9, 8, 1, 5}
x = 10

Inicializar carry = 0;

i = 0, prod = res [0] * x + carry = 9 * 10 + 0 = 90.
res [0] = 0, acarreo = 9

i = 1, prod = res [1] * x + carry = 8 * 10 + 9 = 89
res [1] = 9, llevar = 8

i = 2, prod = res [2] * x + carry = 1 * 10 + 8 = 18
res [2] = 8, llevar = 1

i = 3, prod = res [3] * x + carry = 5 * 10 + 1 = 51
res [3] = 1, llevar = 5

res [4] = llevar = 5

res [] = {0, 9, 8, 1, 5}

En la mayoría de los casos, se le pide que encuentre el factoriales módulo algún valor M. Puede calcularlos previamente y almacenarlos en una matriz. Luego puede recuperar valores en O (1) en lugar de calcularlos una y otra vez en O (n).

factorial [0] = 1
para (i = 1; i <= 100000; i ++)
factorial [i] = (factorial [i-1] * i)% M

Puede usar un fragmento similar al anterior. Este método solo funciona cuando el factorial debe calcularse para valores <= 1e6. Si es mucho más grande que eso, no puede almacenar la matriz en la memoria.