Inaccurate C++ factorial program

  • A+
Category:Languages

I wrote an implementation of the following tutorial: LINK

Basically, since C/C++ does not have BIG Integer we are storing the factorial decimal values in an array. This is equivalent to writing a multiplication that performs the multiplication kids are taught at schools.

Problem: It works fine for values up to 17! after that (18!, 19!,... ) it does not output correct values.

#include <iostream> using namespace std;  int main(){     int fact[1000]={1};     int n; scanf("%d", &n); //n are the number of factorials we will calculate     while(n--){         int number; scanf("%d", &number);   //scan the number         if(number == 0) printf("%d", 1);         int flag = number;         int index = 0, length = 0;         //following lines we find the length of the entered number         while(flag!=0){             fact[index] = flag%10;             flag /= 10;             index++; length++;         }         //following lines are the multiplication code         while(number>1){             index = 0;             int temp = 0;             number--;             for(index = 0; index<length; index++){                 int x = (fact[index] * number) + temp;                 fact[index] = x%10;                 temp = x/10;             }             //here we append the carry over left from multiplication             while(temp){                 fact[index] = temp%10;                 temp /= 10;                 length++;             }         }         //print the array from most to least significant digit         for(int i = length-1; i>=0; i--){             printf("%d", fact[i]);         }         printf("/n");     }     return 0; } 

 


For a start, you need to be very careful with:

long long int x = (fact[index] * number) + temp; 

Since fact[], number and temp are all int types, the calculation will be done as an int and only widened to a long long when placing the value into x.

You would be better off with:

long long x = fact[index]; x *= number; x += temp; 

That way, it becomes a long long early enough that the calculations will be done with that type.


However, that doesn't actually fix your problem, so let's modify your code a little to see where the problem lies:

#include <iostream> using namespace std;  int main(){     int fact[1000]={1};     int n = 18, numberx = 0;     while(n-- > 0){         int number = ++numberx;         if(number == 0) { printf("%d", 1); continue; }         int flag = number;         int index = 0, length = 0;         //following lines we find the length of the entered number         while(flag!=0){             fact[index] = flag%10;             flag /= 10;             index++; length++;         }         //following lines are the multiplication code         while(number>1){             index = 0;             int temp = 0;             number--;             for(index = 0; index<length; index++){                 long long int x = fact[index];                 x *= number;                 x += temp;                 fact[index] = x%10;                 temp = x/10;             }             //here we append the carry over left from multiplication             while(temp){                 fact[index] = temp%10;                 temp /= 10;                 length++;             }         }         //print the array from most to least significant digit         printf("%d! = ", number);         for(int i = length-1; i>=0; i--){             printf("%d ", fact[i]);         }         printf("/n");     }     return 0; } 

Running this gives you:

1! = 1 2! = 2 3! = 6 4! = 2 4 5! = 1 2 0 6! = 7 2 0 7! = 5 0 4 0 8! = 4 0 3 2 0 9! = 3 6 2 8 8 0 10! = 3 6 2 8 8 0 0 11! = 3 9 9 1 6 8 0 0 12! = 4 7 9 0 0 1 6 0 0 13! = 6 2 2 7 0 2 0 8 0 0 14! = 8 7 1 7 8 2 9 1 2 0 0 15! = 1 3 0 7 6 7 4 3 6 8 0 0 0 16! = 2 0 9 2 2 7 8 9 8 8 8 0 0 0 17! = 3 5 5 6 8 7 4 2 8 0 9 6 0 0 0 18! = 1 9 9 1 0 4 7 1 7 3 8 5 7 2 8 0 0 0 

which is, as you state okay up until 18!, where if fails. And, in fact, you can see the ratio between 17! and 18! is about 500 rather than 18 so that's where we should look.

Let's first strip out the extraneous stuff by starting at 17!. That can be done simply by changing a couple of starting values:

int n = 2, numberx = 16; 

and that gives:

17! = 3 5 5 6 8 7 4 2 8 0 9 6 0 0 0 18! = 1 9 9 1 0 4 7 1 7 3 8 5 7 2 8 0 0 0 

Then we can add debug code to see what's happening, outputting temporary results along the way. The main loop can become:

