Кто-нибудь может объяснить этот алгоритм расчета больших факториалов?

Question

я наткнулся на следующую программу для вычисления больших факториалов (числа до 100). Может кто-нибудь объяснить мне основную идею, используемую в этом алгоритме? Мне нужно знать только математику, применяемую при расчете факториала.

#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

Обратите внимание, что

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

так что

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

Это важно, потому что если k является положительным целым числом, то верхний предел log(k) является числом цифр в представлении base-10 k. Таким образом, эти строки кода подсчитывают количество цифр в n!.

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

Затем эти строки кода выделяют пространство для хранения цифр n!:

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

Тогда мы просто делаем алгоритм умножения начальной школы

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);
    }
}

Внешний цикл выполняется с j с 2 до n, потому что на каждом шаге мы будем умножать текущий результат, представленный цифрами в a, на j. Внутренний цикл - это алгоритм умножения начальной школы, в котором мы умножаем каждую цифру на j и переносим результат в q, если необходимо.

p = 0.0 перед вложенным циклом и p += log10(j) внутри цикла до сих пор отслеживают количество цифр в ответе.

Кстати, я думаю, что в этой части программы есть ошибка. Условие цикла должно быть i < z, а не i <= z, иначе мы будем писать после конца a, когда z == d, что обязательно произойдет, когда j == n. Таким образом заменить

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

от

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

Тогда мы просто распечатаем цифры

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

и освободить выделенную память

delete []a;