避免使用C中的置换(nPr，nCr)函数进行整数溢出 [英] Avoiding interger overflow with permutation (nPr, nCr) functions in C

问题描述

我正在尝试执行一些与统计相关的功能，因此我可以执行一些相关的程序(即:概率的统计计算，为任意深度生成帕斯卡三角形等).

I am attempting to do some statistics-related functions so I can carry out a few related procedures (ie: statistics calculations for probabilities, generate Pascal's triangle for an arbitrary depth, etc).

我遇到了可能会处理溢出的问题.例如，如果我要计算(n = 30，p = 1)的nPr，我知道可以将其减少为:

I have encountered an issue where I am likely dealing with overflow. For example, if I want to calculate nPr for (n=30,p=1), I know that I can reduce it to:

30P1 = 30! / (30 - 1)!
     = 30! / (29)!
     = 30! / 29!
     = 30

但是，当使用下面的函数进行计算时，由于整数溢出，我总是会得到无效的值.是否有不需要使用库来支持任意大数目的变通办法?我已经阅读了有关gamma函数的其他文章，但是找不到具体示例.

However, when calculating using the functions below, it looks like I will always get invalid values due to integer overflow. Are there any workarounds that don't require the use of a library to support arbitrarily large numbers? I've read up a bit in other posts on the gamma functions, but couldn't find concrete examples.

int factorial(int n) {
   return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}


int nCr(int n, int r) {
   return (nPr(n,r) / factorial(r));
   //return factorial(n) / factorial(r) / factorial(n-r));
}


int nPr(int n, int r) {
   return (factorial(n) / factorial(n-r));
}

推荐答案

您看起来像在正确的轨道上，所以您可以进行以下操作:

You look like you are on the right track, so here you go:

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

int nCr(int n, int r) {
   if(r>n) {
      printf("FATAL ERROR"); return 0;
     }       
   if(n==0 || r==0 || n==r) {
      return 1;
   } else {
      return (int)lround( ((double)n/(double)(n-r)/(double)r) * exp(lgamma(n) - lgamma(n-r) - lgamma(r)));
   }
}


int nPr(int n, int r) {
   if(r>n) {printf("FATAL ERROR"; return 0;}
   if(n==0 || r==0) {
      return 1;
   } else {
      if (n==r) {
         r = n - 1;
      }
      return (int)lround( ((double)n/(double)(n-r)) * exp(lgamma(n) - lgamma(n-r)));
   }
}

要编译，请执行:gcc -lm myFile.c && ./a.out

请注意，结果的准确性受double数据类型的位深度限制.您应该能够由此获得良好的结果，但是要警告:用long long unsigned替换上面的所有int不一定代表对于n,r较大的值都可以保证准确的结果.在某个时候，您仍然需要一些数学库来处理任意大的值，但这应该有助于避免较小的输入值.

Note that the accuracy of your results is limited by the bit-depth of the double data type. You should be able to get good results with this, but be warned: replacing all the ints above with long long unsigned may not necessarily guarantee accurate results for larger values of n,r. At some point, you will still need some math library to handle arbitrarily large values, but this should help you avoid that for smaller input values.

这篇关于避免使用C中的置换(nPr，nCr)函数进行整数溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！