Factorial using GMP library (bignum)

May 13, 2010 by santosh

I recently tried to compute factorial of large numbers. But I realized that using native data types this is not possible. Either you have to do the computation in software or find a machine with real big registers. But we just have only 64 bit machine in normal use. So I started poking into the GMP library and wrote the following factorial code.


#include <stdio.h>
#include <stdarg.h>
#include <gmp.h>
int main (void)
{
mpz_t fact, num;
unsigned long i;
size_t len;
mpz_init(num);
mpz_init_set_ui(fact, 1); /* Initialise fact to 1, default is 0 */
for (i = 1; i <= 999; i++) {
mpz_mul_ui(fact, fact, i);
}
len = mpz_out_str(stdout, 10, fact);
printf("\nNumber of digits: %ld\n", len);
return 0;
}


I tried till 999, 9999, 99999. But I got a segmentation fault at the end. I am investigating why it would segfault. May be the mpz_t type has a limitation, and we have to re-alloc it. I will keep you posted through twitter (@santosh).

Once you start using the GMP data types, you cannot go for primitive operatives for arithmetic and relational operations. There are functions provided to do the very same.

$ gcc factorial.c -lgmp
$ time ./a.out
Segmentation fault (core dumped)

real 5m27.125s
user 5m26.669s
sys 0m0.105s
$