我有一个 Haskell 解决方案 Project Euler Problem 2对于 400 万的限制以及高达 10^100000 的限制，它工作得很好，在我的机器上只需要几秒钟。
但是对于更大的事情，例如10^1000000，计算不会及时返回(如果有的话)(已尝试将其保留几分钟)。这里的限制因素是什么？
evenFibonacciSum :: Integer -> Integer
evenFibonacciSum limit =
foldl' (\t (_,b) -> t + b) 0 . takeWhile ((<=limit) . snd) . iterate doIteration $ (1,2) where
doIteration (a, b) = (twoAB - a, twoAB + b) where
twoAB = 2*(a + b)
最佳答案
问题在于您正在对(偶数)斐波那契数求和。这意味着您必须计算所有这些。但是
F(n) ≈ φ^n / √5, with φ = (1 + √5)/2
所以你要添加很多大尺寸的数字，Θ(n) F(n) 的位。对于 10^1000000 的限制，您需要大约 800000×2 个大于 10^500000 的数字相加。一般来说，您需要Θ(n)数字相加Θ(n)位。
添加d的数字数字[以任何基数]是 O(d)手术。所以你的算法的指数是二次的。
为避免这种情况，请找到总和的封闭公式 S(k)第一个 k即使是斐波那契数(提示:这是一个相对简单的公式，涉及 一个 斐波那契数)，找到最大的 k这样F(3*k) <= limit ，并使用公式和算法计算总和来计算 F(n)在O(log n)步骤例如here .
关于haskell - 欧拉计划 #2 大极限，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13923675/