When I calculate a large factorial, why do I get a negative number?

Question

So, simple procedure, calculate a factorial number. Code is as follows.

int calcFactorial(int num)
{
    int total = 1;

    if (num == 0)
    {
     return 0;
    }

    for (num; num > 0; num--)
    {
     total *= num;
    }

    return total;
}

Now, this works fine and dandy (There are certainly quicker and more elegant solutions, but this works for me) for most numbers. However when inputting larger numbers such as 250 it, to put it bluntly, craps out. Now, the first couple factorial "bits" for 250 are { 250, 62250, 15126750, 15438000, 3813186000 } for reference.

My code spits out { 250, 62250, 15126750, 15438000, -481781296 } which is obviously off. My first suspicion was perhaps that I had breached the limit of a 32 bit integer, but given that 2^32 is 4294967296 I don't think so. The only thing I can think of is perhaps that it breaches a signed 32-bit limit, but shouldn't it be able to think about this sort of thing? If being signed is the problem I can solve this by making the integer unsigned but this would only be a temporary solution, as the next iteration yields 938043756000 which is far above the 4294967296 limit.

So, is my problem the signed limit? If so, what can I do to calculate large numbers (Though I've a "LargeInteger" class I made a while ago that may be suited!) without coming across this problem again?

Answer 1

2^32 doesn't give you the limit for signed integers.

The signed integer limit is actually 2147483647 (if you're developing on Windows using the MS tools, other toolsuites/platforms would have their own limits that are probably similar).

You'll need a C++ large number library like this one.

Answer 2

If i remember well:

unsigned short int = max 65535

unsigned int = max 4294967295

unsigned long = max 4294967295

unsigned long long (Int64 )= max 18446744073709551615

Edited source:

Int/Long Max values

Modern Compiler Variable

Answer 3

Yes, you hit the limit. An int in C++ is, by definition, signed. And, uh, no, C++ does not think, ever. If you tell it to do a thing, it will do it, even if it is obviously wrong.

Consider using a large number library. There are many of them around for C++.

Answer 4

If you don't specify signed or unsigned, the default is signed. You can modify this using a command line switch on your compiler.

Just remember, C (or C++) is a very low-level language and does precisely what you tell it to do. If you tell it to store this value in a signed int, that's what it will do. You as the programmer have to figure out when that's a problem. It's not the language's job.

Answer 5

In addition to the other comments, I'd like to point out two serious bugs in your code.

• You have no guard against negative numbers.
• The factorial of zero is one, not zero.

Answer 6

My Windows calculator (Start-Run-Calc) tells me that

hex (3813186000) =         E34899D0
hex (-481781296) = FFFFFFFFE34899D0

So yes, the cause is the signed limit. Since factorials can by definition only be positive, and can only be calculated for positive numbers, both the argument and the return value should be unsigned numbers anyway. (I know that everybody uses int i = 0 in for loops, so do I. But that left aside, we should use always unsigned variables if the value can not be negative, it's good practice IMO).

The general problem with factorials is, that they can easily generate very large numbers. You could use a float, thus sacrificing precision but avoiding the integer overflow problem.

Oh wait, according to what I wrote above, you should make that an unsigned float ;-)

Answer 7

You have an overflow problem. Factorials can easily exceed the limits of integers. You could change your function to return doubles, but that will only buy you a little more room. In applications, you often need multiply factorials times very small numbers where the end result will fit inside a double but the intermediate steps will not. Here's an article that explains how to handle this situation: http://www.johndcook.com/blog/2008/04/24/how-to-calculate-binomial-probabilities/