0

So, the factorial of a number is given as the following n!=n*(n-1)*(n-2)..(n-n). Which I implemented in C as the following:

unsigned int factorial(int n) {
    unsigned int product = 1;
    for(int i = n; i > 0; i--) {
        product *= i;
    }
    return product;
}

Then the permutation is given as the following:

enter image description here

Which I implemented as the following in C:

// Given the example of p(5, 3) => 5!/3! which is the same as 5*4, that is how I implemented this below
unsigned int permutation(int N, int n) {
    int temp = N-n;
    unsigned int product = 1;
    for(int i = N; i > temp; i--) { // only compute values from N * (N-1)... (N-n) based on the previous math above
        product *= i;
    }
    return product;
}

The Combination is given as the following, where k is refers to r in above notation:

enter image description here

Which I implemented as the following in C:

int combination(int N, int n) {
    unsigned int temp = permutation(N, n);
    unsigned int product = factorial(n);
    return temp / product;
}

The problem I'm having is I'm trying to take the Combination of nCr(31, 24) = 2629575, which in my C code is the same as permuation(31, 24) / factorial(24) which should equal 1.6315x10^30 / 6.2044x10^23 = 2629575. But I think I'm getting an integer overload because my permutation(31, 24) returns 1279262720, and my factorial(24) returns 3519021056. How do I compute the combination and permutation's of large numbers? Is there a way to store a massive amount of memory aside in C for the factorial and permutations? Lastly, my little TI-30XS calculator can handle these calculations fine, storing numbers up to 1e99, how does it store it?

notMyName
  • 690
  • 2
  • 6
  • 17
  • You can't do 31! with `int` or even with `long long int`. You need a bigint library. You can gain *some* headroom by cancelling out, for example 9! / 6! is only 9x8x7. – Weather Vane Sep 09 '20 at 19:34
  • @WeatherVane , well how do products compute these values? My little 20$ calculator can compute 69! – notMyName Sep 09 '20 at 19:36
  • Your little calculator only computers 69! approximately. I bet it doesn't display all the digits. C can do that with `double` but it's approximate just like the calculator! – user253751 Sep 09 '20 at 19:37
  • Hint, though: you can use maths. What is n! / (n-k!) if you write both of those out as 1x2x3x4x...? And what happens when you multiply and divide by the same number? – user253751 Sep 09 '20 at 19:37
  • @user253751, Ya I know that, already wrote it down in my implementation. Ya, it can only display 10 digits but It is accurate in multiplying large numbers. – notMyName Sep 09 '20 at 19:39
  • Your factorial expression incorrectly includes (n-n) as a term, which of course is incorrect since n-n is zero and would force the entire product to zero. n! is the product of 1 through n, inclusive. If n is zero, this is an empty product whose value is the multiplicative identity 1. Your `factorial` function does not contain this error and should function correctly. – Tom Karzes Sep 09 '20 at 20:11
  • If you want exact results, then you need to use integer values. You can use `unsigned long long` to extend the representable range of values. Beyond that, you would need to use an extended precision integer representation. Your calculator uses a format that discards low-order digits (or bits), so while it can "handle" larger values, the result is inexact. You can do the same thing in C by using `double` instead of an integer type. – Tom Karzes Sep 09 '20 at 20:17

0 Answers0