Error in Fibonacci program

Question

I am trying to find the k-th Fibonacci number in C using:

int fibk(int k)
{
    if(k == 1 || k== 2)
        return 1;

    int i,a = 1,b = 1;

    for(i=3;i<=k;i++)
    {
            b = a + (a=b);
    }

    return b;
}

I have earlier used this code for swapping two variables values:

    a = a + b - (b = a)

So I was trying:

     b = a + (a=b);

But this code is first changing a's value to b and simply adding it back to itself effectively doubling its value rather than adding it to its previous value.

Why does the swapping code work but not the code for finding next Fibonacci number?

Answer 1

To answer the question: both a = a + b - (b = a); and b = a + (a=b); have undefined behaviour. C does not specify either the order of evaluation, nor the order that side-effects (such as variable assignment) occur, unless there is an explicit sequence point. So in both the above expressions, the assignment on the right-hand side could happen before, after or while the value of the assigned variable is accessed. (The "while" case covers the case where the assignment is done in more than one machine instruction, perhaps because the variable is too large to be stored or loaded in a single instruction.)

"Undefined behaviour" is just that -- undefined. It may mimic the behaviour which you erroneously expect; it may simply do things in an unexpected order; it may produce unintelligible garbage; or it may be simply deleted by the compiler so that nothing at all happens. Or many other possibilities. And there is no guarantee that a program with undefined behaviour will behave the same way as the same program compiled tomorrow.

---

For a small bonus, since you seem to be attempting to avoid use of a temporary variable, here's a different fibonacci hack with no temporary and no UB:

int fibk(int n) {
  int a = 1, b = 0, i = n - 1;
  for (; i > 0; i -= 2) {
    b += a;
    a += b;
  }
  return i ? b : a;
}

Since it unrolls the loop, it might be slightly faster. Then again, it might not. :)

Answer 2

Operation on 'a' may be undefined, so "swapping code" actually "not working". One approach is, you can use a tem(temporary) variable to keep the value of b. Try like this:

tem = a + b;
a = b;
b = tem;