#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    2
    Rep Power
    0

    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 :)
  2. #2
  3. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,253
    Rep Power
    2222
    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 64-bit 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 implementation-dependent, each limits.h could be different.

    Comments on this post

    • Lux Perpetua agrees : Simulpost!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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 64-bit unsigned integer is 2^64-1 = 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**63-1 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 64-bit two's-complement arithmetic. (An unsigned 64-bit 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's-complement signed integer.)

    Comments on this post

    • dwise1_aol agrees : [i]Dang![/i] Even though mine took longer to write {grin}. Two perspectives on the same theme. Should help him to understand it better.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    2
    Rep Power
    0
    Aha OK I see. Thanks for the help guys.
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,966
    Rep Power
    481
    Link to gmp is a library for extended precision operations.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo