Calculating Factorial

[ice661666]

Hi,

I have been asked to write C++ program to calculate the factorial for numbers from 1 until 255, the problem is that no variable exist as far as I know that can handle the result for calculating 140! And greater “I am not sure about the number but it is stuck at some level”..

Someone advise me to use this library http://gmplib.org/ to solve the issue but I couldn’t use the library as I am beginner in programming field..

Can you advise me about a solution or how to use this library step by step..

Thanks.

[Alex Edwards]

I was just going to say "wouldn't implementing a scientific notation class be optimal?" But I guess we're staying away from STL's so... I think your instructor may expect you to represent the factorial as a collection of other factorials or.... as a string.

Either that or you will have to subtract the MAX VALUE of the positive number storing data type (a long long I believe), as you increase the factorial...

For example...

if you overshoot the amount a long long can hold, store the value in another long long variable after subtraction the max value of a long long...

You'll have to keep doing this until you finally get the number... but I suppose that's too much work.

It might be better to just search for an API that will handle this. This is obviously a lesson about data types and how to work around their limits.

[ice661666]

Put in your mind that the result from the factorial will be added to a formula (i.e. I will add it or multiply it by another values, so the will program will calculate the factorial as a part of the complete formula “the big formula”). I am saying that to let you know that the array solution is not helpful in my case.

I have searched for the available data types that can handle the result but nothing until now.

thanks.

[Alex Edwards]

Put in your mind that the result from the factorial will be added to a formula (i.e. I will add it or multiply it by another values, so the will program will calculate the factorial as a part of the complete formula “the big formula”). I am saying that to let you know that the array solution is not helpful in my case.

I have searched for the available data types that can handle the result but nothing until now.

thanks.

I wonder if you can calculate the value and immediately return/store it in a string?

But now I'm seriously beginning to think that you'll need scientific notation. This is an interesting assignment...

[Lerner]

The type long double can hold up to 19 digits.

If that's not enough you could declare your own data type/class. Call the new class BigInt or HugeInt or whatever and use a string, as suggested, to hold char representations the individual digits. Overload the math operator *, and maybe the + operator, too, for the class and you should be set.

[Alex Edwards]

The type long double can hold up to 19 digits.

If that's not enough you could declare your own data type/class. Call the new class BigInt or HugeInt or whatever and use a string, as suggested, to hold char representations the individual digits. Overload the math operator *, and maybe the + operator, too, for the class and you should be set.

255! is 3.3 * 10^503, long double wont be enough =/

You'll definitely have to do "character addition" where--

you'll have to set up a class or method that accepts a number and calculates it via chars.

maybe something like...

const int MAX = /*number of digit locations for 255!*/, index = 0;
char *aString = new char[MAX];

