Can anyone explain this algorithm for calculating large factorials?

Question

i came across the following program for calculating large factorials(numbers as big as 100).. can anyone explain me the basic idea used in this algorithm?? I need to know just the mathematics implemented in calculating the 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

Note that

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

so that

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

This is important because if k is a positive integer then the ceiling of log(k) is the number of digits in the base-10 representation of k. Thus, these lines of code are counting the number of digits in n!.

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

Then, these lines of code allocate space to hold the digits of n!:

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

Then we just do the grade-school multiplication algorithm

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

The outer loop is running from j from 2 to n because at each step we will multiply the current result represented by the digits in a by j. The inner loop is the grade-school multiplication algorithm wherein we multiply each digit by j and carry the result into q if necessary.

The p = 0.0 before the nested loop and the p += log10(j) inside the loop just keep track of the number of digits in the answer so far.

Incidentally, I think there is a bug in this part of the program. The loop condition should be i < z not i <= z otherwise we will be writing past the end of a when z == d which will happen for sure when j == n. Thus replace

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

by

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

Then we just print out the digits

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

and free the allocated memory

delete []a;