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)?

Is this not an obvious MSVC bug in some fashion? Also works fine if p is just declared as an int. — Barry
– Barry, Commented Jul 26, 2024 at 18:35
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) — Erel
– Erel, Commented Jul 26, 2024 at 18:36
Apparently using auto p is also ok for MSVC, so... I agree, this is a bug in MSVC — Erel
– Erel, Commented Jul 26, 2024 at 18:39
Compilers have "steps" limit for constexpr, it is possible you reach it for MSVC. (constexpr doesn't requires memoization). — Jarod42
– Jarod42, Commented Jul 26, 2024 at 18:44
@Jarod42 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 — Barry
– Barry, Commented Jul 26, 2024 at 19:36

Richard · Accepted Answer · 2024-07-27 15:29:40Z

5

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

edited Jul 27, 2024 at 15:29

answered Jul 27, 2024 at 15:22

Richard

47k7 gold badges40 silver badges94 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related