为什么这个斐波那契的实现速度非常快？
Why this implementation of Fibonacci is extremely fast?
这种斐波那契的实现很容易理解但是很慢：
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Fibonacci 的以下实现很难理解，但速度非常快。它在我的笔记本电脑上立即计算出第 100,000 个斐波那契数。
fib = fastFib 1 1
fastFib _ _ 0 = 0
fastFib _ _ 1 = 1
fastFib _ _ 2 = 1
fastFib a b 3 = a + b
fastFib a b c = fastFib (a + b) a (c - 1)
后一种实现有什么神奇之处，它是如何工作的？
神奇的是递归公式所描述的计算过程的反映、具体化、解释：
fib 0 = 0 -- NB!
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
-- n1 n2
= let {n1 = fib (n-1) ; n2 = fib (n-2)}
in n1 + n2
= let {n1 = fib (n-2) + fib (n-3) ; n2 = fib (n-2)}
-- n2 n3
in n1 + n2
= let {n1 = n2+n3 ; n2 = fib (n-2) ; n3 = fib (n-3)}
in n1 + n2
= let {n1 = n2+n3 ; n2 = fib (n-3) + fib (n-4) ; n3 = fib (n-3)}
-- n3 n4
in n1 + n2
= let {n1 = n2+n3 ; n2 = n3+n4 ; n3 = fib (n-3) ; n4 = fib (n-4)}
in n1 + n2
= let {n1 = n2+n3 ; n2 = n3+n4 ; n3 = n4+n5 ; n4 = fib (n-4) ; n5 = fib (n-5)}
in n1 + n2
= .......
，查看最终案例，然后 翻转时间箭头 （或者只是从右到左阅读），然后编码 显式 let 内部隐式发生的事情，作为递归模拟 "call stack" 操作的一部分。
最重要的是，用等号代替等号，也就是引用透明性——使用 n2 代替 fib (n-2) 的 each 等
为什么第一次执行很慢？
嗯，它很慢，因为每次调用 fib 可能会导致最多两次（平均更接近 1.6）次调用 fib，因此要计算 fib 5，您调用 fib 4和fib 3分别调用了fib 3和fib 2，以及fib 2和fib 1，所以我们可以看到每次调用fib (n+1) 的结果是调用 fib n.
的两倍
我们可能会观察到的一件事是，我们会多次计算同一件事，例如上面我们计算了 fib 3 两次。如果你必须锻炼，那可能需要很长时间。 fib 100两次。
如何更快地进行小便？
我认为从这里开始比直接跳到 fastFib 更好。如果我让你手工计算第十个斐波纳契数，我希望你不会通过应用该算法计算第三个数。你可能会记得你到目前为止所拥有的。在 Haskell 中确实可以做到这一点。只需编写一个程序来生成斐波那契数列（懒惰地）并对其进行索引：
mediumFib = (\n -> seq !! n) where
seq = 0:1:[mediumFib (i-1) + mediumFib (i-2)| i <- [2..]]
这要快得多，但它很糟糕，因为它使用大量内存来存储斐波那契数列，而且查找列表的第 n 个元素很慢，因为您必须遵循大量指针.
从头开始计算单个斐波那契数（即尚未计算任何数）需要二次方时间。
您可以手算第十个斐波那契数列的另一种方法是写下斐波那契数列，直到您到达第十个元素。然后你永远不需要回顾过去或记住你以前计算过的所有东西，你只需要看看前面的两个元素。可以想象一种命令式算法可以做到这一点
fib(n):
if (n<2) return n
preprevious = 0
previous = 1
i = 2
while true:
current = preprevious + previous
if (i = n) return current
preprevious, previous = previous, current
这只是单步执行递推关系：
f_n = f_(n-2) + f_(n-1)
其实我们也可以写成Haskell:
fastFib n | n < 2 = n
| otherwise = go 0 1 2 where
go pp p i | i = n = pp + p
| otherwise = go p (pp + p) (i + 1)
现在这个速度非常快，我们可以将其转换为您也拥有的功能。以下是步骤：
- 交换
pp（上一个）和 p（上一个）的参数顺序
- 不要向上数
i，而是从 n 开始向下数。
- 将
go 提取到顶级函数中，因为它不再依赖于 n。
这个算法每一步只需要做一次求和，所以是线性时间，速度非常快。计算 fib (n+1) 只比计算 fib n 多一个常数。将此与上面的工作量进行比较，大约是工作量的 1.6 倍。
有没有更快的fib？
当然有。事实证明，有一种巧妙的方式来表达斐波那契数列。我们认为转换 a,b -> a+b,a 是转换族 T_pq:
的特例
T_pq : a -> bq + aq + ap
b -> bp + aq
具体是p = 0和q = 1的特例。我们现在可以做一些代数来计算是否有一种简单的方法来表达应用 T_pq 两次：
T_pq T_pq :
a -> (bp + aq)q + (bq + aq + ap)(q + p)
b -> (bp + aq)p + (bq + aq + ap)q
=
a -> (b + a)(q^2 + 2pq) + a(q^2 + p^2)
b -> b(q^2 + p^2) + a(q^2 + 2pq)
= T_(q^2 + p^2),(q^2 + 2pq)
所以现在让我们写一个简单的函数来计算T_pq^n (a,b)和fib n
tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
| otherwise = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)
fib 0 = 0
fib 1 = 1
fib n = fst $ tPow 0 1 1 0 (n-1)
现在我们可以使用我们的关系来使 tPow 更快：
tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
| odd n = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)
| even n = tPow (q*q + p*p) (q*q + 2*p*q) a b (n `div` 2)
为什么这样更快？好吧，它更快，因为计算 fib (2*n) 只比计算 fib n 多了一个小常量，而之前是两倍，之前是四倍，之前是工作量的平方。实际上，步数类似于 n 的二进制位数加上 n 的二进制表示中 1 的位数。计算 fib 1024 只需要大约 10 步，而以前的算法大约需要 1000 步。计算第 10 亿个斐波那契数只需要 30 步，比十亿少很多。
只是想说明一下，尾递归与使第二个程序变快的原因无关。下面，我重写了您的第一个程序以使用适当的尾调用，并将执行时间与第二个程序进行比较。我还重写了那个，因为它可以简化很多 -
fib1 n = slow n id
where
slow 0 k = k 0
slow 1 k = k 1
slow n k = slow (n - 1) (\a ->
slow (n - 2) (\b ->
k (a + b)))
fib2 n = fast n 0 1
where
fast 0 a _ = a
fast n a b = fast (n - 1) b (a + b)
对 n = 10 这样的小数字的影响可以忽略不计 -
fib1 10
-- 55
-- (0.01 secs, 138,264 bytes)
fib2 10
-- 55
-- (0.01 secs, 71,440 bytes)
但即使在 n = 20 左右，我们也注意到 fib1 性能大幅下降 -
fib1 20
-- 6765
-- (0.70 secs, 8,787,320 bytes)
fib2 20
-- 6765
-- (0.01 secs, 76,192 bytes)
在n = 30，影响是可笑的。两个程序仍然得到相同的结果，这很好，但是 fib1 花费了 30 多秒。 fib2 仍然只需要几分之一秒 -
fib1 30
-- 832040
-- (32.91 secs, 1,072,371,488 bytes) LOL so bad
fib2 30
-- 832040 (0.09 secs, 80,944 bytes)
这是因为第一个程序 fib1 进行了 两次 次递归调用。此函数的过程使用指数时间和 space 作为 n 增长。在 n = 30，慢程序将进行 1,073,741,824（230）次递归调用。快程序只会重复30次
在 n = 1000，我们 运行 遇到了 fib1 的严重问题。根据fib1 30的性能，我们估计需要1.041082353242204e286年才能完成21000次递归调用。同时，fib2 1000 毫不费力地处理 1000 次递归 -
fib2 1000
-- 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
-- (0.13 secs, 661,016 bytes)
添加 k 参数后，您的第一个程序的原始重写可能很难理解。使用 Cont 可以让我们看到 Haskell 熟悉的 do 表示法中清晰的步骤顺序 -
import Control.Monad.Cont
fib1 n = runCont (slow n) id
where
slow 0 = return 0
slow 1 = return 1
slow n = do
a <- slow (n - 1)
b <- slow (n - 2)
return (a + b)
隐藏输入数字被用作计数器的事实只是混淆视听。我希望如果你看到这样的东西，你会明白为什么：
fib2 n = fastFib2 0 1 0 n
fastFib2 current previous count 0 = 0
fastFib2 current previous count 1 = 1
fastFib2 current previous count n
| count == n = current
| otherwise =
fastFib2 (current + previous) current (count + 1) n
在上面的代码中，我们明确了计数器：当它等于我们的输入 n 时，我们 return 我们的累加器 current；否则，我们将跟踪当前和先前数字（“two preceding ones”）的 "forward" 递归，所有这些都是构建斐波那契数列所需的。
您分享的代码做同样的事情。 (c - 1) 使它看起来更像一个更传统的 "backwards" 循环，当它实际上在第一次调用时从累加器开始，然后添加到它。
这种斐波那契的实现很容易理解但是很慢：
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Fibonacci 的以下实现很难理解，但速度非常快。它在我的笔记本电脑上立即计算出第 100,000 个斐波那契数。
fib = fastFib 1 1
fastFib _ _ 0 = 0
fastFib _ _ 1 = 1
fastFib _ _ 2 = 1
fastFib a b 3 = a + b
fastFib a b c = fastFib (a + b) a (c - 1)
后一种实现有什么神奇之处，它是如何工作的？
神奇的是递归公式所描述的计算过程的反映、具体化、解释：
fib 0 = 0 -- NB!
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
-- n1 n2
= let {n1 = fib (n-1) ; n2 = fib (n-2)}
in n1 + n2
= let {n1 = fib (n-2) + fib (n-3) ; n2 = fib (n-2)}
-- n2 n3
in n1 + n2
= let {n1 = n2+n3 ; n2 = fib (n-2) ; n3 = fib (n-3)}
in n1 + n2
= let {n1 = n2+n3 ; n2 = fib (n-3) + fib (n-4) ; n3 = fib (n-3)}
-- n3 n4
in n1 + n2
= let {n1 = n2+n3 ; n2 = n3+n4 ; n3 = fib (n-3) ; n4 = fib (n-4)}
in n1 + n2
= let {n1 = n2+n3 ; n2 = n3+n4 ; n3 = n4+n5 ; n4 = fib (n-4) ; n5 = fib (n-5)}
in n1 + n2
= .......
，查看最终案例，然后 翻转时间箭头 （或者只是从右到左阅读），然后编码 显式 let 内部隐式发生的事情，作为递归模拟 "call stack" 操作的一部分。
最重要的是，用等号代替等号，也就是引用透明性——使用 n2 代替 fib (n-2) 的 each 等
为什么第一次执行很慢？
嗯，它很慢，因为每次调用 fib 可能会导致最多两次（平均更接近 1.6）次调用 fib，因此要计算 fib 5，您调用 fib 4和fib 3分别调用了fib 3和fib 2，以及fib 2和fib 1，所以我们可以看到每次调用fib (n+1) 的结果是调用 fib n.
我们可能会观察到的一件事是，我们会多次计算同一件事，例如上面我们计算了 fib 3 两次。如果你必须锻炼，那可能需要很长时间。 fib 100两次。
如何更快地进行小便？
我认为从这里开始比直接跳到 fastFib 更好。如果我让你手工计算第十个斐波纳契数，我希望你不会通过应用该算法计算第三个数。你可能会记得你到目前为止所拥有的。在 Haskell 中确实可以做到这一点。只需编写一个程序来生成斐波那契数列（懒惰地）并对其进行索引：
mediumFib = (\n -> seq !! n) where
seq = 0:1:[mediumFib (i-1) + mediumFib (i-2)| i <- [2..]]
这要快得多，但它很糟糕，因为它使用大量内存来存储斐波那契数列，而且查找列表的第 n 个元素很慢，因为您必须遵循大量指针.
从头开始计算单个斐波那契数（即尚未计算任何数）需要二次方时间。
您可以手算第十个斐波那契数列的另一种方法是写下斐波那契数列，直到您到达第十个元素。然后你永远不需要回顾过去或记住你以前计算过的所有东西，你只需要看看前面的两个元素。可以想象一种命令式算法可以做到这一点
fib(n):
if (n<2) return n
preprevious = 0
previous = 1
i = 2
while true:
current = preprevious + previous
if (i = n) return current
preprevious, previous = previous, current
这只是单步执行递推关系：
f_n = f_(n-2) + f_(n-1)
其实我们也可以写成Haskell:
fastFib n | n < 2 = n
| otherwise = go 0 1 2 where
go pp p i | i = n = pp + p
| otherwise = go p (pp + p) (i + 1)
现在这个速度非常快，我们可以将其转换为您也拥有的功能。以下是步骤：
- 交换
pp（上一个）和p（上一个）的参数顺序 - 不要向上数
i，而是从n开始向下数。 - 将
go提取到顶级函数中，因为它不再依赖于n。
这个算法每一步只需要做一次求和，所以是线性时间，速度非常快。计算 fib (n+1) 只比计算 fib n 多一个常数。将此与上面的工作量进行比较，大约是工作量的 1.6 倍。
有没有更快的fib？
当然有。事实证明，有一种巧妙的方式来表达斐波那契数列。我们认为转换 a,b -> a+b,a 是转换族 T_pq:
T_pq : a -> bq + aq + ap
b -> bp + aq
具体是p = 0和q = 1的特例。我们现在可以做一些代数来计算是否有一种简单的方法来表达应用 T_pq 两次：
T_pq T_pq :
a -> (bp + aq)q + (bq + aq + ap)(q + p)
b -> (bp + aq)p + (bq + aq + ap)q
=
a -> (b + a)(q^2 + 2pq) + a(q^2 + p^2)
b -> b(q^2 + p^2) + a(q^2 + 2pq)
= T_(q^2 + p^2),(q^2 + 2pq)
所以现在让我们写一个简单的函数来计算T_pq^n (a,b)和fib n
tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
| otherwise = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)
fib 0 = 0
fib 1 = 1
fib n = fst $ tPow 0 1 1 0 (n-1)
现在我们可以使用我们的关系来使 tPow 更快：
tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
| odd n = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)
| even n = tPow (q*q + p*p) (q*q + 2*p*q) a b (n `div` 2)
为什么这样更快？好吧，它更快，因为计算 fib (2*n) 只比计算 fib n 多了一个小常量，而之前是两倍，之前是四倍，之前是工作量的平方。实际上，步数类似于 n 的二进制位数加上 n 的二进制表示中 1 的位数。计算 fib 1024 只需要大约 10 步，而以前的算法大约需要 1000 步。计算第 10 亿个斐波那契数只需要 30 步，比十亿少很多。
只是想说明一下，尾递归与使第二个程序变快的原因无关。下面，我重写了您的第一个程序以使用适当的尾调用，并将执行时间与第二个程序进行比较。我还重写了那个，因为它可以简化很多 -
fib1 n = slow n id
where
slow 0 k = k 0
slow 1 k = k 1
slow n k = slow (n - 1) (\a ->
slow (n - 2) (\b ->
k (a + b)))
fib2 n = fast n 0 1
where
fast 0 a _ = a
fast n a b = fast (n - 1) b (a + b)
对 n = 10 这样的小数字的影响可以忽略不计 -
fib1 10
-- 55
-- (0.01 secs, 138,264 bytes)
fib2 10
-- 55
-- (0.01 secs, 71,440 bytes)
但即使在 n = 20 左右，我们也注意到 fib1 性能大幅下降 -
fib1 20
-- 6765
-- (0.70 secs, 8,787,320 bytes)
fib2 20
-- 6765
-- (0.01 secs, 76,192 bytes)
在n = 30，影响是可笑的。两个程序仍然得到相同的结果，这很好，但是 fib1 花费了 30 多秒。 fib2 仍然只需要几分之一秒 -
fib1 30
-- 832040
-- (32.91 secs, 1,072,371,488 bytes) LOL so bad
fib2 30
-- 832040 (0.09 secs, 80,944 bytes)
这是因为第一个程序 fib1 进行了 两次 次递归调用。此函数的过程使用指数时间和 space 作为 n 增长。在 n = 30，慢程序将进行 1,073,741,824（230）次递归调用。快程序只会重复30次
在 n = 1000，我们 运行 遇到了 fib1 的严重问题。根据fib1 30的性能，我们估计需要1.041082353242204e286年才能完成21000次递归调用。同时，fib2 1000 毫不费力地处理 1000 次递归 -
fib2 1000
-- 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
-- (0.13 secs, 661,016 bytes)
添加 k 参数后，您的第一个程序的原始重写可能很难理解。使用 Cont 可以让我们看到 Haskell 熟悉的 do 表示法中清晰的步骤顺序 -
import Control.Monad.Cont
fib1 n = runCont (slow n) id
where
slow 0 = return 0
slow 1 = return 1
slow n = do
a <- slow (n - 1)
b <- slow (n - 2)
return (a + b)
隐藏输入数字被用作计数器的事实只是混淆视听。我希望如果你看到这样的东西，你会明白为什么：
fib2 n = fastFib2 0 1 0 n
fastFib2 current previous count 0 = 0
fastFib2 current previous count 1 = 1
fastFib2 current previous count n
| count == n = current
| otherwise =
fastFib2 (current + previous) current (count + 1) n
在上面的代码中，我们明确了计数器：当它等于我们的输入 n 时，我们 return 我们的累加器 current；否则，我们将跟踪当前和先前数字（“two preceding ones”）的 "forward" 递归，所有这些都是构建斐波那契数列所需的。
您分享的代码做同样的事情。 (c - 1) 使它看起来更像一个更传统的 "backwards" 循环，当它实际上在第一次调用时从累加器开始，然后添加到它。