Why is initialization of variable with constexpr evaluated at runtime instead of at compile time

A short compilation time is not proof that the calls weren't evaluated at compile time. You can look at the compiled assembly to see that it was in fact evaluated at compile time using constexpr in my test here: https://godbolt.org/z/vbWaxe

In my tests with a newer compiler, const wasn't measurably slower than constexpr. It could be a quality of implementation issue with your version of the compiler.

The secret for the fast compile time evaluation is that there are only very very few Fibonacci numbers that would fit into the nowadays maximum data type unsigned long long.

The basic message for Fibonacci number calculation is: Any calculation at runtime is not necessary at all! Everything can and should be done at compile time. And then, a simple lookup mechanism can be used. That will always be the most efficient and fastest solution.

So, with Binet's formula, we can calculate that there are only very few Fibonacci numbers that will fit in a C++ unsigned long long data type, which has usually 64 bit now in 2021 and is the "biggest" available data type. Roundabout 93. That is nowadays a really low number.

With modern C++ 17 (and above) features, we can easily create a std::array of all Fibonacci numbers for a 64bit data type at compile time. Because there are, as mentioned above, only 93 numbers.

So, we will spend only 93*8= 744 BYTE of none-runtime memory for our lookup array. That is really negligible. And, the compiler can get those values fast.

After the compile time calculation, we can easily get the Fibonacci number n by writing FIB[n]. For detailed explanation, please see below.

And, if we want to know, if a number is Fibonacci, then we use std::binary_search for finding the value. So, this function will be for example:

bool isFib(const unsigned long long numberToBeChecked) {
    return std::binary_search(FIB.begin(), FIB.end(), numberToBeChecked);
}

FIB (of course any other name possible) is a compile time, constexpr std::array. So, how to build that array?

We will first define the default approach for calculation a Fibonacci number as a constexpr function (non-recursive):

// 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;
}

With that, Fibonacci numbers can easily be calculated at compile time as constexpr values. Then, we fill a std::array with all Fibonacci numbers. We use also a constexpr and make it a template with a variadic parameter pack.

We use std::integer_sequence to create a Fibonacci number for indices 0,1,2,3,4,5, ....

That is straigtforward and not complicated:

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

This function will be fed with an integer sequence 0,1,2,3,4,... and return a std::array<unsigned long long, ...> with the corresponding Fibonacci numbers.

We know that we can store maximum 93 values. And therefore we make a next function, that will call the above with the integer sequence 1,2,3,4,...,92,93, like so:

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

And now, finally,

constexpr auto FIB = generateArray();

will give us a compile-time std::array<unsigned long long, 93> with the name FIB containing all Fibonacci numbers. And if we need the i'th Fibonacci number, then we can simply write FIB[i]. There will be no calculation at runtime.

The whole example program will look like this:

#include <iostream>
#include <array>
#include <utility>
#include <algorithm>
#include <iomanip>
// ----------------------------------------------------------------------
// 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) 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;
}
// We will automatically build an array of Fibonacci numbers at compile 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 an 64bit unsigned value (Binet's 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();

// All the above was compile time
// ----------------------------------------------------------------------


// Check, if a number belongs to the Fibonacci series
bool isFib(const unsigned long long numberToBeChecked) {
    return std::binary_search(FIB.begin(), FIB.end(), numberToBeChecked);
}

// Test
int main() {

    const unsigned long long testValue{ 498454011879264ull };

    std::cout << std::boolalpha << "Does '" <<testValue << "' belong to Fibonacci series?  --> " << isFib(testValue) << "\n\n";

    for (size_t i{}; i < 10u; ++i)
        std::cout << i << '\t' << FIB[i] << '\n';

    return 0;
}

Developed and tested with Microsoft Visual Studio Community 2019, Version 16.8.2

Additionally tested with gcc 10.2 and clang 11.0.1

Language: C++ 17