Maybe you will think,"how simple to calculate the factorial of a number!"And you just write a program like the following.
//Calculating the Factorial of A Large Number v1
#include <stdio.h>
unsigned long long int Factorial(unsigned long long int j);
int main(void)
{
unsigned long long int i;
printf("Input a nonnegative integer:");
scanf("%llu",&i);
printf("%llu!=%llu\n",i,Factorial(i));
return 0;
}
unsigned long long int Factorial(unsigned long long int j)
{
unsigned long long int k,result=1;
for(k=2;k<=j;k++)
result*=k;
return result;
}
Since we use "%llu" to control the formats of these numbers,we have acturally considered the precision.So there is priviously a problem,"as i becomes larger and larger,can the factorial of i be printed accurately?"Of course no,for numbers are stored in a computer with specific ranges the compiler allows.Here is an example of wrong result.
It's obvious that last digit of 25! should be 0,but in this result not.
Then,are there any ways to avoid accuracy losses?
Remenber how we expressed a number in the program Wenquxing Guessing Game?Through an array with enough elements,we can easily store a large number and print it.Then the improved code is following.
//Calculating the Factorial of A Large Number v2
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 100
//N means the maximal number of digits allowed for the value of a factorial
void OutputFactorial(int j);
int main(void)
{
int i;
do
printf("Input a nonnegative integer less than or equal to %d(maximum of int type):",INT_MAX);
while (scanf("%d",&i)!=1||i<0);
OutputFactorial(i);
printf("\n");
return 0;
}
void OutputFactorial(int j)
{
int k,m,carry=0,digit=1,array[N] ;
array[0]=1;
for(k=2;k<=j;k++)
{
for(m=0;m<digit;m++)
{
array[m]=array[m]*k+carry;
carry=array[m]/10;
array[m]%=10;
}
while (carry)
{
array[digit++]=carry%10;
carry/=10;
}
}
if (digit<=N)
{
printf("%d!=",j);
while (digit>=1)
printf("%d",array[--digit]);
}
else
printf("Sorry.The factorial has more than %d digits.It's not intended to output the result.",N);
}
Through this program,I did calculate some factorials successfully.But it seemed that the program didn't run as expected when I input a number out of range.For example,when I input the number 100,the result was beyond expection.
How can we explain the wrong result?To find the bug,I read the code carefully.And finally I
give the 3rd version.
//Calculating the Factorial of A Large Number v3
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 100
//N means the maximal number of digits allowed for the value of a factorial
void OutputFactorial(int j);
int main(void)
{
int i;
do
printf("Input a nonnegative integer less than or equal to %d(maximum of int type):",INT_MAX);
while (scanf("%d",&i)!=1||i<0);
OutputFactorial(i);
printf("\n");
return 0;
}
void OutputFactorial(int j)
{
int k,m,carry=0,digit=1,array[N] ;
array[0]=1;
for(k=2;k<=j;k++)
{
for(m=0;m<digit;m++)
{
array[m]=array[m]*k+carry;
carry=array[m]/10;
array[m]%=10;
}
while (carry>0&&digit<N)
{
array[digit++]=carry%10;
carry/=10;
}
}
if (digit>=N&&carry>0)
printf("Sorry.The factorial has more than %d digits.It's not intended to output the result.",N);
else
{
printf("%d!=",j);
while (digit>=1)
printf("%d",array[--digit]);
}
}
Do you know why I modified the program like this? I defined an array with N elements in the function OutputFactorial(j) but didn't check whether the subscript was out of range in the loop of 2nd version.So trouble came.
Although the 3rd version is improved,it remains some problems.For instance,if you input a character,not a number,then the program will fall into an endless loop.Actually,it's a problem caused by buffer.What's worse,theoretically the program could calculate the factorial of a number as large as INT_MAX,but the efficiency is extremely low so it's impossible for us to wait.In the meantime,It's assumed that the number inputted is not larger than INT_MAX,so the robustness of this program needs to be improved.
Do you have any ideas better than mine?Welcome to share!
