mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2005-04-07, 13:04   #1
Unregistered
 

32·733 Posts
Wink 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.
  Reply With Quote
Old 2005-04-07, 13:10   #2
dave_dm
 
May 2004

1208 Posts
Default

A possible fac.c to print the factorial of the first command-line argument:
Code:
#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
Code:
gcc fac.c -o fac -lgmp
If you're running windows then you'll have to do all this under cygwin.

Dave
dave_dm is offline   Reply With Quote
Old 2005-04-07, 13:12   #3
dave_dm
 
May 2004

24·5 Posts
Default

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
dave_dm is offline   Reply With Quote
Old 2005-04-07, 13:14   #4
Unregistered
 

11·283 Posts
Talking Thanks

Thanks
  Reply With Quote
Old 2005-04-07, 13:39   #5
Unregistered
 

2·11·229 Posts
Unhappy Yes but...

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.
  Reply With Quote
Old 2005-04-07, 14:14   #6
dave_dm
 
May 2004

24·5 Posts
Default

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
dave_dm is offline   Reply With Quote
Old 2005-04-07, 14:42   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

3·53·31 Posts
Default

Quote:
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.
ewmayer is offline   Reply With Quote
Old 2005-04-09, 20:13   #8
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

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.
Code:
#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;
}
geoff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Multi-Factorial Search rogue And now for something completely different 1 2015-06-02 23:51
Factorial puzzle henryzz Puzzles 5 2015-04-02 12:58
Factorial primes Unregistered Information & Answers 2 2011-09-11 21:32
Factorial mfgoode Puzzles 6 2007-07-24 14:24
Factorial problem xilman Puzzles 12 2003-07-20 20:22

All times are UTC. The time now is 05:30.

Sun Apr 18 05:30:31 UTC 2021 up 10 days, 11 mins, 0 users, load averages: 1.75, 1.55, 1.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.