//assuming factorial(int) is the method to do the factorial...
for(int i = 0; i < factorial(255); i++)//so long as I doesn't reach the max value...
{
        if(aString[index] != '9')
        {
             //Increment the first position by 1
             aString[index] = (char)(static_cast<int>(aString[index] + 1);
        }
        else
        {
                //check the current characters
               for(int j = 0; j < current; j++)
               {  
                    //if the number to increment is 9, set to 0 and increment the one after it by 1
                    if(aString[i] == '9')
                    {
                        aString[i] = '0';
                        aString[i + 1] = (char)(static_cast<int>(aString[i + 1] + 1);
                    }//process will repeat for chars equal to 9 after increment
               }
         }
}

If the above code works, cool. If not, be warned that I DIDN'T compile, but the idea is simple--

-> Make an array of chars thats big enough for the amount of characters in 255!
-> Fill the char array with char values, easiest when done incrementally (like shown above)
-> parse the string using one of the standard streams and use for a calculation.

[tesuji]

255! is 3.3 * 10^503, long double wont be enough =/

Wrong!

long double is stored in 80 bits. So their numbers have approximately 19 digits of precision in a range from 3.37 x 10-4932 to 1.18 x 10+4932 !

The poor problem is that neither printf nor cout of M$ visual c++ is able to print out long double values! So you need to changes compilers to do your homework. This is the result of 255 ! computed and printed out from a program compiled with well designed compiler:

1 Faculty is 1.00000000000000E+0000
2 Faculty is 2.00000000000000E+0000
3 Faculty is 6.00000000000000E+0000
4 Faculty is 2.40000000000000E+0001
5 Faculty is 1.20000000000000E+0002
6 Faculty is 7.20000000000000E+0002
7 Faculty is 5.04000000000000E+0003
8 Faculty is 4.03200000000000E+0004
9 Faculty is 3.62880000000000E+0005
10 Faculty is 3.62880000000000E+0006
11 Faculty is 3.99168000000000E+0007
12 Faculty is 4.79001600000000E+0008
13 Faculty is 6.22702080000000E+0009
...
21 Faculty is 5.10909421717094E+0019
22 Faculty is 1.12400072777760E+0021
23 Faculty is 2.58520167388850E+0022
. . .
100 Faculty is 9.33262154439442E+0157
101 Faculty is 9.42594775983836E+0159
102 Faculty is 9.61446671503513E+0161
. . .
200 Faculty is 7.88657867364791E+0374
201 Faculty is 1.58520231340323E+0377
202 Faculty is 3.20210867307452E+0379
. . .
249 Faculty is 1.29314250436364E+0490
250 Faculty is 3.23285626090911E+0492
251 Faculty is 8.11446921488186E+0494
252 Faculty is 2.04484624215023E+0497
253 Faculty is 5.17346099264008E+0499
254 Faculty is 1.31405909213058E+0502
255 Faculty is 3.35085068493298E+0504

Happy computing !

krs,
tesu

[Alex Edwards]

Wrong!

long double is stored in 80 bits. So their numbers have approximately 19 digits of precision in a range from 3.37 x 10-4932 to 1.18 x 10+4932 !

The poor problem is that neither printf nor cout of M$ visual c++ is able to print out long double values! So you need to changes compilers to do your homework. This is the result of 255 ! computed and printed out from a program compiled with well designed compiler:

1 Faculty is 1.00000000000000E+0000
2 Faculty is 2.00000000000000E+0000
3 Faculty is 6.00000000000000E+0000
4 Faculty is 2.40000000000000E+0001
5 Faculty is 1.20000000000000E+0002
6 Faculty is 7.20000000000000E+0002
7 Faculty is 5.04000000000000E+0003
8 Faculty is 4.03200000000000E+0004
9 Faculty is 3.62880000000000E+0005
10 Faculty is 3.62880000000000E+0006
11 Faculty is 3.99168000000000E+0007
12 Faculty is 4.79001600000000E+0008
13 Faculty is 6.22702080000000E+0009
...
21 Faculty is 5.10909421717094E+0019
22 Faculty is 1.12400072777760E+0021
23 Faculty is 2.58520167388850E+0022
. . .
100 Faculty is 9.33262154439442E+0157
101 Faculty is 9.42594775983836E+0159
102 Faculty is 9.61446671503513E+0161
. . .
200 Faculty is 7.88657867364791E+0374
201 Faculty is 1.58520231340323E+0377
202 Faculty is 3.20210867307452E+0379
. . .
249 Faculty is 1.29314250436364E+0490
250 Faculty is 3.23285626090911E+0492
251 Faculty is 8.11446921488186E+0494
252 Faculty is 2.04484624215023E+0497
253 Faculty is 5.17346099264008E+0499
254 Faculty is 1.31405909213058E+0502
255 Faculty is 3.35085068493298E+0504

Happy computing !

krs,
tesu

If you're going to make a statement like that you should supply a link to the compiler =/

Also, for my above code it needs and edit. I never incremented current @_@.

Either way, if this is true then the above code wont matter. Supply the compiler soon! I need a new one anyways =P

[mitrmkar]

The poor problem is that neither printf nor cout of M$ visual c++ is able to print out long double values!

Surprisingly, at some point M$ dropped support for 80 bit long double, nowadays long double and double are equivalent (64 bits) (although distinct types).

[tesuji]

If you're going to make a statement like that you should supply a link to the compiler =/

Also, for my above code it needs and edit. I never incremented current @_@.

Either way, if this is true then the above code wont matter. Supply the compiler soon! I need a new one anyways =P

I dont care this code. Particularly it does not meet the requirements of the questioner. You may try this one:

int main(int argc, char* argv[])
{ int n=255; long double f=1.0;
   for (int i=1;i<=n;i++){
      f*=i; printf("%3i factorial is %25.18Le\n",i,f);
   }
   return 0;
}
I have to apologized deeply for having mistaken "faculty" for "factorial".

And to be more informed about technical standards you may study "What Every Computer Scientist Should Know about Floating-Point Arithmetic" by Goldberg, for example there: http://www.validlab.com/ goldberg/paper.ps. Especially on page 191 you will find the parameters of standardized floating point numbers.

krs,
tesu

p.s.
it s c++builder (or delphi or ;) )
which also have computed: 1000 factorial is 4.023872600770937732e+2567