Alex Rivera | Logout

Given that b is always non-zero, why `b ? --b : ++b` works, but `--b` does not?

Asked 2011-06-17T13:39:15.030
16

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 + multiply(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.

Edit
Report

3 Answers

1

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

answered 2011-06-17T13:42:35.657
1

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.

answered 2011-06-17T14:51:32.627
0

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)

answered 2011-06-17T19:21:59.903

Your Answer