Неточные вычисления последовательности Фибоначчи во время компиляции в рекурсивной лямбда-выражении
Ниже приведено рекурсивное лямбда-выражение, которое может вычислять значения последовательности Фибоначчи как во время выполнения, так и во время постоянной оценки:
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 );
Насколько я вижу, в GCC и Clang это работает нормально, но в Visual Studio это работает только для первых 7 элементов, а fib(8) вычисляется неточно, что приводит к сбою статического утверждения. Онлайн-демо: https://gcc.godbolt.org/z/dMM6f16do
Если программа корректна, почему она хорошо работает с небольшими числами и не работает с большими (например, переполнение целых чисел, слишком много рекурсивных вызовов)?
Удивительно (?), MSVC может вычислить fib(8) и соглашается, что это 21, как можно увидеть, изменив ваш пример на return fib(8) (gcc.godbolt.org/z/6h7YThT7M)
Судя по всему, использование auto p также подходит для MSVC, так что... Я согласен, это ошибка в MSVC.
У компиляторов есть ограничение на количество шагов для constexpr, возможно, вы достигнете его для MSVC. (constexpr не требует запоминания).
@Jarod42 Джарод42 Я не думаю, что это проблема. MSVC принимает constexpr auto f8 = fib(8)
@ Jarod42 Jarod42 Он не перестает оценивать, он просто дает неправильный ответ. MSVC static_assert особенно плох тем, что он не дает буквально никакой информации... но проблема в том, что он думает, что fib(8) есть 20, а не в том, что он не может оценить fib(8): gcc.godbolt.org/z/zqTn5Yv4K
Хм, я уже сталкивался со странными ошибками MSVC с нехвостовой рекурсией функций-членов, где-то в VS2010\2012 (в каком-то плохом\запутанном коде, написанном стажерами, поэтому у меня нет памяти, как воспроизвести). Может быть аналогичная проблема.
Кажется, это сработает, если избавиться от (бессмысленного) v и просто return f(p-1) + f(p-2); естественным путем. (Ошибки генерации кода чаще встречаются в случае неудобного или необычного кода.)
Этот сбой: godbolt.org/z/Pz6PKq3rT, кажется, намекает, что проблема заключается в передаче переменной стека по ссылке. Изменение auto&&p -> auto p или f(v)->f(+v) также заставляет это работать. Так может быть, ошибка в какой-то оптимизации хвостового вызова constexpr?
Ответы 1
Это определенно ошибка msvc (несоответствующее поведение). Обратите внимание, что msvc печатает21, когда мы печатаем fib(8) напрямую с помощью std::cout:
int main()
{
std::cout << fib(8) << "\n"; //msvc prints 21
constexpr int i = fib(8);
std::cout << i; //msvc prints 20
}
Вот отправленный отчет об ошибке:
Разве это не очевидная ошибка MSVC? Также отлично работает, если
pпросто объявлен какint.