September 13th, 2012, 09:18 PM

Weird ouput from factorial function
Can somebody explain why I am getting this output for this factorial function...
Code:
#include <stdio.h>
unsigned long factorial(unsigned long n){
unsigned long i, x = 1;
for (i = 2; i <= n; ++i) {
x *= i;
}
return x;
}
int main(int argc, char* argv[]){
unsigned long i = 0;
for(i = 0; i < 47; i++){
unsigned long ans = factorial(i);
printf("%ld! is: %ld\n", i, ans);
}
return 0;
}
Sample of the output:
0! is: 1
1! is: 1
2! is: 2
3! is: 6
4! is: 24
5! is: 120
6! is: 720
7! is: 5040
8! is: 40320
9! is: 362880
10! is: 3628800
11! is: 39916800
12! is: 479001600
13! is: 6227020800
14! is: 87178291200
15! is: 1307674368000
16! is: 20922789888000
17! is: 355687428096000
18! is: 6402373705728000
19! is: 121645100408832000
20! is: 2432902008176640000
21! is: 4249290049419214848
22! is: 1250660718674968576
23! is: 8128291617894825984
24! is: 7835185981329244160
25! is: 7034535277573963776
26! is: 1569523520172457984
27! is: 5483646897237262336
28! is: 5968160532966932480
29! is: 7055958792655077376
30! is: 8764578968847253504
31! is: 4999213071378415616
32! is: 6045878379276664832
33! is: 3400198294675128320
34! is: 4926277576697053184
35! is: 6399018521010896896
36! is: 9003737871877668864
37! is: 1096907932701818880
38! is: 4789013295250014208
39! is: 2304077777655037952
40! is: 70609262346240000
41! is: 2894979756195840000
42! is: 7538058755741581312
43! is: 7904866829883932672
44! is: 2673996885588443136
45! is: 8797348664486920192
46! is: 1150331055211806720
Sometimes the factorial is negative, I thought maybe the number is too big or something but then other higher numbers are positive....
Linux ubuntu 12.04 GNU C compiler. Thanks for any help :)
September 13th, 2012, 09:51 PM

Two problems:
1. Overflow. Data types are of limited size, which a fixed number of bits, and hence a fixed and limited range of values. If you exceed that range, then you have overflow. Some languages will raise an exception to that and crash the program if you don't handle the exception. C is not one of those languages. Instead, you simply lose those upper bits that don't fit.
You're using unsigned long, which is probably 32 bits long and ranges up to a bit over 4 billion. Some compilers have a long long int with even more bits and even larger range. Look into that.
2. You're using the wrong format flag in printf. ans is declared as unsigned long, but with "%ld" you're telling printf to treat it as a signed long. Read up on Two's Complement, which is the common binary method to represent signed integers. In Two's Complement, the most significant bit (MSB) is the sign bit: if the sign bit is a 1, then it's a negative value, 0 for a positive. So when your unsigned long int exceeds the maximum value of a signed long int (which is, after all, what you're interpreting it as being), that MSB gets set to 1 and printf interprets the number as negative. Then you do actually overflow the unsigned long, the sign bit will sometimes be a zero and you will display a positive, and sometimes a one and you will display a negative.
What you need to do is to display the number as unsigned, eg "%lu". But that will only get you through an extra couple iterations, so you should attempt to use long long instead.
It may help examine what's happening in binary, or better in hex (it's much more readable). Looking at the last valid value, 2,432,902,008,176,640,000, which in hex is 0x21C3677C82B40000, we see that on your system the compiler uses 64bit longs. I don't know what a long long would be. In your compiler's include directory, open the limits.h file. That file contains definitions for the minimum and maximum values of each data type. Because some datatype sizes are implementationdependent, each limits.h could be different.
Comments on this post
September 13th, 2012, 09:51 PM

Originally Posted by murdell55
Sometimes the factorial is negative, I thought maybe the number is too big or something but then other higher numbers are positive....
"Too big" is exactly right. The largest number that can be represented as a 64bit unsigned integer is 2^641 = 18446744073709551615. The factorial of 30, on the other hand, is 265252859812191058636308480000000, which is slightly too big.
However, 30! mod 2^64 = 9682165104862298112, which is what your factorial function actually computes: unsigned integer arithmetic is ordinary arithmetic modulo 2^64 (assuming 64 bits). Now, you're wondering why it's negative. It isn't, but since you're printing it using the "%ld" specifier, the bits of your unsigned integer `ans' are being interpreted as a signed long integer, so naturally you're not getting the right output. (Use "%lu" for unsigned long arguments.) Since nonnegative integers up to 2**631 have the same representation in either signed or unsigned machine integers, you're fine until your code exits that range, at which point positive unsigned integers may show up as negative signed integers. Observe that
30! mod 2^64  2^64 = 9682165104862298112  2^64 = 8764578968847253504,
which is what your code outputs. This occurs because the signed integer 8764578968847253504 has the same binary representation as the unsigned integer 9682165104862298112 in 64bit two'scomplement arithmetic. (An unsigned 64bit integer in the range 2^63 <= x < 2^64 turns into x  2^64 when you take the same bits and interpret them as a two'scomplement signed integer.)
Comments on this post
September 13th, 2012, 10:00 PM

Aha OK I see. Thanks for the help guys.
September 14th, 2012, 09:32 AM

Link to gmp is a library for extended precision operations.
[code]
Code tags[/code] are essential for python code and Makefiles!