Тип переполнения в проекте euler # 5

Question

Я пытаюсь решить проект euler # 5:

2520 - это наименьшее число, которое можно без деления разделить на каждое из чисел от 1 до 10.

Какое наименьшее положительное число, которое равномерно делится на все числа от 1 до 20?

Вот мой код:

open System

let rec gcd a b =
    match b with
        | x when x = 0 -> a
        | _ -> gcd b (a % b)

let lcm a b = (a * b) / (gcd a b)        
let result = Seq.fold lcm 1 [1..20]

[<EntryPoint>]
let main(args : string[]) =
    printfn "result = %d" result 
    0

Отлично работает с числами [1..19], но я получаю неправильный результат с числами [1..20].Я пытался выяснить причину ошибки и обнаружил, что:

$ Seq.fold lcm 1 [1..19]
232792560 // right
$ lcm 232792560 20
18044195 // wrong

Это похоже на переполнение типа.Как я могу исправить ошибку?

Answer 1

Используйте BigInt, целочисленный тип, который не будет переполнен. Если вы замените 0 на 0I (суффикс I используется для литералов BigInt) в gcd, то и gcd, и lcm будут выведены для работы с BigInt с вместо int s.

Answer 2

На других языках возможно работать с 4-байтовым целым числом до тех пор, пока оно не переполнится, тогда во время выполнения обновляется ваше целое число и происходит, как запланировано.

Интересно, могли бы мы сделать то же самое вF #, для оптимизации производительности.

Answer 3

Другое решение состоит в том, чтобы слегка переопределить функцию lcm

let lcm a b = let m = b / (gcd a b) in a * m;; 

Поскольку вы умножаете на несколько меньшие числа, оно не переполняется.Задачи Эйлера также касаются математики: p

Answer 4

Вы можете использовать LanguagePrimitives.GenericZero вместо литерала 0. Таким образом, функция gcd и, следовательно, функция lcm являются общими и будут работать с любым числовым типом. Вот решение с использованием int64:

module Problem5 =
    let rec greatestCommonDivisor a b  = // Euclidean algorithm
        if b = LanguagePrimitives.GenericZero then  a 
        else greatestCommonDivisor b (a % b)
    let leastCommonMultiple a b  = (a * b) / (greatestCommonDivisor a b)
    // Take the least common multiple of all numbers from 1 to 20.
    let solution = [1L..20L] |> List.fold leastCommonMultiple 1L