algorithm - Delphi 阶乘运算精度

Question

情况

我需要为我的关于组合和排列的数学类(class)编写一个程序。如果你想计算它们，你必须处理阶乘，我写了这个典型的递归函数:

//TCombinazioni is a class that I have created to solve Combinations
function TCombinazioni.fattoriale(const x: integer): Int64;
begin

 Result:= 1;
 if x > 0 then
  begin
   Result:= fattoriale(x-1)*x;
  end;

end;

---

问题

我在我的类(class) TCombinazioni 中编写了这段代码:

function TCombinazioni.getSoluzioni: Int64;
begin
  //C(n,k) = (n+k-1)! / (k! * (n-1)!)
  Result := fattoriale(n+k-1) div (fattoriale(k) * fattoriale(n-1));    
end;

代码本身是正确的，如果 n 和 k(均为整数)较小，则函数返回所需的数字。当您输入大数字时就会出现问题，因为阶乘增长得非常快。在这里你可以看到一个例子。

在左侧您可以看到输出 11440 是正确的，但在右侧则不正确。我知道这种计算是“危险的”，因为我正在处理大整数，即使它们被声明为 Int64。

据我所知，Int64 类型是最大的整数类型，但如果我尝试使用大整数进行计算，还有其他可能性吗？

可能的解决方案

1. 很简单，例如我可以设置 n 和 k 不能大于 10(但我不想这样做)

2. 使用浮点运算。我在想我可以使用 getSoluzioni 函数和 Extended 返回值(而不是 Int64)。由于这些操作的结果必须是一个整数，我可以检查 double 的小数部分是否为零。如果不是，我不会接受结果。

我正在考虑第 2 点，因为 Extended 的值范围比 Int64 更广。 Delphi 中的 Extended 除法比 Int64 除法更精确吗？

例如，我希望能够在至少 n=14 和 k=8 的情况下获得不错的结果。

Answer 1

Extended 有 64 位精度，所以没有增益。另外，它使编码变得非常复杂。您当然可以通过重写计算以在进行时进行除法来降低计算溢出的可能性。这将在一定程度上有所帮助。因此，当您在分子和分母中找到相同的因子时，只需将其从两者中删除即可。

但您真正需要的是一个大型整数库。在网上搜索找到一个。