Counting error while calculating large number(e.g. 50!)

Question

My code is doing well when I enter small numbers like 10 choose 2, but when it comes to 50 choose 10, its result is wrong, can you tell me what's wrong here?

#include <stdio.h>

long long int factorial(int n);
long long int combn(int n, int k);

int main(void) {
    int n = 0;
    int k = 0;
    printf("Enter n and k:\n");
    scanf("%d %d", &n, &k);
    combn(n, k);
}

long long int combn(int n, int k) {
    long long int C = 0;

    C = factorial(n) / (factorial(k) * factorial(n - k));
    printf("C %d choose %d = %ld\n", n, k, C);
}

long long int factorial(int n) {
    if (n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

combn(50, 10) should be 10272278170.

Answer 1

50! is a very large number, taking almost 150 bits to represent, The long long datatype provides only 64 bits. So, C can't do the computation the way you're doing it; it overflows.

You can use an arbitrary-precision arithmetic package library for this purpose. This kind of library represents numbers with variable numbers of bits, and offers operations that don't overflow.

gmp -- the Gnu MP Bignum library, is an example of such a library. There are others. Here's how you might do it with gmp. (not debugged).

#include "gmp.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int main(int argc, char * argv[]){
  uint n;
  uint m;

  mpz_t nn;
  mpz_t mmn;
  mpz_t mmm;
  mpz_t denom;
  mpz_t result;
  char * str;

  if (argc <= 2){
    printf ("Usage: %s <number> <number> \n", argv[0]);
    return 1;
  }
  n = atoi(argv[1]);
  m = atoi(argv[2]);

  mpz_fac_ui (nn,n);          /* nn = n! */
  mpz_fac_ui (mmn,n-m);       /* mmn = (n-m)! */
  mpz_fac_ui (mmm,m);         /* mmm = m! */

  mpz_mul(denom, mmm, mmn);       /* denom = mmn * mmm */
  mpz_fdiv_q(result, nn, denom);  /* result = nn / denom */

  str =  mpz_get_str (null, 10, const mpz_t result);
  printf ("deal %d from %d: %s combinations\n", n,m, str);
  free (str);
  mpz_clear(nn);
  mpz_clear(mmm);
  mpz_clear(mmn);
  mpz_clear(denom);
  mpz_clear(result);

  return 0;
}

Another possibility: take advantage of the fact that (n!) / (n-m)! is equal to the product of the integers from (m+1 to n). For example 50!/ 47! is 48 * 49 * 50. That should, in many cases, keep your integers representable in 64 bits. And, even better when you're doing this kind of computer arithmetic, you don't have to perform an actual division operation because it falls right out of the formulas.