Monday 19 September 2011

Factorial of a large number

To calculate factorial for a big number we need to use integer array as factrial value wont fit in the
size of the integer.

Ex:
2432902008176640000 = 20!
51090942171709440000 = 21!
8222838654177922817725562880000000 = 31!
263130836933693530167218012160000000 = 32
295232799039604140847618609643520000000 = 34!

Create and integer array  and initialize with 0.  In every iteration stored value(val) is multiplied and val%10 value will be stored in current index and val/10 will be added ( carry forwarded) to next number.Here multiplier will be incremented by one for each iteration
ex:
   5! = 120;
   a = {0,0,0,0,0};
   i=1;
  a = {1,0, 0,0,0};
  i=2;
  a = {2,0,0,0,0};
  i=3;
  a= {6,0,0,0,0};
  i=4;
  a={4,2,0,0,0};
  i=5;
  a={0,2,1,0,0}
  reverse array and print output.
code
-------


#include <iostream>
using namespace std;

int main()
{
   int a[200]={0};
   //100 factorial 
   int carry=1,m=1,n=100,j,val,i;
   for(i=1;i<=n;i++)
   {
      j=0;
      while( j < m || carry !=0 )
      {
          val = a[j]*i + carry;
          a[j] = val % 10;
          carry = val/10;
          j++;
      }
      m = j;
   }
   
    for(i=m-1;i>=0;i--)
      cout<<a[i];
}

No comments:

Post a Comment