Given that b is always non-zero, why `b ? --b : ++b` works, but `--b` does not?_问答_开发者

I was trying to multiply two integers using recursion, and wrote this code, accidently:

//the original version
int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else
     return a + multi开发者_运维百科ply(a, b ? --b : ++b ); //accident
}

I said, I wrote this accidently, because I intended to write :

b > 0 ? --b : ++b instead of b ? --b : ++b

I realize that what I intended to write wouldn't work. But what is surprising to me is, what I did not intend to write does work.

Now, I note that b ?--b : ++b is basically equivalent to --b because b in else-block is guaranteed to be non-zero. So I modified the above code, replacing b?--b:++b with --b, as shown below:

//the modified version
int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, --b); //modification here
}

Since the original version woks, I expected the modified version to work as well. But again, to my surprise, it doesn't work!

What is wrong the modified version?
Is it not equivalent to the original version?
Is --b not equivalent to b ?--b : ++b IF b is non-zero? If its equivalent, then why does the first code work but the second doesn't?

Note: here, by "work", I mean it gives the correct output. That is, it gives the multiplication of the integers passed to the function.

It doesn't work. I don't know what ideone is smoking, that code is going to overflow the stack.

EDIT

Tried it on gcc 4.6.0 - segfault (due to stack overflow). If however you enable -O2 optimizations, then indeed "it works". In conclusion: it works by chance, depending on what the compiler does behind the scenes.

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

TL;DR version: The reason b? --b: ++b prints a result and --b fails with SIGXCPU is that ideone sets a time limit on submitted code. One version gets optimized better, and completes in the time allowed. The other version gives the exact same answer, but you won't see that with ideone because it runs too slowly and gets aborted by the time limit.

As for why the stack overflow isn't occuring, I guess in one case the compiler must be transforming recursion into iteration (this isn't a tail call, but it is trivially transformable).

The result of the transformation would be something like http://ideone.com/AeBYI which indeed gives the correct result. With higher optimization settings, the compiler could calculate the results at compile time and store constants in the resulting code.

The output from the code below should give a very strong clue ;)

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

It looks to me like it's getting the answer by going the long way.

Edit: In response to the comment from Nawaz below, the first method works because of the vagaries of two's complement signed integer arithmetic. Like I said, it takes the long way around. It is enabled, as others have pointed out because of some compiler optimization or another. You can see this in the code below for the test input previously provided:

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

It in fact should work for any pair of integers but will take some time to run in some case (but I expect you weren't interested in efficiency in any event).

The second case does not work because your conditional b > 0 ? --b : ++b essentially converts b to abs(b). That is, you only add 7 times in your test case even though b = -7. If you wanted it to behave the way I think you wanted it to behave you would instead need to do something like:

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

Edit 2: Try this instead:

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

and

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

Both of these compile, run and return the same (correct) result with or without optimization. As others have pointed out, the cause of the execution time difference you are seeing can only be attributed to the way the compiler is optimizing your code. You will need to analyze the assembly code of the two methods to determine the root cause of the time discrepancies.

Indeed, it has nothing to do with --b, but with your algorithm.

If b < 0, what do you excpect ? You will loop indefinitively and ends up with a stack overflow.

This is why you have the right result at first multiply(12, 7) but then your program fail when you call multiply(12, -7).

Because of the way 2's complement numbers work, your code is "correct" for both positive and negative values for b. It is just that for negative b's, any recursive version needs a big stack to work. So any time the compiler emits a nonrecursive version, you have working code. So it boils down to: what rule does my complier use internally to determine when to emit nonrecursive code. That just depends on how the compiler was written.

Both forms of multiply crash in Visual Studio with a stack overflow, when b is negative.

So, the answer is, neither form is correct. Likely what is happening in gcc is that, due to some quirk (not a bug!) the compiler is optimizing away the tail-recursion in the first example but not the second.

As a side note, even if you change it to b > 0 ? --b : ++b, you are still not multiplying by the sign of b (eg. multiply(-1, -1) == -1)

But what is surprising to me is, what I did not intend to write does work.

Apparently what's happening is that at optimization level 2 in g++ the compiler correctly sees that if b is positive, your code is equivalent to a*b. It also apparently sees that if b is negative your code invokes undefined behavior. The compiler optimizes that undefined behavior away by generalizing to a*b in all cases. Here is the assembler from 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

I don't trust optimizers. IMO the compiler's response to recognizing the undefined behavior should be failure to compile rather than optimizing the undefined behavior away.

Edit

Rather than adding another answer as another answer, I'll add another answer as an edit.

Ask any physicist the value of the infinite sum 1+2+3+... and they'll tell you that it is -1/12. (e.g., see http://math.ucr.edu/home/baez/qg-winter2004/zeta.pdf). This going the long way around works by a similar trick of twos complement arithmetic. A solution that does not involve going the long way around for negative numbers:

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

Even at high levels of optimization, my compiler is no longer smart enough to recognize the above as multiplication. Split the above into two functions and the compiler once again does recognize that what is being done is integer multiplication:

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