Java：避免階乘溢出

Question

我應該優化下面的代碼，以便它計算中心二項係數達到整數的最大值（最多n = 16）。

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？

還是有更好的方法來計算中央二項式係數？

Answer 1

下面是幾個優化，除了可以使用BigIntegers可能會降低你的計算做的，在你大多數情況下可能溢出，你可能在你的程序中。

1. 由於您需要階乘（n）至少兩次。計算一次並將其存儲在一個變量中。

2. 因子（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走。

Answer 2

如果您需要大數量的階乘，你必須使用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; 
} 

Answer 3

如果17的中央二項式係數大於整數max，並且只需要計算17個數，那麼顯而易見的解決方案就是查找表。創建一個包含n = 0到16的中心二項式係數的17元素數組。我認爲您會發現這個解決方案非常高效。

你可以在這裏找到它們的列表。 http://oeis.org/A000984

Answer 4

只是通過伽瑪壓縮你的階乘。 將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); 
}