Tuesday, December 18, 2012

A program to calculate factorial for big numbers

C++ Program to calculate Factorial for big numbers : One fine day I was trying to get factorial of some number ( >300) and couldn't find it on any tool . Most of the open tools had some limitations, so I decided to write my own program and thought of sharing it :)  Of course this is a program written in less than half an hour or so, hence don't expect it to be most efficient OR wonderfully written wrt language constructs. It did what I wanted at that moment and fulfilled its purpose :)
------------ code starts here -------------

#include < iostream >

#ifndef ARRAY  
#include < vector >
#endif

/*  @author : Manish Baphna < manish.baphna@gmail.com >
 *  @brief  : This program calculates factorial of given number. There are already available tools for that
 *            but most of them have some limitations like upper limit on number (e.g. google online calculator
 *            doesn't calculate factorial for numbers bigger than 170 : type 171! on google and search!! )
 *            This program is just an effort to give better results. Use this @your own risk :)
 *
 *  @warning :I am sharing this program ONLY because I think its better to share it instead of just keeping in
 *            my drive. This code is written in haste and NOT WRITTEN to explain things. So if you are looking
 *            for too many comments and nice formatting, please excuse me. How ever , constrcutive suggestions
 *            are most welcome. BUGS are most most most welcome !
 */

//! This is the main sizing factor here. Using SIZE = 10K , I can find max fact of 3249 ( 10,000 digits ) .
//! If you have bigger number than 3249 then increase SIZE to few ZEROs :) How much, that you have to try and learn
//! If you get glibc error for a number , it means you need bigger SIZE.
#define SIZE 10000

using namespace std  ;

/*!
 * @brief  This is the main function which does all calculation. This function has two implementation , default is
 *         vector based , other is ARRAY based. What essentially is done here is the alternate storage mechanism
 *         for results. For big factorials , int / long are insufficient so this method stores them in a BIG variable
 *         called 'array' which is actually sequence of integers . (Note: ARRAY is compile time switch)
 * @param  N the number for which you want to find factorial
 */
void myfact(int N){
#ifdef ARRAY  
   cout << " \n Array Form \n------------------------------\n" ;
   int array[SIZE] ;
   memset(array,0x0,SIZE) ;
   array[0] = 1 ;
#else
   cout << " \n Vector Form \n------------------------------\n" ;
   vector array(SIZE,0) ; 
   array[0] = 1 ;
#endif
   
   int count = 1 ;
   int xcount = 1 ;
   int temp = 0 , carry = 0 ;
   int num = 2;
   while(num <= N){
      carry = 0 ;
      count = xcount  ;
      for(int i=0; i< count; i++){
         temp = array[i] * num +  carry  ;  
         if(temp>= 10) {
           array[i] = temp % 10 ;
           carry  = temp / 10 ;
           xcount = i+1+1 ;
         }else{
        array[i] = temp ;
        carry = 0;
         }
      }
      while(carry>0){
         array[count++] = carry%10 ;
      carry = carry/10 ;
        if(carry) xcount++ ;
      }
      num++ ;
   }
 
   for(int j=0; j< xcount ; j++){
      cout << array[xcount -1 - j ] ;
   }
   cout << "\n digits required  " << xcount-1 << endl ;
}

int main(int argc, char *argv[]){
if(argc !=2 ){
cout << "pgm " << endl << " e.g. : pgm 200 " << endl ;
exit(1) ;
}
int num = (atoi)(argv[1]) ;
cout << " returning factorial of " << num << endl ;
        myfact(num) ;
   return 1;
}