Java：避免阶乘溢出

我应该优化下面的代码，以便它计算中心二项系数达到整数的最大值（最多n = 16）。Java：避免阶乘溢出

public static int factorial(int n) 
{ 
    int result= 1; 

    for(int i = 2; i <= n; i++) result *= i; 

    return result; 
} 

public static int centralbinom(int n) 
{ 
    return factorial(2*n)/(factorial(n) * factorial(n)); 
}

当然，我得到一个溢出每n> 6. 如何“打破”阶乘功能，使不具有处理大的数字，如为2n = 2 * 16 = 32？

还是有更好的方法来计算中央二项式系数？

来源

2014-05-01 WalterWhite

你得到7的溢出！？ – NWard

@NWard 14！（2 * N） –

你有没有想过使用BigInteger？ –

下面是几个优化，除了可以使用BigIntegers可能会降低你的计算做的，在你大多数情况下可能溢出，你可能在你的程序中。

由于您需要阶乘（n）至少两次。计算一次并将其存储在一个变量中。

因子（2 * n）中有因子（n）。由于您已经计算了阶乘（n），因此您需要先计算阶乘（2n ... n），然后再乘以阶乘（n）。以下是一个如何完成的方法。

//Pseudocode 

//find factorial of n given I know already till k 

int findFactorial(n, k) { 
    int result = 1 
    for i n to 1 

    if(i==k) 
     break; 

    result = result * n; 
    return result 
} 

//factorial(2*n) = facorial(n, k) * factorial(k)

这将减少你的计算了很多，在情况下，如果你希望你的程序不能有溢出，你可以用BigIntegers走。

来源

2014-05-01 20:01:51

如果您需要大数量的阶乘，你必须使用BigInteger类计算结果：

public static BigInteger factorial(int n) { 
    BigInteger result = BigInteger.ONE; 

    for (int i = 2; i <= n; ++i) { 
     result = result.multiply(BigInteger.valueOf(i)); 
    } 

    return result; 
}

来源

2014-05-01 19:56:12

如果17的中央二项式系数大于整数max，并且只需要计算17个数，那么显而易见的解决方案就是查找表。创建一个包含n = 0到16的中心二项式系数的17元素数组。我认为您会发现这个解决方案非常高效。

你可以在这里找到它们的列表。 http://oeis.org/A000984

来源

2014-05-01 20:10:43 mattarod

只是通过伽玛压缩你的阶乘。将gamma设置为10就足够好了

public static double factorial(int n, double gamma) 
{ 
    double result= 1; 
    double gammaInv = 1.0/gamma; 
    for(int i = 2; i <= n; i++) result *= pow(i,gammaInv); 

    return result; 
} 

public static int centralbinom(int n, double gamma) 
{ 
    return pow(factorial(2*n,gamma)/
     (factorial(n,gamma) * factorial(n),gamma), 
     gamma); 
}

来源

2018-01-30 11:13:57

Java：避免阶乘溢出

回答

相关问题