使用clang的固定深度限制(fconstexpr深度似乎不起作用)

Question

是否有任何方式来配置constexpr实例化深度？我运行的是-fconstexpr深度=4096(使用clang/XCode)。

但是仍然无法用错误编译此代码: Constexpr变量fib_1必须由常量表达式初始化。无论是否设置了选项fconstexpr深度=4096，代码都会失败。

这是一个带有clang的bug，还是期望这样的行为。注意:直到fib_cxpr(26)，27是当它开始失败时，它才能正常工作。

代码：

constexpr int fib_cxpr(int idx) {
    return idx == 0 ? 0 :
           idx == 1 ? 1 :
           fib_cxpr(idx-1) + fib_cxpr(idx-2); 
}

int main() {
    constexpr auto fib_1 = fib_cxpr(27);
    return 0; 
}

Answer 1

与“深度极限”无关，但与Fibonacci数的计算密切相关。

递归可能是错误的方法，而不是必需的。

有一个超快的解决方案，内存占用可能较低。

因此，我们可以使用编译时间预计算所有符合64位值的Fibonacci数。

Fibonacci级数的一个重要性质是它的值呈强指数增长。因此，整数数据类型中的所有现有构建都会很快溢出。

使用比内公式，您可以计算出第93位斐波那契数是最后一个不带符号的64位值。

在编译过程中计算93个值是一个非常简单的任务。

我们将首先将计算Fibonacci数的默认方法定义为constexpr函数：

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

这样，在编译时可以很容易地计算斐波纳契数。然后，我们用所有Fibonacci数填充一个std::array。我们还使用了一个constexpr，并使它成为一个带有可变参数包的模板。

我们使用std::integer_sequence为指数0,1,2,3,4,5，.

这是斜视的，并不复杂：

template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

此函数将用整数序列0、1、2、3、4、.并用相应的斐波那契数返回一个std::array<unsigned long long, ...>。

我们知道我们可以存储最多93个值。因此，我们做了一个下一个函数，它将调用上面的整数序列1,2,3,4，...,92,93，如下所示：

constexpr auto generateArray() noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

现在，终于，

constexpr auto FIB = generateArray();

将给我们一个包含所有斐波那契数字的名为FIB的编译时std::array<unsigned long long, 93>。如果我们需要I‘the数，那么我们可以简单地编写FIB[i]。运行时将不进行计算。

我不认为有更快的方法来计算n‘’th斐波那契数。

请参阅以下完整的课程：

#include <iostream>
#include <array>
#include <utility>
// ----------------------------------------------------------------------
// All the following will be done during compile time

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}
// We will automatically build an array of Fibonacci numberscompile time
// Generate a std::array with n elements 
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

// Max index for Fibonaccis that for in an 64bit unsigned value (Binets formula)
constexpr size_t MaxIndexFor64BitValue = 93;

// Generate the required number of elements
constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

// This is an constexpr array of all Fibonacci numbers
constexpr auto FIB = generateArray();
// ----------------------------------------------------------------------

// Test
int main() {

    // Print all possible Fibonacci numbers
    for (size_t i{}; i < MaxIndexFor64BitValue; ++i)

        std::cout << i << "\t--> " << FIB[i] << '\n';

    return 0;
}

用MicrosoftVisualStudioCommunity2019开发和测试，版本16.8.2。

另外用clang11.0和gcc10.2编译和测试

语言: C++17