C / Find 190! (factorial) in c programming

Question

I try to find 190! in C.

I define my variable to long double, but I see that it calculate (correctly) only to 172!:

After that, I got #INF00000...`

There is any way to do it?

Answer 1

It's really just a few lines of code to implement enough of a bigint implementation to compute factorials. Here's code that prints the first 200 factorials.

#include <stdio.h>

int mult(int n, size_t size, unsigned char *data) {
    int carry = 0;
    for (int i = 0; i < size; i++) {
        int result = data[i] * n + carry;
        data[i] = result % 100;
        carry = (result - data[i]) / 100;
    }
    return carry != 0;
}

void print(size_t size, unsigned char *data) {
    int first = 1;
    for (int i = 0; i < size; i++) {
        int d = data[size - i - 1];
        if (first && d == 0) continue;
        printf("%0*d", first && d < 10 ? 1 : 2, d);
        first = 0;
    }
}

int main(int argc, char*argv[]) {
    for (int fact = 1; fact <= 200; fact++) {
        unsigned char data[1000] = {1};
        for (int i = 1; i <= fact; i++) {
            if (mult(i, sizeof(data), data)) {
                return 1;
            }
        }
        printf("%d! = ", fact);
        print(sizeof(data), data);
        printf("\n");
    }
    return 0;
}

Answer 2

Factorial of 190 is:

9680322675255249156123346514615331205418161260462873360750859919944104623425228207640470674933540169424682360525991982916161596983449594045525553704253602287443197783274656957056546338783001340434094795097553229620273057440272298773179365935914105128629426348958748638226084106818484328004851174161755668480000000000000000000000000000000000000000000000

or, 1170 bits. So that's not gonna fit in any built in type. You really need a bigint library to represent things this large.

Answer 3

One way is to use arbitrary-precision arithmetic. You can implement it yourself or use one of these libraries.

Note that even the value of 172! you got is most probably only approximately correct.

Answer 4

This sample (Win32/Visual Studio Express) program shows that error becomes a !23 with an unsigned 64 bit:

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


unsigned __int64 fact( unsigned __int64 in) {
    if( in == 1 ) {
        return 1;
    }
    unsigned __int64 f = fact(in-1);
    printf( "!%3I64u = %20I64u = 0x%016I64X\n", in-1, f, f );
    return in*f;
}

int main( int argc, char * argv[] ) {
    unsigned __int64 in = atoi(argv[1]);
    unsigned __int64 f  = fact(in);
    printf( "!%3I64u = %20I64u = 0x%016I64X\n", in, f, f );
    return 0;
}

run:

C:\> Factorial 23
!  1 =                    1 = 0x0000000000000001
!  2 =                    2 = 0x0000000000000002
!  3 =                    6 = 0x0000000000000006
!  4 =                   24 = 0x0000000000000018
!  5 =                  120 = 0x0000000000000078
!  6 =                  720 = 0x00000000000002D0
!  7 =                 5040 = 0x00000000000013B0
!  8 =                40320 = 0x0000000000009D80
!  9 =               362880 = 0x0000000000058980
! 10 =              3628800 = 0x0000000000375F00
! 11 =             39916800 = 0x0000000002611500
! 12 =            479001600 = 0x000000001C8CFC00
! 13 =           6227020800 = 0x000000017328CC00
! 14 =          87178291200 = 0x000000144C3B2800
! 15 =        1307674368000 = 0x0000013077775800
! 16 =       20922789888000 = 0x0000130777758000
! 17 =      355687428096000 = 0x0001437EEECD8000
! 18 =     6402373705728000 = 0x0016BEECCA730000
! 19 =   121645100408832000 = 0x01B02B9306890000
! 20 =  2432902008176640000 = 0x21C3677C82B40000
! 21 = 14197454024290336768 = 0xC5077D36B8C40000
! 22 = 17196083355034583040 = 0xEEA4C2B3E0D80000
! 23 =  8128291617894825984 = 0x70CD7E2933680000

!21 and after are wrong.