Calculate large Factorials

vegaseat 0 Tallied Votes 1K Views Share

Factorials get large very rapidly. The factorial of 13 is !13 = 1*2*3*4*5*6*7*8*9*10*11*12*13 = 6227020800. This number already exceeds the unsigned long integer, and gets into the real money as the politicians say! This program uses an array of characters to store the factorial as a numeric string. Go ahead, exercise your computer with astronomical numbers. The factorial of 47 is 258623241511168180642964355153611979969197632389120000000000. Checked it with Python, where these kind of things are a natural.

// calculate large factorials (factorials above 12!)
// note that 13! already exceeds unsigned long
// a Dev-C++ tested console program  by  vegaseat  26mar2005 

#include <cmath>
#include <iostream>

using namespace std;

int main()
{
  unsigned int nd, nz;   // number of digits
  unsigned char *ca;     // char array to hold result
  unsigned int j, n, q, temp;
  int i;
  double p;
    
  while(1)
  {
    cout << "\nEnter an integer to calculate factorial (0 to exit): ";
    cin >> n;
    
    if (n == 0) break;
     
    //calculate nd = the number of digits required
    p = 0.0;
    // p is really log10(n!)
    for(j = 2; j <= n; j++)
    {
      p += log10((double)j);   // cast to double
    }

    nd = (int)p + 1;
    // allocate memory for the char array
    ca = new unsigned char[nd];
    if (!ca)
    {
      cout << "Could not allocate memory!!!";
      exit(0);
    }
    //initialize char array
    for (i = 1; i < nd; i++)
    {
      ca[i] = 0;
    }
    ca[0] = 1;
    
    // put the result into a numeric string using the array of characters
    p = 0.0;
    for (j = 2; j <= n; j++)
    {
      p += log10((double)j);   // cast to double!!!    
      nz = (int)p + 1;         // number of digits to put into ca[]
      q = 0;                   // initialize remainder to be 0
      for (i = 0; i <= nz; i++)
      {
        temp = (ca[i] * j) + q;
        q = (temp / 10);
        ca[i] = (char)(temp % 10);
      }
    }
  
    cout << "\nThe Factorial of " << n << " is: ";
    // the factorial is stored in reverse, spell it from the back
    for( i = nd - 1; i >= 0; i--)
    {
      cout << (int)ca[i];
    }
    cout << endl;
    
    // free up allocated memory
    delete []ca;    
  }  // while
    	
  return 0;
}
homi 0 Newbie Poster

thanks pal.we required a good code like.The one that we coded was too long and reqd the creation of a header file , which i am not very familiar with.

daniusr 0 Newbie Poster

Nice C++ program.

Would it be possible to copy ca into a buffer. I tried to copy ca into a a buffer using strcpy(), and strncpy() without any success. I am using Dev-C++ 4.

Any help would be appreciated.

Thanks in advance.

drmikeaz 0 Newbie Poster

I have found the above code to be very useful. However, I have found some anomalies
which I do not understand.
First let me share my system; Vista Home Premium (64), Dell Inspiron 530s,288 GB,
RAM 4.00 GB, Code-blocks I.D.E.
Certain numbers calculate the factorial (correctly) but then the Windows message appears
"large.exe has stopped working."This behaviour is consistent for the following numbers:
40, 1000, 1040, 1140, 1800, 2000 regardless of their sequence in the input chain.
The program works well at much higher numbers e.g. 4000 is O.K. although the accuracy is
difficult to check at this level (!).
I would be fascinated to see if anyone can explain this odd behaviour.

WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague

What's the value of 40! ?
What's the largest value a variable can accurately hold?
Rim-shot!

drmikeaz 0 Newbie Poster

What's the value of 40! ?
What's the largest value a variable can accurately hold?
Rim-shot!

Please read the original post by vegaseat !!

The answer is:
815915283247897734345611269596115894272000000000

Bulls-eye !!!

WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague

Oops. Sorry. I tend not to bother reading posts that are 7 years old... My philosophy is if there's a problem, let it stay buried rather than dig it up and let it live yet again. That may be just me...

mazzica1 -1 Junior Poster

i found these two solutions big array bigInt Class

