- A+

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