usando - factorial en borland c++

¿Alguien puede explicar este algoritmo para calcular grandes factoriales?

Question

Me encontré con el siguiente programa para calcular grandes factoriales (números tan grandes como 100). ¿Puede alguien explicarme la idea básica utilizada en este algoritmo? Necesito saber solo las matemáticas implementadas en el cálculo del factorial.

#include <cmath>
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{

      unsigned int d;

      unsigned char *a;

      unsigned int j, n, q, z, t;

      int i,arr[101],f;

      double p;


    cin>>n;
    p = 0.0;
    for(j = 2; j <= n; j++)
        p += log10(j);
    d = (int)p + 1;
    a = new unsigned char[d];
    for (i = 1; i < d; i++)
        a[i] = 0; //initialize
    a[0] = 1;
    p = 0.0;
    for (j = 2; j <= n; j++)
    {
        q = 0;
        p += log10(j);
        z = (int)p + 1;
        for (i = 0; i <= z/*NUMDIGITS*/; i++)
        {
            t = (a[i] * j) + q;
            q = (t / 10);
            a[i] = (char)(t % 10);
        }

    }
    for( i = d -1; i >= 0; i--)
        cout << (int)a[i];
    cout<<"/n";
    delete []a;

return 0;
}

Answer 1

Tenga en cuenta que

n! = 2 * 3 * ... * n

así que eso

log(n!) = log(2 * 3 * ... * n) = log(2) + log(3) + ... + log(n)

Esto es importante porque si k es un entero positivo, entonces el techo de log(k) es el número de dígitos en la representación de k de base-10. Por lo tanto, estas líneas de código cuentan el número de dígitos en n! .

p = 0.0;
for(j = 2; j <= n; j++)
    p += log10(j);
d = (int)p + 1;

Luego, estas líneas de código asignan espacio para contener los dígitos de n! :

a = new unsigned char[d];
for (i = 1; i < d; i++)
    a[i] = 0; //initialize

Luego simplemente hacemos el algoritmo de multiplicación de la escuela primaria

p = 0.0;
for (j = 2; j <= n; j++) {
    q = 0;
    p += log10(j);
    z = (int)p + 1;
    for (i = 0; i <= z/*NUMDIGITS*/; i++) {
        t = (a[i] * j) + q;
        q = (t / 10);
        a[i] = (char)(t % 10);
    }
}

El bucle externo se ejecuta de j de 2 a n porque en cada paso multiplicaremos el resultado actual representado por los dígitos en a por j . El bucle interno es el algoritmo de multiplicación de la escuela de grado en el que multiplicamos cada dígito por j y llevamos el resultado a q si es necesario.

La p = 0.0 antes del bucle anidado y la p += log10(j) dentro del bucle solo hacen un seguimiento del número de dígitos en la respuesta hasta el momento.

Por cierto, creo que hay un error en esta parte del programa. La condición del bucle debe ser i < z no i <= z contrario, estaremos escribiendo más allá del final de a cuando z == d lo que ocurrirá con seguridad cuando j == n . Así reemplazar

for (i = 0; i <= z/*NUMDIGITS*/; i++)

por

for (i = 0; i < z/*NUMDIGITS*/; i++)

Luego simplemente imprimimos los dígitos

for( i = d -1; i >= 0; i--)
    cout << (int)a[i];
cout<<"/n";

y liberar la memoria asignada

delete []a;