How to calculate large nPr in C?

Question

I have written a function to calculate the nPr of two numbers in C, can you please help me adapt it to handle large numbers?

I need to be able to calculate a value of upto 1x10^12 - I have tried many different data types and am very stuck!

#include<stdio.h>
    #include<math.h>

int main()
    {
        long int n=49,k=6;
            printf("%li nPr %li = %li\n\n",n,k,nPr(n,k));

        return 0;

    }      

long nPr(long int n, long int k);
     long nPr(long int n, long int k){

        if (n < 0 ){
            printf("\nERROR - n is less than 0\n\n");
            return -1;
        }

        if (k > n ){
            printf("\nERROR - k is greater than n\n\n");
            return -1;
        }

        else {
            long int i,result = 1,c=n+1-k;

            for(i=c; i<=n; i++)
            {
                result = result * i;
            }
            return result;
        }
     }

Thanks

J

UPDATE: These are permutations WITHOUT repition,

also I tried

long long nPr(long long int n, long long int k);
long long nPr(long long int n, long long int k){

    if (n < 0 ){
        printf("\nERROR - n is less than 0\n\n");
        return -1;
    }

    if (k > n ){
        printf("\nERROR - k is greater than n\n\n");
        return -1;
    }

    else {
        long long int i,result = 1,c=n+1-k;

        for(i=c; i<=n; i++)
        {
            result = result * i;
        }
        return result;
    }
 }

however it did not seem to make any difference

@SethCarnegie No, [permutation with repetition.](http://www.mathsisfun.com/combinatorics/combinations-permutations.html) — , Oct 21 '12 at 16:50
What compiler are you using? Did you try "long long" for 64-bit number? — akhisp, Oct 21 '12 at 16:56
permutations are without repition, using GNU GCC compiler, long long had no effect if I used it correctly (showed how I tried to change it in above edit) — user1763328, Oct 21 '12 at 17:54
You don't need to calculate the factorials fully to calculate npr/ncr: http://stackoverflow.com/questions/26311984/permutation-and-combination-in-c-sharp/26312275#26312275 — weston, Apr 09 '15 at 13:26

Basile Starynkevitch · Answer 1 · 2012-10-21T19:37:14.637

You may want to compute using bignums, perhaps using the GMP library. If you switch to C++, you could use the familiar a+b notation even for bignums, using the C++ class interface to GMP. If you stay in pure C, you'll need to carefully use specific routines, e.g. mpz_add for addition.

BTW, some languages (e.g. Common Lisp) natively support bignums (without the need to modify the source code working on ordinary numbers). You might want to try with SBCL (at least on Linux).

Of course, bignum arithmetic (a very complex subject) is slower than native arithmetic.

Bignums are not supported natively in C, you need to use a library (or implement itself yours, which is a non-sense: good algorithms for bignums are hard to understand and to implement, so better use an existing library).

PS. long long won't really help, since it is still 64 bits. Some GCC compilers and target processors may support __int128 i.e. 128 bits integers, but you really need bignums.

weston · Answer 2 · 2017-06-05T14:00:40.633

You don't need to fully evaluate the factorials when dividing, this reduces the risk of integer overflow (as well as being more efficient):

long factorialDivision(int topFactorial, int divisorFactorial)
{
    long result = 1;
    int i;
    for (i = topFactorial; i > divisorFactorial; i--)
        result *= i;
    return result;
}

long factorial(int i)
{
    if (i <= 1)
        return 1;
    return i * factorial(i - 1);
}

long nPr(int n, int r)
{
    // naive: return factorial(n) / factorial(n - r);
    return factorialDivision(n, n - r);
}

long nCr(int n, int r)
{
    // naive: return factorial(n) / factorial(r) * factorial(n - r);
    return nPr(n, r) / factorial(r);
}

How to calculate large nPr in C?

2 Answers2

Linked