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

Question

我正在用 F# 做 Project Euler 问题 1：

Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

这是我的尝试：

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

val it : int = 233168

我朋友在Excel中计算的是3的倍数和5的倍数相加提取15的倍数，他用更大的上限向我挑战：求出所有3或5的倍数之和低于 1234567.

我试过这个：

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

System.OverflowException: Arithmetic operation resulted in an overflow.

第二次尝试：

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

error FS0010: Unexpected integer literal in pattern. Expected infix operator, quote symbol or other token.

令我惊讶的是，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

问题：

为什么 F# 程序会导致 "Arithmetic operation resulted in an overflow"？
是否可以在 F# 中编写上述 python 等效解决方案？
解决此问题的惯用 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

另外对于数字less then 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

让我试着回答你的问题：

为什么F#程序会导致"Arithmetic operation resulted in an overflow"？

由于 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

是否可以在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

解决此问题的惯用 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

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

How to handle Arithmetic operation OverflowException in F#?

python

f#