haskell - 欧拉计划 #2 大极限

Question

我有 Project Euler Problem 2 的 Haskell 解决方案这适用于四百万的限制，以及高达 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)

Answer 1

问题是您要对(偶数)斐波那契数求和。这意味着你必须计算所有这些。但是

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 .