Type overflow in project euler #5
I am trying to solve the project euler #5:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbe开发者_运维百科rs from 1 to 20?
Here is my code:
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
It works fine with numbers [1..19], but I get the wrong result with numbers [1..20]. I was trying to find out the reason of error and find that:
$ Seq.fold lcm 1 [1..19]
232792560 // right
$ lcm 232792560 20
18044195 // wrong
It looks like the type overflow. How can I fix the error?
Use BigInt
, an integer type which won't overflow. If you replace 0
with 0I
(the I
suffix is used for BigInt
literals) in gcd
, then both gcd
and lcm
will be infered to work with BigInt
s instead of int
s.
The other solution is to redefine slightly the lcm function
let lcm a b = let m = b / (gcd a b) in a * m;;
Since you multiply by slightly smaller numbers, it won't overflow. Euler problems are also about mathematics :p
In other languages, it's possible to work with 4-byte integer until it overflows, then the run-time upgrades your integer, and proceeds as planned.
I wonder if we could do the same thing in F#, to optimize performance.
You could use LanguagePrimitives.GenericZero instead of the literal 0. This way the gcd function and thus the lcm function are generic and will work with any numeric type. Here a solution using 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
精彩评论