Учитывая, что b всегда отличное от нуля, почему `b? -b: ++ b` works, но `-b` нет?

Ответ 1

TL; версия DR: Причина b? --b: ++b выводит результат, а --b терпит неудачу с SIGXCPU - это то, что ideone устанавливает ограничение на предоставленный код.. Одна версия оптимизируется лучше, и завершается за допустимое время. Другая версия дает тот же ответ, но вы не увидите этого с ideone, потому что он работает слишком медленно и прерывается по времени.

Что касается того, почему переполнение стека не происходит, я предполагаю, что в одном случае компилятор должен преобразовывать рекурсию в итерацию (это не хвостовой вызов, но он тривиально трансформируемый).

Результат преобразования будет выглядеть как http://ideone.com/AeBYI, который действительно дает правильный результат. При более высоких настройках оптимизации компилятор мог вычислять результаты во время компиляции и сохранять константы в полученном коде.

Ответ 2

Это не работает. Я не знаю, какой идеон курит, этот код переполнит стек.

ИЗМЕНИТЬ

Пробовал это на gcc 4.6.0 - segfault (из-за). Однако, если вы включите оптимизацию -O2, то действительно "это работает". В заключение: он работает случайно, в зависимости от того, что компилятор делает за кулисами.

g++ -g -Wall -o f f.cpp # stack overflow
g++ -O2 -g -Wall -o f f.cpp # "works"

Ответ 3

Результат из приведенного ниже кода должен дать очень сильный ключ;)

#include <iostream>

using namespace std;

int multiply(int a, int b)
{
  cout << "a = " << a << "\tb = " << b << std::endl;
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b );
}

int main() {
        cout << multiply(12, 7) << endl;
        cout << multiply(12, -7) << endl;
        cout << multiply(-12, -7) << endl;
        cout << multiply(-12, 7) << endl;
        return 0;
}

Мне кажется, что я получаю ответ, пройдя длинный путь.

Изменить: В ответ на комментарий из Nawaz ниже, первый метод работает из-за капризов двухзначной арифметики со знаком со знаком. Как я уже сказал, это проходит долгий путь. Он включен, как указывали другие, из-за некоторой оптимизации компилятора или другой. Вы можете увидеть это в коде ниже для ранее введенного тестового ввода:

int mul2(int a, int b)
{
    int rv = 0;
    while (b--) rv += a;
    return rv;
}

На самом деле это должно работать для любой пары целых чисел, но в некоторых случаях потребуется некоторое время (но я ожидаю, что вы не заинтересованы в эффективности в любом случае).

Второй случай не работает, потому что ваш условный b > 0 ? --b : ++b по существу преобразует b в abs(b). То есть, вы добавляете только 7 раз в тестовый пример, хотя b = -7. Если вы хотите, чтобы он вел себя так, как я думаю, вы хотели, чтобы он вел себя, вам нужно будет сделать что-то вроде:

int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else if (b < 0)
     return -a + multiply(-a, -b-1);
  else
     return a + multiply(a, --b);
}

Изменить 2: Попробуйте это вместо:

short multiply(short a, short b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b );
}

и

short multiply(short a, short b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, --b);
}

Оба эти компилируются, запускаются и возвращают один и тот же (правильный) результат с оптимизацией или без нее. Как указывали другие, причина разницы во времени выполнения, которую вы видите, может быть отнесена только к тому, как компилятор оптимизирует ваш код. Вам нужно будет проанализировать ассемблерный код этих двух методов, чтобы определить основную причину временных расхождений.

Ответ 4

В самом деле, это не имеет ничего общего с -b, но с вашим алгоритмом.

Если b < 0, что вы ожидаете? Вы будете бесконечно зацикливаться и заканчиваете переполнение стека.

Вот почему у вас есть правильный результат при первом умножении (12, 7), но тогда ваша программа выйдет из строя при вызове умножения (12, -7).

Ответ 5

Из-за того, как работают 2 номера дополнений, ваш код является "правильным" как для положительных, так и для отрицательных значений для b. Просто для отрицательных b любая рекурсивная версия нуждается в большом стеке для работы. Поэтому в любое время, когда компилятор выдает нерекурсивную версию, у вас есть рабочий код. Таким образом, это сводится к: какому правилу мой комплимент использует внутренне, чтобы определить, когда испускать нерекурсивный код. Это зависит только от того, как был написан компилятор.

Ответ 6

Но для меня удивительно то, что я не собирался писать, работает.

По-видимому, происходит то, что на уровне оптимизации 2 в g++ компилятор правильно видит, что если b положителен, ваш код эквивалентен a * b. Также очевидно, что если b отрицательно, ваш код вызывает поведение undefined. Компилятор оптимизирует поведение undefined путем обобщения на a * b во всех случаях. Вот ассемблер из g++ -O2 (i686-apple-darwin10-g++ - 4.2.1):

.globl __Z8multiplyii
__Z8multiplyii:
LFB1477:
   pushq %rbp
LCFI0:
   movq  %rsp, %rbp
LCFI1:
   xorl  %eax, %eax
   testl %esi, %esi
   je L5
   movl  %esi, %eax
   imull %edi, %eax
L5:
   leave
   ret 

Я не доверяю оптимизаторам. IMO ответ компилятора на распознавание поведения undefined должен заключаться в сбое компиляции, а не в оптимизации поведения undefined.

Edit

Вместо добавления другого ответа в качестве другого ответа, я добавлю еще один ответ в качестве редактирования.

Спросите любого физика значение бесконечной суммы 1 + 2 + 3 +... и они скажут вам, что это -1/12. (например, см. http://math.ucr.edu/home/baez/qg-winter2004/zeta.pdf). Это идет длинный путь вокруг работ аналогичным трюком арифметики дополнений. Решение, которое не предполагает долгого пути для отрицательных чисел:

int multiply (int a, int b) {
   if (b == 0) {
      return 0;
   }
   else if (b < 0) {
      return -multiply (a, -b);
   }
   else {
      return a + multiply(a, b-1);
   }
}

Даже при высоких уровнях оптимизации мой компилятор уже недостаточно умен, чтобы распознать выше как умножение. Разделите это на две функции, и компилятор еще раз узнает, что то, что делается, является целым умножением:

int multiplyu(int a, unsigned int b) {
   return (b == 0) ? 0 : a + multiplyu(a, b-1);
}

int multiply(int a, int b) {
   return (b < 0) ? -multiplyu (a, -b) : multiplyu (a, b); 
}

Ответ 7

Обе формы multiply аварии в Visual Studio с переполнением стека, когда b отрицательный.

Итак, ответ таков: ни одна форма не верна. Вероятно, что происходит в gcc, так это то, что из-за некоторой причуды (а не ошибки!) Компилятор оптимизирует хвостовую рекурсию в первом примере, но не второй.

В качестве побочной заметки, даже если вы измените ее на b > 0 ? --b : ++b, вы все равно не умножаетесь знаком b (например, multiply(-1, -1) == -1)