F#中int类型的溢出问题

Question

我正在做一些作业，需要在F#中制作一个组合函数。我已经完成了阶乘函数的编写，但是当我使用阶乘函数计算大数值时（例如20），似乎会发生溢出。虽然我知道可以使用int64或float类型，但这将改变代码中所有输入的数据类型。请问应该使用哪种数据类型？

let rec Fact (a:int)=
   if (a = 0) then 1 else a*Fact(a-1);;

let combo (n:int) (k:int)=
   if (n = 0) then 0 else (Fact n)/((Fact k)*(Fact (n-k)));;

现在的代码中，当我输入combo 20 5之后，它给出了2147这个明显错误的答案。我查看了阶乘函数，当我输入20时，它会给我一个很大的负数。非常感谢您能提供帮助。提前致谢。

- user999999

---

“20！”大约是“2.4 * 10 ^ 18”，比“int”要大得多，所以溢出并不奇怪。虽然我不太明白你的问题是什么。你问应该使用哪种类型，但同时又拒绝使用另一种类型。嗯？ - Fyodor Soikin

Answer 1

首先，如果你想避免出现意外，你可以在文件的顶部打开 Checked 模块。这将重新定义数值运算符，使它们执行溢出检查 - 这样你就会得到一个异常而不是意外的数字：

open Microsoft.FSharp.Core.Operators.Checked

正如Fyodor在评论中指出的那样，你不能用int来容纳20的阶乘，需要使用int64。然而，你的combo函数执行除法运算，这会使combo 20 5的结果变得足够小，可以适应int的范围。

一种选择是将Fact更改为使用int64，但保持combo作为一个接受和返回整数的函数 - 在调用Fact之前，您需要将它们转换为int64，然后在执行除法后再转换为int：

let rec Fact (a:int64) =
   if (a = 0L) then 1L else a * Fact(a-1L)

let combo (n:int) (k:int) =
   if (n = 0) then 0 else int (Fact (int64 n) / (Fact (int64 k) * Fact (int64 (n-k))))

现在您可以调用combo 20 5，并且您将得到15504作为结果。

编辑: 如其他答案中的 @pswg 所述，int64 也相当有限，因此您需要 BigInteger 来计算更大的阶乘。但是，对于您来说，相同的方法应该适用于 BigInteger。您可以将 combo 函数保留为返回 int 的函数，通过将 BigInteger 转换回 int 来实现。

- Tomas Petricek

Answer 2

您无法使用32位整数(int)来完成此操作。64位整数可以计算出20!，但在21!时将失败。数字变得太大了，增长也太快了。如果要继续进行下去，您需要使用System.Numerics.BigInteger（在F#中缩写为bigint）。

该参数可能保持为int以保持合理性，但您需要返回一个bigint：

let rec Fact (n : int) = 
    if n = 0 then bigint.One else (bigint n) * Fact (n - 1)

或者更加通俗易懂一点的说法：

let rec Fact = function | 0 -> bigint.One | n -> (bigint n) * Fact (n - 1)

现在，在您的Combo函数中，您需要内部使用这些bigint进行所有数学计算（幸运的是，整数除法在这种情况下就足够了）。

let Combo (n : int) (k : int) =
    if n = 0 then bigint.Zero else (Fact n) / ((Fact k) * (Fact (n - k)))

如果你真的想让Combo返回一个int，你可以在这里进行转换：

let Combo (n : int) (k : int) =
    if n = 0 then 0 else (Fact n) / ((Fact k) * (Fact (n - k))) |> int

例子：

Combo 20 5 // --> 15504
Combo 99 5 // --> 71523144 (would break if you used int64)

编辑: 通过重新思考您对Combo的实现，您可以从中获得一些重大的性能改进。请参见Math.SE上的这个问题以获取该实现的基础:

let ComboFast (n : int) (k : int) =
    let rec Combo_r (n : int) = function 
        | 0 -> bigint.One 
        | k -> (bigint n) * (Combo_r (n - 1) (k - 1)) / (bigint k)
    Combo_r n (if (2 * k) > n then n - k else k)

快速的基准测试表明，这个版本比上面基于Fact的版本要显著更快：

Function             Avg. Time (ms)
Combo 99 5            30.12570 
ComboFast 99 5         0.72364

- p.s.w.g