factorial for values greater than 16

This is a discussion on factorial for values greater than 16 within the C Programming forums, part of the General Programming Boards category; I have the below program to calculate factorial. It is working good for values upto 16. But when I give ...

  1. #1
    Dragon Rider jas_atwal's Avatar
    Join Date
    Nov 2007
    Location
    India
    Posts
    54

    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);
    }
    -------------------------------------------------------------------
    There are 10 kinds of people in this world....Those who understand binary and those who don't

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,854
    Arithmetic overflow perhaps?
    Factorial grows very quickly.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Dragon Rider jas_atwal's Avatar
    Join Date
    Nov 2007
    Location
    India
    Posts
    54
    Quote Originally Posted by Salem View Post
    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?
    -------------------------------------------------------------------
    There are 10 kinds of people in this world....Those who understand binary and those who don't

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,304
    Use "&#37;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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Banned
    Join Date
    Nov 2007
    Posts
    678
    Hey! Use Python
    Code:
    def factorial(n):
        f=1
        while n:
            f *= n
            n -= 1
        return f
    
    >>> factorial(25)
    >>> 15511210043330985984000000L
    Sorry. Bad joke.

  7. #7
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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.

  8. #8
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by foxman View Post
    ...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.

  9. #9
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with simple timer function
    By mike_g in forum C Programming
    Replies: 16
    Last Post: 01-15-2008, 12:16 PM
  2. About aes
    By gumit in forum C Programming
    Replies: 13
    Last Post: 10-24-2006, 04:42 PM
  3. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 01:00 AM
  4. SSH Hacker Activity!! AAHHH!!
    By Kleid-0 in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 03-06-2005, 03:53 PM
  5. How to change number data from base 256 to base 16?
    By ooosawaddee3 in forum C++ Programming
    Replies: 2
    Last Post: 11-05-2002, 12:19 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21