drmikeaz 0 Newbie Poster

i found these two solutions big array bigInt Class

Thanks for your reply. However I'm not really looking for a different program because that provided by "vegaseat" appears to be accrurate and versatile. What perplexes me is the fact that the program stops working only after processing a few specific numbers (correctly !). For example: Run program for the following numbers;
5 result O.K. continue with 39 result O.K. try 40 result O.K. but program stops running. No matter what sequence of numbers given to the program as soon as one of the "mystery" numbers is processed the program stops running.

This peculiar behaviour has aroused my curiosity.

messr135 0 Newbie Poster

hmmmm....i tried a simple code with unsigned long and it worked until 12!

#include<iostream.h>
#include<conio.h>
main()
{
int i,n,j;
unsigned long p=1,q=1;
cout<<"Enter number ";
cin>>n;
cout<<"Factorial is ";
for(i=1;i<=12;i++)
p*=i;   
for(j=13;j<=n;j++)
q*=j;
cout<<p<<endl;
cout<<q;           
getch();
}

cn v sumhow store the outputs differently n then display them as one as above?i admit its lame bt any easy diff way possible?

WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague

hmmmm....i tried a simple code with unsigned long and it worked until 12!

What's the maximum value an unsigned long can hold?
What's the actual result at 12?

cn v sumhow ... bt any easy diff way possible?

And what does this mean? Is it Swahili? Reread the member rules about posting in English.

jaskij 45 Junior Poster in Training

+1 for that WaltP

By comparing maximal values (using Mathematica) uint32 will work up to 12!, uint64 up to 20!.

Looking at IEEE 754-2008 and again comparing the values, long double (binary128 in IEEE 754) should work somewhere to the upper thirties, didn't check the exact value.

But still, that's not the point of vegaseats code, is it?

drmikeaz 0 Newbie Poster

hmmmm....i tried a simple code with unsigned long and it worked until 12!

The following code using long long works up to 20!. But again, i'm trying to find out why the vegaseat program stops working for some (a few) particular numbers. Has anyone else tried it ?

/* This program will calculate factorials of numbers up to 20.
If int were used only factorials of numbers up to 12 would be correct.
If long were used the program would be good for numbers up to 15 (I think !) */

#include <iostream>
using namespace std;

long long factorial(long long);

int main() {
    long long number;

    cout << "Please enter a positive integer: ";
    cin >> number;
    if (number < 0)
        cout << "That is not a positive integer.\n";
    else
        cout << number << " factorial is: " << factorial(number) << endl;

    cin.clear();
    cin.ignore(255, '\n');
    cin.get();
}

long long factorial(long long number) {
    long long temp;

    if(number <= 1) return 1;

    temp = number * factorial(number - 1);
    return temp;
}
WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague

The following code using long long works up to 20!. But again, i'm trying to find out why the vegaseat program stops working for some (a few) particular numbers. Has anyone else tried it ?

"...for some (a few) particular numbers?" Which particular numbers? If 12, we already explained that.

drmikeaz 0 Newbie Poster

"...for some (a few) particular numbers?" Which particular numbers? If 12, we already explained that.

WaltP, Please go back and read my post of January 25,2012 where I posted some of the numbers already. Since then I have found that 76 is another case in point.

drmikeaz 0 Newbie Poster

WaltP, Please go back and read my post of January 25,2012 where I posted some of the numbers already. Since then I have found that 76 is another case in point.

Here is an update to previous info. on "mystery" numbers.
(1) I have checked ALL numbers from 2 to 208
(2) Let me emphasise that the program (by vegaseat)gives the correct answer in all cases.
(3) The program stops running after calculation for the following numbers:
18,24,40,54,72,76,97,101,124,128,143,154,165,172,179,190,207
(4) In addition I have found the following cases :
1000,1040,1140,1800,2000.
Question : Has anyone else tried this ? Have they found similar behaviour ? What system did they use ?

vegaseat 1,735 DaniWeb's Hypocrite Team Colleague

My Linux machine bit the dust a few years ago.
Using CodeBlocks on Window7 gives me the mystery number effect.
(changed exit(0); to return 0; for CodeBlocks)

The correct number comes up, but then Windows forces the program to exit.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.