while(number>1){     index = 0;     int temp = 0;     number--;     if (numberx > 17) printf("/n");     for(index = 0; index<length; index++){         if (numberx > 17) printf("index %d fact[] %d number %d temp %d", index, fact[index], number, temp);         long long int x = fact[index];         x *= number;         x += temp;         fact[index] = x%10;         temp = x/10;         if (numberx > 17) printf(" -> fact[] %d temp %d/n", fact[index], temp);     }     //here we append the carry over left from multiplication     while(temp){         fact[index] = temp%10;         temp /= 10;         length++;     }     if (numberx > 17) {         printf("temp: ");         for(int i = length-1; i>=0; i--){             printf("%d ", fact[i]);         }         printf("/n");     } } 

This shows you *exactly where things start to go wrong (// bits are added by me):

17! = 3 5 5 6 8 7 4 2 8 0 9 6 0 0 0  index 0 fact[] 8 number 17 temp 0 -> fact[] 6 temp 13 index 1 fact[] 1 number 17 temp 13 -> fact[] 0 temp 3 temp: 3 0 6 // okay: 18 * 17 = 306  index 0 fact[] 6 number 16 temp 0 -> fact[] 6 temp 9 index 1 fact[] 0 number 16 temp 9 -> fact[] 9 temp 0 index 2 fact[] 3 number 16 temp 0 -> fact[] 8 temp 4 temp: 4 8 9 6 // okay 306 * 16 = 4896  index 0 fact[] 6 number 15 temp 0 -> fact[] 0 temp 9 index 1 fact[] 9 number 15 temp 9 -> fact[] 4 temp 14 index 2 fact[] 8 number 15 temp 14 -> fact[] 4 temp 13 index 3 fact[] 4 number 15 temp 13 -> fact[] 3 temp 7 temp: 7 3 4 4 0 // okay 4896 * 15 = 73440  index 0 fact[] 0 number 14 temp 0 -> fact[] 0 temp 0 index 1 fact[] 4 number 14 temp 0 -> fact[] 6 temp 5 index 2 fact[] 4 number 14 temp 5 -> fact[] 1 temp 6 index 3 fact[] 3 number 14 temp 6 -> fact[] 8 temp 4 index 4 fact[] 7 number 14 temp 4 -> fact[] 2 temp 10 temp: 8 1 2 8 1 6 0 // no good: 73440 * 14 = 10128160 !!!       1 0 2 8 1 6 0 // is what it should be 

With a bit of thought, it appears to be the point where the final "carry" from the multiplication is greater than nine, meaning it's almost certainly in the code for handling that:

while(temp){     fact[index] = temp%10;     temp /= 10;     length++; } 

Thinking about that (and comparing it to other code that changes index and length together), it becomes obvious - even though you increase the length of the array, you're not increasing the index. That means, for a final carry of ten or more, the subsequent carry will not populate the correct index, it will simply overwrite the same index each time.

This can be seen here:

temp: 8 1 2 8 1 6 0 // no good: 73440 * 14 = 10128160 !!!       1 0 2 8 1 6 0 // is what it should be 

where it will have placed the zero (10 % 10) at that second location (increasing the length) but then placed the one (10 / 10) at the same index, leaving the 8 at whatever value it had before.

So, if we increment index as well, what do we see (going back to the less verbose code)?

1! = 1 2! = 2 3! = 6 4! = 2 4 5! = 1 2 0 6! = 7 2 0 7! = 5 0 4 0 8! = 4 0 3 2 0 9! = 3 6 2 8 8 0 10! = 3 6 2 8 8 0 0 11! = 3 9 9 1 6 8 0 0 12! = 4 7 9 0 0 1 6 0 0 13! = 6 2 2 7 0 2 0 8 0 0 14! = 8 7 1 7 8 2 9 1 2 0 0 15! = 1 3 0 7 6 7 4 3 6 8 0 0 0 16! = 2 0 9 2 2 7 8 9 8 8 8 0 0 0 17! = 3 5 5 6 8 7 4 2 8 0 9 6 0 0 0 18! = 6 4 0 2 3 7 3 7 0 5 7 2 8 0 0 0 19! = 1 2 1 6 4 5 1 0 0 4 0 8 8 3 2 0 0 0 20! = 2 4 3 2 9 0 2 0 0 8 1 7 6 6 4 0 0 0 0 

That solves your specific problem and hopefully provides some education on debugging as well :-)

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: