项目欧拉＃类型溢出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

它看起来像类型的溢出。我该如何解决这个错误？

来源

2011-06-24 demas

另一个解决办法是由略小数乘法重新定义略有LCM功能

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

既然你，它不会溢出。欧拉问题也与数学有关：p

来源

2011-06-24 12:47:26

使用BigInt，这是一个不会溢出的整数类型。如果您要更换0与0I在gcd（该I后缀用于BigInt文字），那么这两个gcd和lcm将infered与BigInt！而非int s到工作。

来源

2011-06-24 12:36:19

而不是步骤1，你也可以用'0I'代替'0'。 –

@Ramon Snir - 实际上，我将修改我的答案以表明相反，因为无论如何您都无法拥有递归内联函数。 –

在其他语言中，可以使用4字节整数直到它溢出，然后运行时升级整数，然后按计划进行。

我不知道我们是否可以在F＃中做同样的事情来优化性能。

来源

2011-06-24 14:33:36 GregC

为了好玩，试着计算3^N，然后打印这些值。在Ruby中。 – GregC

你可以用任何语言做同样的事情，但表现很糟糕。整数溢出在实践中非常罕见，因此不值得牺牲所有整数算术的性能特征。 –

您可以使用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

来源

2014-02-28 21:35:27

项目欧拉＃类型溢出5

回答

相关问题