factorial for values greater than 16

I have the below program to calculate factorial. It is working good for values upto 16. But when I give a value greater than 16, like 17 the output is in negative. e.g for 17 i get -288522240. Why is this?

Code:

---

#include<stdlib.h>
#include<stdio.h>

int factorial(int);

int main(){
        int i,j;
        printf("Enter a number to calculate factorial:\n");
        scanf("%d",&i);
        j=factorial(i);
        printf("Factorial is %d\n",j);
        return(0);
}

int factorial(int x){
        int i, j=1;

        for ( i = x; i > 1; i--)
        {
                j = j*i;
        }
        return(j);
}

---

Arithmetic overflow perhaps?
Factorial grows very quickly.

Quote:

---

Originally Posted by Salem

Arithmetic overflow perhaps?
Factorial grows very quickly.

---

Yes, you are very correct. it is Integer overflow. I tried to use long type instead of int in hope that i may be able to increase this limit from 16 to a little more. But did not work.
Anybody please tell me is it possible to make a program that overcomes this restriction?

Two possibilities: If you are using gcc, you could try "long long", which will give you a bit more digits. Use "%lld" to print it on a Linux system - I think "%I64d" is the right format on Windows, but it's been a while since I used that on Windows.

Alternatively, and definitely more portable/flexible, is to use a "double", which allows a range of 10 to the power of 308 or some such - suffice to say, LARGE numbers. factorial of a more than a hundred should be OK here.

--
Mats

Quote:

---

Use "%lld" to print it on a Linux system - I think "%I64d" is the right format on Windows, but it's been a while since I used that on Windows.

---

It should be %lld too since this is standard in C99.

There is another option: use an arbitrary precision arithmetic library like the GMP.

Hey! Use Python :D

Code:

---

def factorial(n):
    f=1
    while n:
        f *= n
        n -= 1
    return f

>>> factorial(25)
>>> 15511210043330985984000000L

---

Sorry. Bad joke. ;) :D

I once did a program who could calculate factorial of "any" number in assembly language. But i don't remember exactly why i did it in assembly.

By the way, what system/machine are you running for being able to calculate (16!) correctly but not (17!) ? Because you need at least 45 bits to store (16!) and you need at least 49 bits to store (17!) ? 48 bits int ? Didn't know that was common. ;)

Anyway, all the options list above are valid.

Quote:

---

Originally Posted by foxman

...what system/machine are you running for being able to calculate (16!) correctly but not (17!) ?...

---

In fact, with 32-bit ints (which would be my guess, given the symptoms), code like the posted program gives the following values

Code:

---

11 ->    39916800  (OK)
12 ->  479001600  (OK)
13 ->  1932053504  (Should be 6227020800)
14 ->  1278945280  (Should be 87178291200)
15 ->  2004310016  (Should be 1307674368000)
16 ->  2004189184  (Should be 20922789888000)
17 ->  -288522240  (Should be 355687428096000)

---

So, everything above 12 factorial is incorrect, but the overflowed values don't show up as negative until you feed 17 to the function.

D.

Yeah in fact i was a little bit sarcastic when talking about 48-bits ints. I wanted to point out that's not because something seems to display a correct value that this value is necessarily correct. :)

Oh and i have remember why i did a program who could calculate factorial in assembly language. It was mostly for the IA-32 MUL instruction, where you multiply two 32-bits and get the answer in a 64-bits (EDX:EAX), which is something you don't have with C language. That is great.