1,105,633 Community Members

Calculate large Factorials

Member Avatar
Reputation Points: 1,544 [?]
Q&As Helped to Solve: 1,872 [?]
Skill Endorsements: 67 [?]
 
0
 

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;
}
Member Avatar
homi
Newbie Poster
3 posts since Jan 2006
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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.

Member Avatar
daniusr
Newbie Poster
3 posts since Mar 2007
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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.

Member Avatar
drmikeaz
Newbie Poster
6 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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.

Member Avatar
WaltP
Posting Sage w/ dash of thyme
9,363 posts since May 2006
Reputation Points: 2,905 [?]
Q&As Helped to Solve: 1,151 [?]
Skill Endorsements: 45 [?]
Team Colleague
 
0
 

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

Member Avatar
drmikeaz
Newbie Poster
6 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
1
 

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 !!!

Member Avatar
WaltP
Posting Sage w/ dash of thyme
9,363 posts since May 2006
Reputation Points: 2,905 [?]
Q&As Helped to Solve: 1,151 [?]
Skill Endorsements: 45 [?]
Team Colleague
 
0
 

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...

Member Avatar
mazzica1
Junior Poster
148 posts since Oct 2011
Reputation Points: -1 [?]
Q&As Helped to Solve: 27 [?]
Skill Endorsements: 0 [?]
 
0
 

i found these two solutions big array bigInt Class

Member Avatar
drmikeaz
Newbie Poster
6 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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.

Member Avatar
messr135
Newbie Poster
4 posts since Feb 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
-2
 

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?

Member Avatar
WaltP
Posting Sage w/ dash of thyme
9,363 posts since May 2006
Reputation Points: 2,905 [?]
Q&As Helped to Solve: 1,151 [?]
Skill Endorsements: 45 [?]
Team Colleague
 
1
 

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.

Member Avatar
jaskij
Junior Poster
105 posts since Oct 2011
Reputation Points: 45 [?]
Q&As Helped to Solve: 19 [?]
Skill Endorsements: 0 [?]
 
0
 

+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?

Member Avatar
drmikeaz
Newbie Poster
6 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
-1
 

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;
}
Member Avatar
WaltP
Posting Sage w/ dash of thyme
9,363 posts since May 2006
Reputation Points: 2,905 [?]
Q&As Helped to Solve: 1,151 [?]
Skill Endorsements: 45 [?]
Team Colleague
 
0
 

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.

Member Avatar
drmikeaz
Newbie Poster
6 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

"...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.

Member Avatar
drmikeaz
Newbie Poster
6 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
1
 

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 ?

Member Avatar
vegaseat
DaniWeb's Hypocrite
6,984 posts since Oct 2004
Reputation Points: 1,544 [?]
Q&As Helped to Solve: 1,872 [?]
Skill Endorsements: 67 [?]
Moderator
 
0
 

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.

You
Post:
Start New Discussion
Tags Related to this Article