CODEWITHSUNDEEP
clong-integerfactorial
Joanne
Joanne

Reputation: 23

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

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.

Upvotes: 1

Views: 58

Answers (3)

chqrlie
chqrlie

Reputation: 144923

Computing n choose k for moderately large values of n with the default formula involves intermediary results that exceed the range of type long long. There are 2 solutions to address this issue:

  • use a bignum package that can deal with such large numbers
  • enumerate the factors and eliminate the divisors to reduce the computation to series of multiplications.

Here is a modified version with the latter approach:

#include <limits.h>
#include <stdio.h>

unsigned long long int combn(int n, int k) {
    if (k < 0 || n < 0 || k > n)
        return 0;

    // minimize computations
    if (k > n - k)
        k = n - k;

    int factors[k];
    // initialize factors of n! / (n - k)!
    for (int i = 0; i < k; i++)
        factors[i] = n - i;

    for (int i = k; i > 1; i--) {
        // find the multiple of i, divide it by i
        for (int j = 0; j < k; j++) {
            if (factors[j] % i == 0) {
                factors[j] /= i;
                break;
            }
        }
    }

    // compute result
    unsigned long long int C = 1;
    for (int i = 0; i < k; i++) {
        if (C > ULLONG_MAX / factors[i])
            return ULLONG_MAX;
        C = C * factors[i];
    }
    return C;
}

int main(void) {
    int n, k;
    printf("Enter n and k: ");
    if (scanf("%d %d", &n, &k) == 2) {
        unsigned long long C = combn(n, k);
        if (C == ULLONG_MAX)
            printf("overflow\n");
        else
            printf("%d choose %d is %llu\n", n, k, C);
    }
    return 0;
}

Output:

50 choose 10 is 10272278170

Upvotes: 0

OznOg
OznOg

Reputation: 4732

you overflow the long long capacity (and you code is mixing long long and int BTW)

you need to compute 50! which is ~ 3.10^64, thus far above max int (~2^9) and max long long int which is ~9.10^18. You need to use a special big integer library or rework your algo not to compute overflowed values (or do not use big values...)

Seems there are algorithm that can compute combination that fits a long long without overflowing; see: Calculating the Amount of Combinations

Upvotes: 1

O. Jones
O. Jones

Reputation: 108736

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.

Upvotes: 1

Related Questions