views:

1767

answers:

7

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?

+16  A: 

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.

Stewart Johnson
For the curious, that number (2,147,483,647) is 2^31 - 1. The limit for unsigned integers is 2^32 - 1.
Graeme Perrow
A: 

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

Daok
In most modern compilers, an int is the same as a long.
Graeme Perrow
long long is a INT64 in MSDN documentation. My values are ok with modern compilers too. Have a nice day
Daok
Sorry this is plain wrong. Always refer to your compiler documentation for the CPU architecture you are working on. You don't even appear to be right for visual C++:http://msdn.microsoft.com/en-us/library/s3f49ktz(VS.80).aspx
tonylo
i've seen you've been editing... still this data should be caveated...
tonylo
@Daok: Last time I checked (10 years ago) an 'int' was 32 bits. :) Remember, the standard says sizeof(int) >= 2 and sizeof(int) <= sizeof(long), so in most 32-bit systems 'int' is 32-bit to match the native register size.
efotinis
My C++ is old but I have edited to display the difference between Short int and int. Now confusion should be over.
Daok
You're not even reading your own references.http://home.att.net/~jackklein/c/inttypes.html#intWho is right? On any given compiler, one or the other could be right. On some compilers, both would be wrong. I know of one compiler for a 24 bit DSP where an int has 24 bits.
tonylo
+7  A: 

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++.

OregonGhost
LOL! 'C++ does not think, ever.' Great answer!
Treb
+4  A: 

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.

Graeme Perrow
+13  A: 

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.
Ovid
I forgot about the fact that 0! = 1, but as said by Treb factorials are, by definition, non-negative numbers. But, one bug down!
Peter C.
+1  A: 

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 ;-)

Treb
+1  A: 

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/

John D. Cook