CODEWITHSUNDEEP
c
FoolishBeat
FoolishBeat

Reputation: 31

How to calculate this factorial

#include <stdio.h>
int main(){
    int n, v;
    printf("Please enter a value from 39 to 59: \n");
    scanf("%d", &n);
    printf("Please enter a value from 3 to 7: \n");
    scanf("%d", &v);

}

When I got those values from user, how can I perform this factorial calculation:

n! / ((n-v)! * v!))

I've tried different data types but apparently none can hold the result.

For example: n = 49, v=6. The result is: 13,983,816, but how can I go about getting it?

Upvotes: 0

Views: 95

Answers (4)

duffymo
duffymo

Reputation: 309028

You're best bet is to ditch the naive factorial implementations, usually based on recursion, and switch to one that returns the natural log of gamma function.

The gamma function is related to factorial: gamma(n) = (n-1)!

Best of all is natural log of gamma, because you can rewrite that expression like this: 

ln(n!/(n-v)!v!) = ln(n!) - ln((n-v)!) - ln(v!)

But 

(n-v)! = gamma(n-v+1)
n! = gamma(n+1)
v! = gamma(v+1)

So 

ln(n!/(n-v)!v!) = lngamma(n+1) - lngamma(n-v+1) - lngamma(v+1)

You can find an implemenation for lngamma in Numerical Recipes.

lngamma returns a double, so it'll fit even for larger values.

It should go without saying that you'll take exp() of both sides to get the original expression you want back.

Upvotes: 5

Keith Thompson
Keith Thompson

Reputation: 263647

In a comment, you've finally said that you don't need exact results.

Just use floating-point. The largest intermediate result you'll need to handle is 59!, which is about 1.3868e80; type double is more than big enough to hold that value.

Write a function like:

double factorial(int n);

(I presume you know how to implement it) and use that.

If you're going to be doing a lot of these calculations, you might want to cache the results by storing them in an array. If you define an array like:

double fact[60];

then you can store the value of N! in fact[N] for N from 0 to 59 -- and you can fill the entire array in about the time it would take to compute 59! just once. Otherwise, you'll be doing several dozen floating-point multiplications and divisions on each calculation -- which is trivial if you do it once, but could be significant if you do it, say, thousands or millions of times.

If you needed exact results, you could use an extended integer library like GNU MP, as others have suggested. Or you could use a language (like Python, for example) that has built-in support for arbitrary-length integers.

Or you could probably perform the multiplications and divisions in an order that avoids overflow; I don't know exactly how to do that, but since n! / ((n-v)! * v!)) is a common formula I strongly suspect that work has already been done.

Upvotes: 2

chux
chux

Reputation: 154602

@duffymo idea looked like too much fun to ignore: use lgamma() from <math.h>.

Results past maybe x=1e15, start to lose the trailing significant digits.. Still fun to be able to get 1000000.0!.

void factorial_expo(double x, double *significand, double *expo) {
    double y = lgamma(x+1);
    const static double ln10 = 2.3025850929940456840179914546844;
    y /= ln10;
    double ipart;
    double fpart = modf(y, &ipart);
    if (significand) *significand = pow(10.0, fpart);
    if (expo) *expo = ipart;
}

void facttest(double x) {
  printf("%.1f!  =  ", x);
  double significand, expo;
  factorial_expo(x, &significand, &expo);
  int digits = expo > 15 ? 15 : expo;
  if (digits < 1) digits++;
  printf("%.*fe%.0f\n", digits, significand, expo);
}


int main(void) {
  facttest(0.0);
  facttest(1.0);
  facttest(2.0);
  facttest(6.0);
  facttest(10.0);
  facttest(69.0);
  facttest(1000000.0);
  return 0;
}

0.0!  =  1.0e0
1.0!  =  1.0e0
2.0!  =  2.0e0
6.0!  =  7.20e2
10.0!  =  3.628800e6
69.0!  =  1.711224524281441e98
1000000.0!  =  8.263931668544735e5565708

Upvotes: 3

Vladyslav
Vladyslav

Reputation: 786

You can't work with such long numbers as 59! in simple way. However you can use special C libraries which are working with long numbers bigger than 8 bytes, for example GMP

Upvotes: 0

Related Questions