如何处理 F# 中的算术运算溢出异常

Question

我正在F#中做欧拉项目问题1：

3 和 5 的倍数

如果我们列出所有低于 10 的 3 或 5 倍数的自然数，我们得到 3、5、6 和 9。这些倍数的总和是 23。

找到 1000 以下 3 或 5 的所有倍数的总和。

这是我的尝试：

[1..999]
    |> List.filter (fun x -> x%3 * x%5 = 0)
    |> List.sum
val it : int = 233168

我的朋友在 Excel 中通过将 3 的倍数和 5 的倍数相加来计算它，提取 15 的倍数，他用更大的上限向我提出挑战：在 1234567 下面找到 3 或 5 的所有倍数的总和。

我试过这个：

[1..1234567]
     |> List.filter (fun x -> x%3 * x%5 = 0)
     |> List.sum

System.OverflowException：算术运算导致溢出。

第二次尝试：

let mutable result = 0
for x < 1000 do
    if  x%3 * x%5 = 0 then result = result + x

错误 FS0010：模式中出现意外的整数文本。预期的中缀运算符、引号或其他标记。

令我惊讶的是，Python可以很好地处理这个问题并且非常高效：

sum(x for x in range(1234567) if x%3 * x%5 == 0)
# 355636612814L
%time sum(x for x in range(1234567) if x%3 * x%5 == 0)
Wall time: 401 ms
Out: 355636612814L

问题：

1. 为什么 F# 程序会导致"算术运算导致溢出"？
2. 是否可以用 F# 编写上述 python 等效解决方案？
解决此问题
3. 的惯用 F# 方法是什么？

Answer 1

你应该对大数字使用 bigint，像这样

[1I..1234567I] 
    |> List.filter (fun x -> x % 3I * x % 5I = 0I) 
    |> List.sum

或（可读性较差）

[bigint  1..bigint 1234567] 
    |> List.filter (fun x -> x % bigint 3 * x % bigint 5 = bigint 0) 
    |> List.sum

同样对于小于 9,223,372,036,854,775,807 的数字，您可以使用 int64 类型（带 L 后缀），使用 int64 可以提高整体性能

[1L..1234567L] 
    |> List.filter (fun x -> x % 3L * x % 5L = 0L) 
    |> List.sum

Answer 2

在我的机器上，Python 代码的简单翻译运行的时间只有一半，158 毫秒（而 Python 为 317 毫秒）。

seq { 
    for x in 0L..1234566L do 
        if x % 3L * x % 5L = 0L then
            yield x
}
|> Seq.sum

这个可以说更惯用的代码仍然比你的Python运行得更快（220毫秒）。

seq { 0L .. 1234566L }
|> Seq.filter (fun x -> x % 3L * x % 5L = 0L)
|> Seq.sum

即使是 LINQ 版本也更快（221 毫秒）。

query {
    for x in 0L .. 1234566L do
    where (x % 3L * x % 5L = 0L)
    sumBy x
}

Answer 3

让我试着回答你的问题：

1. 为什么 F# 程序会导致"算术运算导致溢出"？

溢出错误是由于 32 位有符号整数的可表示范围限制 （2^31-1 = 2,147,483,647） 而发生的。 当排除上限为 1,234,567 时，答案如下：

Sum of all natural numbers up to 1234567 divisible by 3 or by 5 is 355,636,612,814
Result was computed in 12 ms

2. 是否可以用 F# 编写上述 python 等效解决方案？

这是类似于Python实现的完整程序。 它可以说是用命令式风格编写的，但它可以快速完成工作。

open System.Diagnostics
[<EntryPoint>]
let main argv = 
   let limit_exclusive = 1234567
   let limit = limit_exclusive - 1
   let divisor1 = 3
   let divisor2 = 5
   let stopwatch = Stopwatch.StartNew()
   let mutable sum = 0UL
   for x = 1 to limit do 
      if (x % divisor1 = 0) || (x % divisor2 = 0) then 
         sum <- sum + uint64 x
   stopwatch.Stop()
   printfn "Sum of all natural numbers up to %d divisible by %d or by %d is %d" limit_exclusive divisor1 divisor2 sum
   printfn "Result was computed in %d ms" stopwatch.ElapsedMilliseconds
   0 // return an integer exit code
Sum of all natural numbers up to 1234567 divisible by 3 or by 5 is 355,636,612,814
Result was computed in 12 ms

解决此问题
3. 的惯用 F# 方法是什么？

由于 F# 是一种多范式语言，它允许人们直观地或靠近机器或介于两者之间的任何其他语言来表达算法。 我想借此机会概述另一种方法，这种方法对某些人来说可能更直观，但会产生较低的性能指标。

   let seq1 = seq { 0 .. divisor1 .. limit }
   let seq2 = seq { 0 .. divisor2 .. limit }
   let both = Seq.append seq1 seq2
   let sum = both
             |> Seq.distinct
             |> Seq.map uint64
             |> Seq.sum
Sum of all natural numbers up to 1234567 divisible by 3 or by 5 is 355,636,612,814
Result was computed in 535 ms