Euler项目#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连Fibonacci数(提示:这是涉及一个相对简单的公式,一个 Fibonacci数),找到最大的k,这样F(3*k) <= limit,用公式和算法计算计算总和F(n)中O(log n)例如这里的步骤.