f# 中的 int 溢出

Question

我正在做一些作业，我们应该在 F# 中创建一个组合函数。我已经降低了阶乘函数，但是一旦我得到一个大数字来使用阶乘，它似乎就会溢出。（比方说 20）我知道我可以使用 int64 或浮点数，但这会改变代码中的所有输入。我应该使用什么数据类型？

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)));;

现在在代码中，当我执行组合 20 5 时；；它给了我 2147。这显然是错误的答案。我查看了阶乘函数，当我在其中输入 20 时，它给了我一个很大的负数。任何帮助将非常感激。提前致谢。

Answer 1

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

open Microsoft.FSharp.Core.Operators.Checked

正如 Fyodor 在评论中指出的那样，您不能在 int 中拟合 20 的阶乘，而您需要 int64。但是，您的 combo 函数随后执行除法，这将使 combo 20 5 的结果足够小以适合 int.

一个选项是将 Fact 更改为使用 int64，但将 combo 保留为接受整数和 returns 整数的函数 - 您需要转换它们在调用 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。您可以通过从 BigInteger 转换回 int.

将 combo 函数保留为 returns int 的函数

Answer 2

您根本无法使用 32 位整数 (int) 做到这一点。一个 64 位整数将使您达到 20!，但会在 21! 时失败。数字变得太大、太快。要更进一步，您需要使用 System.Numerics.BigInteger（在 F# 中缩写为 bigint）。

该参数可能保持为 int 是合理的，但您需要 return 一个 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)))

如果你真的想把Comboreturn变成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 的实现，您可以从中获得一些重大的性能改进。有关此实现的基础，请参阅 this question on 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

f# 中的 int 溢出

Overflow of an int in f#

f#

overflow