Dado un número N muy grande , la tarea es encontrar el factorial del número usando Log.
El factorial de un entero no negativo es la multiplicación de todos los enteros menores o iguales a N .
Anteriormente hemos discutido un programa simple para encontrar el factorial en este artículo . Aquí, discutiremos una forma eficiente de encontrar el factorial de números grandes. Ejemplos:
Input: N = 100 Output: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 Input: N = 50 Output: 30414093201713378043612608166064768844377641568960512000000000000
Enfoque: la versión iterativa más común se ejecuta en el tiempo O(N) esperado. Pero a medida que los números aumentan, será un error suponer que la multiplicación toma un tiempo constante. El enfoque ingenuo toma el tiempo O(K*M) para la multiplicación, donde K es la longitud del multiplicador y M es la longitud del multiplicando. Por lo tanto, la idea es usar propiedades logarítmicas: Como sabemos que 
y 
Por lo tanto: 
Otra propiedad es 
sustituyendo el valor de ln(N!). A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to compute the
// factorial of big numbers
#include <bits/stdc++.h>
using namespace std;
// Maximum number of digits
// in output
#define MAX 1000
// Function to find the factorial
// of large number and return
// them in string format
string factorial(long long n)
{
if (n > MAX) {
cout << " Integer Overflow"
<< endl;
return "";
}
long long counter;
long double sum = 0;
// Base case
if (n == 0)
return "1";
// Calculate the sum of
// logarithmic values
for (counter = 1; counter <= n;
counter++) {
sum = sum + log(counter);
}
// Number becomes too big to hold in
// unsigned long integers.
// Hence converted to string
// Answer is sometimes under
// estimated due to floating point
// operations so round() is used
string result
= to_string(round(exp(sum)));
return result;
}
// Driver code
int main()
{
clock_t tStart = clock();
string str;
str = factorial(100);
cout << "The factorial is: "
<< str << endl;
// Calculates the time taken
// by the algorithm to execute
cout << "Time taken: " << setprecision(10)
<< ((double)(clock() - tStart)
/ CLOCKS_PER_SEC)
<< " s" << endl;
}
Complejidad de tiempo: O(N) , donde N es el número dado.
Complejidad del espacio : O(1) ya que usa variables constantes