编译时怎么能比运行时（指数级）快呢？

Question

下面的代码通过指数慢的算法计算斐波那契数：

#include <cstdlib>
#include <iostream>

#define DEBUG(var) { std::cout << #var << ": " << (var) << std::endl; }

constexpr auto fib(const size_t n) -> long long
{
    return n < 2 ? 1: fib(n - 1) + fib(n - 2);
}

int main(int argc, char *argv[])
{
    const long long fib91 = fib(91);

    DEBUG( fib91 );
    DEBUG( fib(45) );

    return EXIT_SUCCESS;
}

我在运行时计算第45个斐波那契数，在编译时计算第91个。

有趣的事实是，GCC4.9编译代码并在几分之一秒内计算出fib91，但吐出fib(45)需要一段时间。

以上是否意味着GCC会生成fib函数的两个编译版本，其中一个是快的，另一个是指数级慢的？

问题不是编译器如何优化fib(91)计算（是的！它确实使用了某种记忆），而是如果它知道如何优化fib函数，为什么它不对fib(45)做同样的操作呢？并且，fib函数有两个单独的编译吗？一个慢一个快？

Answer 1

GCC可能正在记忆constexpr函数（启用fib(n))的JADEN（n）计算）。编译器这样做是安全的，因为constexpr函数是纯函数的。

将(n)“编译器算法”（使用memoization）与（？ⁿ)运行时算法（其中？是黄金比例）进行比较，突然之间，编译器的速度快得多就变得非常有意义了。

从cppreference上的constexpr页面（着重号为后加）：

constexpr auto compute_fib(const size_t n) -> long long
{
    return n < 2 ? n : compute_fib(n - 1) + compute_fib(n - 2);
}

template <std::size_t N>
struct fib
{
    static_assert(N >= 0, "N must be nonnegative.");
    static const long long value = compute_fib(N);
};

在代码的其余部分中，您可以访问fib<45>::value或fib<91>::value，并保证在编译时对它们进行计算。