Factorial in C programming

Hello everybody

I need a C programme which will compute factorials.
I searched for it on the internet, and found some programmes, but
they don't seem to work when I try factorial 13, instead when I tried factorial 100 I get the answer 0.

Can anybody help, create a programme which works for all numbers.

[dave_dm]

A possible fac.c to print the factorial of the first command-line argument:

#include <stdio.h>
#include <gmp.h>

int main (int argc, char **argv)
{
        mpz_t x;

        mpz_init (x);
        mpz_fac_ui (x, atoi (argv[1]));
        gmp_printf ("%Zd\n", x);
        mpz_clear (x);

        return 0;
}

You'll need to compile and install the gmp library first. Then do

gcc fac.c -o fac -lgmp

If you're running windows then you'll have to do all this under cygwin.

Dave

[dave_dm]

Btw if you only need a few values then use the applet at www.swox.com/gmp. If you're only interested in the source then look at mpz/fac_ui.c in the gmp distribution.

Dave

Thanks

How do I compile the GMP library, and I'm not sure what you mean by cygwin. I'm using Dev-c++ compiler.

Isn't there an easier way of producing factorial programmes. I'm quite new to C programming, hence I only know the basics.

[dave_dm]

Sorry, I don't have a windows machine so I can't walk you through this. Search the forums for "gmp" and "cygwin", it's been done. Btw it's quicker to type "cygwin" into google than post "I'm not sure what you mean by cygwin" on the forums and wait for a reply.

What I told you is IMO by far the easiest way to compute factorials in C. If you want to use Python then it's also easy (but involves you installing Python).

The underlying problem is that 32-bit unsigned longs can only hold numbers less than 2^32, i.e. 13! and above will overflow. So "raw C" isn't good enough - you need a bignum library.

Dave

[ewmayer]

Originally Posted by dave_dm

The underlying problem is that 32-bit unsigned longs can only hold numbers less than 2^32, i.e. 13! and above will overflow. So "raw C" isn't good enough - you need a bignum library.

You don't necessarily need all that machinery. Unsigned long long (64-bit int, typically) is supported my most C compilers and is in fact required as part of the C99 standard - although that'll only allow you to go up to 20! before incurring overflow. If you need somewhat larger values and they don't need to be exact, use double-precision floats - that allows up to around 170! with roughly 15 digits of precision. If you need exact factorials larger than long long can accommodate but not mammoth (i.e. no more than a few thousand digits), you can write a simple multiprecision scalar-times-vector routine, where the accumulated factorials are stored in base-2^32 or 2^64 form. If you only need the values, not a routine you can incorporate into some code, simply use some desktop utility like unix bc or the PARI package.

[geoff]

Here is one using base 10 multiplication, the number is stored as a text string and multiplied digit by digit. It is very slow, to make it fast you need to use base 2^16 or 2^32, and write a routine to convert into base 10 for printing.

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

int multiply(char *str, int len, int n)
{
  int c, i;

  for (c = i = 0; i < len; i++)
  {
    c += n * (str[i] - '0');
    str[i] = c % 10 + '0';
    c /= 10;
  }

  while (c > 0)
  {
    str[i++] = c % 10 + '0';
    c /= 10;
  }

  return i;
}

void usage_error(void)
{
  printf("Usage: 'factorial n', n a non-negative integer.\n");
  exit(1);
}

void memory_error(void)
{
  printf("Failed to allocate enough memory.\n");
  exit(1);
}

int main(int argc, char **argv)
{
  int n, len, buf = 10000;
  char *str;

  if (argc < 2)
    usage_error();

  n = atoi(argv[1]);
  if (n < 0)
    usage_error();

  str = (char *)malloc(buf);
  if (str == NULL)
    memory_error();

  str[0] = '1';
  len = 1;

  while (n > 1)
  {
    if (len > buf - 10)
    {
      buf *= 2;
      str = (char *)realloc(str, buf);
      if (str == NULL)
        memory_error();
    }

    len = multiply(str, len, n--);
  }

  while (len >= 1)
    putchar(str[--len]);
  putchar('\n');

  return 0;
}