Как обрабатывать арифметическую операцию OverflowException в F#?

Question

Как обрабатывать арифметическую операцию OverflowException в F#?

Я делаю задачу Эйлера проекта 1 в F#:

Кратные 3 и 5

Если мы перечислим все натуральные числа ниже 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих кратных равна 23.

Найдите сумму всех кратных 3 или 5 ниже 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: арифметическая операция привела к переполнению.

Вторая попытка:

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

Вопрос:

почему программа F# приводит к тому, что"арифметическая операция привела к переполнению"?

можно ли написать вышеупомянутое эквивалентное решение python в F#?

каков идиоматический F# способ решения этой проблемы?

452 3

python

3 ответов:

Comments

Ничего не найдено.

segrived · Accepted Answer · 2015-06-15 17:16:09

Вы должны использовать 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

Daniel · Accepted Answer · 2015-06-15 18:39:41

Простой перевод вашего кода Python выполняется в два раза быстрее, 158 мс (против 317 мс для Python) на моей машине.
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
}

GregC · Accepted Answer · 2015-08-28 00:06:00

Позвольте мне попытаться ответить на ваши вопросы:

почему программа 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
возможно ли написать вышеупомянутое эквивалентное решение python в F#?

Вот полная программа, которая похожа на реализацию 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# является многопарадигмальным языком, он позволяет выражать алгоритмы интуитивно или близко к машине, или что-либо еще между ними. Я хотел бы воспользоваться возможностью, чтобы обрисовать другой подход, который может быть более интуитивным для некоторых, но дает более низкие результаты метрики производительности.
   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