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

Answer 1

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.