8

I am trying to find the numbers till 100! (factorial) but after 20! it gives an error as the value is too large to handle. How can I store such a number?

Jeff Mercado
  • 129,526
  • 32
  • 251
  • 272
Rishabh
  • 3,752
  • 4
  • 47
  • 74
  • 2
    Floating-point or multi-precision library... – Mysticial Nov 15 '11 at 09:19
  • 1
    What do you plan to do with the factorial afterwards? – jfs Nov 15 '11 at 09:22
  • First thing, that comes to my mind for such questions - why `C`? You need this as a part of something bigger, or you just need the values? Because `python` or `scheme` or many other languages will do this for you extremely fast and without any problems. – Kiril Kirov Nov 15 '11 at 09:22
  • Use GMP, the GNU Multi Precision library. I hacked together [this](https://gist.github.com/iwillspeak/5374227) to compute factorials with it a while ago. – Will Jul 13 '13 at 12:01

4 Answers4

12

20 factorial is 19 digits long. 100 factorial is 158 digits long, taking up 500 bits! It's actually: 

933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000
00000000

None of the standard types will work for you here, what you'll have to do is implement your own routine for handling such large numbers.

For example you will need to accept that multiplying two 32 bit values together may result in a 64 bit result.

This was coommon practice for calculating large numbers in the days of 8 bit processors. Its referred to as arbitrary precision arithemtic.

Here's a link to describe how this was done. Admittedly it's for assembler, but it still holds true here. You'll need to take into account the default sizes of int on your system.

ChrisBD
  • 9,104
  • 3
  • 22
  • 35
10

At least on Linux, a possible multi-precision library could be GMP (it also works on Solaris, Windows, MacOSX, etc...).

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
  • And for more libraries, Wikipedia has a nice list for different languages: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries – wormsparty Nov 15 '11 at 09:25
1

How would you do it on paper?
Doing multiplications with numbers 160-digits long is not that hard for a computer.

Try writing your own function or use an existing library.

pmg
  • 106,608
  • 13
  • 126
  • 198
  • 4
    I would write this as comment. No offence :) – Kiril Kirov Nov 15 '11 at 09:28
  • I'm not sure that naive approaches are enough. I did read quickly a book on multi-precision arithmetic, and the actual algorithms are much better -complexity wise- than naive ones, but are absolutely non-intuitive. (the math involved is non-trivial). Also, actual implementations may use machine-specific (e.g. some assembly code for addition with carry, ...) or system-specific tricks – Basile Starynkevitch Nov 15 '11 at 09:29
  • 1
    Basile: I agree, but Rishabh (the OP) is, apparently, a newcomer to programming. Writing his own function would be a fun learning experience. @Kiril: no offence taken. – pmg Nov 15 '11 at 09:33
-3

This code will help up to 170!. Use double for the factorial function, because normal int or long int will not support that factorial result, double will support up to 1.7e308.

#include<stdio.h>

double fact(int k){
    int i;
    double f=1;
    for(i=1;i<=k;i++) f=f*i;
    return (f);
}
int main(){
    int i;
    for(i=1;i<=65;i++)
    printf("%d! = %.3lf\n",i,fact(i));
    return 0;
}
Neil
  • 54,642
  • 8
  • 60
  • 72
sharjis Ibne Wadud
  • 1
  • 1