Inaccurate compile-time computation of Fibonacci sequence in a recursive lambda

Question

Below is a recursive lambda expression that can compute the values of Fibonacci sequence both in runtime and during constant evaluation:

auto fib = [](this auto && f, auto && p) {
    if ( p < 3 ) return 1;
    decltype(+p) v{};
    v = p - 2;
    return f(v+1) + f(v);
};

// ok everywhere
static_assert( fib(1) == 1 );
static_assert( fib(2) == 1 );
static_assert( fib(3) == 2 );
static_assert( fib(4) == 3 );
static_assert( fib(5) == 5 );
static_assert( fib(6) == 8 );
static_assert( fib(7) == 13 );
static_assert( 20 <= fib(8) && fib(8) <= 21 );
// fails in MSVC
static_assert( fib(8) == 21 );

As far as I can see it works fine in GCC and Clang, but in Visual Studio it is so only for the first 7 elements, and fib(8) is computed inaccurately resulting in a failure of static assertion. Online demo: https://gcc.godbolt.org/z/dMM6f16do

If the program is correct, why does it perform well for small numbers and does not work for larger ones (e.g. integer overflow, too many recursive calls)?

Dungaree

Is this not an obvious MSVC bug in some fashion? Also works fine if p is just declared as an int. – Unreal

Surprisingly (?), MSVC is able to compute fib(8) and agrees it's 21 as can be seen by modifying your example to return fib(8) (gcc.godbolt.org/z/6h7YThT7M) – Hague

Apparently using auto p is also ok for MSVC, so... I agree, this is a bug in MSVC – Hague

Compilers have "steps" limit for constexpr, it is possible you reach it for MSVC. (constexpr doesn't requires memoization). – Cockleboat

@Cockleboat I don't think that's the issue. MSVC accepts constexpr auto f8 = fib(8) – Hague

@Cockleboat It doesn't fail to evaluate, it just gives the wrong answer. MSVC's static_assert is particularly poor in that it gives literally no information whatsoever... but the problem is taht it thinks fib(8) is 20, not that it cannot evaluate fib(8): gcc.godbolt.org/z/zqTn5Yv4K – Unreal

Hmm, I've ran into odd MSVC bugs with member function non-tail recursion before, somewhere in VS2010\2012 (in some bad\convoluted code written by interns, so I don't have memory how to reproduce). Could be similar issue. – Hijacker

It seems to work if you get rid of (the pointless) v and just return f(p-1) + f(p-2); in the natural way. (Code generation bugs are more common with awkward or unusual code.) – Chester

This failure: godbolt.org/z/Pz6PKq3rT seems to hint the problem is with passing the stack variable by reference. Changing auto&&p -> auto p or f(v)->f(+v) also makes it work. So maybe a bug with some constexpr tail call optimization? – Hole

Answer 1

This is definitely a msvc bug(non-conformant behavior). Note that msvc prints 21 when we print fib(8) directly using std::cout:

int main()
{
    std::cout << fib(8) << "\n"; //msvc prints 21
    constexpr int i = fib(8);
    std::cout << i;              //msvc prints 20
}

Demo

Here is the submitted bug report:

MSVC prints different result based on call to constepxr function is used in constexpr context or not

Tantalic