如何将此运行时效率函数转换为constexpr？

Question

我正在使用C++ constexpr在编译时评估此代码可以正确评估的计算的Fibonacci序列的最大项.为此,我使用以下代码:

constexpr unsigned long long fibo(unsigned n) {
    return (n < 2) ? 1 : fibo(n-1)+fibo(n-2);
}

constexpr unsigned max_fibo(unsigned n) {
    return (fibo(n+1) >= fibo(n)) ? max_fibo(n+1) : n;
}

const unsigned MAX_FIBO_TERM = max_fibo(0);

这很好,并快速构造MAX_FIBO_TERM(我的机器上的92)正确的值.但是,使用该fibo函数在运行时实际计算项是非常慢的(仅计算前48个项需要大约90秒).

我可以使用替代函数来计算更快的术语:

unsigned long long fiboiter(unsigned n, unsigned long long &prev, 
                            unsigned long long &prevprev) {
    return prev = (n < 2) ? prevprev = 1 : 
        (std::swap(prev, prevprev), prev + prevprev);
}

但是,我似乎无法将其变为有效的constexpr功能.(这就是为什么它以那种奇怪的方式写的.)当我运行这个版本时,我的机器需要0.005秒.

当我用g++ -O2 -std=c++11 fibo.cpp -o fibo它编译它只需要0.302秒.

我的问题是:如何在运行时和编译时使用相同的高效函数？

我在64位Linux机器上使用g ++ 4.8.3,但我想要的是一个跨平台的通用答案,而不仅仅是一个特定于这个编译器和机器的答案.不,在这种情况下,C++ 14还不是一个选择.

此外,我的问题与此问题类似,但不一样,因为我在询问如何在编译时使用相同的运行时效率代码而不是为什么或如何使编译时代码高效.

这是完整的计划.

fibo.cpp

#include <iomanip>
#include <iostream>
#include <locale>

constexpr unsigned long long fibo(unsigned n) {
    return (n < 2) ? 1 : fibo(n-1)+fibo(n-2);
}   
unsigned long long fiboiter(unsigned n, unsigned long long &prev, 
                            unsigned long long &prevprev) {
    return prev = (n < 2) ? prevprev = 1 : 
        (std::swap(prev, prevprev), prev + prevprev);
}    
constexpr unsigned max_fibo(unsigned n) {
    return (fibo(n+1) >= fibo(n)) ? max_fibo(n+1) : n;
}    
const unsigned MAX_FIBO_TERM = max_fibo(0);

int main(int argc, char **)
{
    // format numeric output according to user's preferred locale
    std::cout.imbue(std::locale{""});
    unsigned long long prev, prevprev;

    if (argc > 1) {
        for (unsigned i = 0; i <= MAX_FIBO_TERM; ++i) 
            std::cout << "fib(" << std::setw(2) << i << ") = " 
                      << std::setw(26) << fiboiter(i, prev, prevprev) << '\n';
    } else {
        for (unsigned i = 0; i <= MAX_FIBO_TERM; ++i) 
            std::cout << "fib(" << std::setw(2) << i << ") = " 
                      << std::setw(26) << fibo(i) << '\n';
    }
}

样本输出

fib( 0) =                          1
fib( 1) =                          1
fib( 2) =                          2
fib( 3) =                          3
fib( 4) =                          5
fib( 5) =                          8
 ...
fib(89) =  2,880,067,194,370,816,120
fib(90) =  4,660,046,610,375,530,309
fib(91) =  7,540,113,804,746,346,429
fib(92) = 12,200,160,415,121,876,738

Answer 1

好的编译器可以很好地优化尾递归,尝试尾递归constexpr实现:

constexpr unsigned long long fibo(unsigned n,
                                  unsigned long long prev = 1,
                                  unsigned long long prevprev = 0) {
    return n == 0 ? prev : fibo(n - 1, prev + prevprev, prev);
}   

根据Coliru的铿锵声,两个版本constexpr和非constexpr版本都需要5-6毫秒才能完成(这可能是I/O占主导地位).