如何用C语言计算大的nPr？

Question

我用C语言编写了一个计算两个数字的nPr的函数，你能帮我把它修改成处理大数吗？

我需要能够计算一个高达1x10^12的值--我尝试过许多不同的数据类型，而且非常困难！

#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;
        }
     }

谢谢

J

更新：--这些是不重复的排列，

我也试过

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;
    }
 }

然而，这似乎没有任何区别。

Answer 1

您可能希望使用大群进行计算，或者使用GMP库。如果切换到C++，就可以使用熟悉的a+b表示法，甚至可以使用GMP的C++类接口。如果您停留在纯C中，则需要谨慎地使用特定的例程，例如添加添加。

顺便说一句，有些语言(例如普通Lisp)本机支持大型语言(不需要修改处理普通数字的源代码)。您可能想尝试使用SBCL (至少在Linux上)。

当然，bignum算法(一个非常复杂的主题)比本地算法慢。

Bignums在C中本机不受支持，您需要使用一个库(或者实现自己的库，这是一种非意义的:好的大型算法很难理解和实现，所以更好地使用现有的库)。

PS。long long不会有什么帮助，因为它仍然是64位。一些GCC编译器和目标处理器可能支持int128，即128个位整数，但您确实需要大数。

Answer 2

在除法时，您不需要完全评估阶乘，这降低了整数溢出的风险(以及更有效)：

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);
}