fibonacci works in python but fails in Java

Question

I have this code for calculating fibonacci number in python. It works and gives the expected result. but when I translated the same to Java, it fails. Any idea of what is going wrong here?

In python:

def fib3(n): 
  a,b=0,1
  while n>0:
      a,b=b,a+b
      n-=1
  return a

fib3(12) --> 144

In Java:

 public static int fib2(int n){
        int a = 0;
        int b =1;
        while(n-- >0){
            a=b;
            b=a+b;

        }
    return a;
}

fib2(12) --> 2048

Answer 1

In this section:

a=b;
b=a+b;

you're assigning b to a+b, but a is already b. So really you're doubling b

Easiest solution is a temp variable:

public static int fib2(int n){
    int a = 0;
    int b =1;
    while(n-- >0){
        int old_a;
        old_a = a;
        a=b;
        b=old_a+b;
    }
    return a;
}

In python, a, b = b, a + b stores an intermediate tuple automatically before assigning the new values to the variables, while in Java you need to be explicit about it

Breaking down Python's instructions, a, b = b, a + b is executing this disassembly:

  5          17 LOAD_FAST                1 (b)
             20 LOAD_FAST                0 (a)
             23 LOAD_FAST                1 (b)
             26 BINARY_ADD
             27 ROT_TWO
             28 STORE_FAST               0 (a)
             31 STORE_FAST               1 (b)

In a simpler sense, staying python, here's the process:

temp_tuple = (b, a + b)
a, b = temp_tuple

Answer 2

The issue is that you've got to one value from b to a at the same time as assigning to b the sum of a and b. Get that simultaneous swap wrong and you get the wrong answer.

In the spirit of the Python code, I present:

public static int fib(int n) {
    int a = 0, b = 1;
    while (n-->0)
        b = a + (a = b);
    return a;
}

This does the swap effectively at the same time as the add (strictly not, but it's good enough). Note that this is well-defined Java, as the language defines the evaluation order of operators precisely, unlike in C and C++ (where the equivalent of the above code is permitted to make demons fly out of your nose due to being Undefined Behavior).

---

OK, if it did make you experience problems with nasal demons, I'd suggest not using that compiler in future. But you wouldn't have any assurance of getting a correct fib() function…

Answer 3

a = b;
b = a+b;

This computes b = 2*b because a's value is overwritten by the time you compute the new value for b. Replace it with:

t = b;
b = a+b;
a = t

Answer 4

a=b;
b=a+b;

... is the problem. You need to save the old value of a before adding it to b.

Answer 5

The code is not equivalent, and relies on python's ability to assign multiple primitives in one line a,b=b,a+b; you need a temporary variable -

public static int fib2(int n){
  int a = 0;
  int b =1;
  while(n-- >0){
      int t = b; // <-- to hold the original value of b.
      b = a + b;
      a = t;
  }
  return a;
}

Answer 6

In java - When you write "a=b; b=a+b;" you are essentially saying that a should be equal to be and then that (since 'a' is now equal to 'b') that 'b' should just be twice what it originally was. There are two ways you can fix this. 1) You can either continue the function you are originally using and then create a int 'temp' to store 'a' before you change 'a'. 2) You can also do what I would rather do ( this will use a lot more time however for a algorithm like fibonacci and would generally be a terrible idea for real world applications) is use a recursive function that will call itself.

It would generally look something like the following.

    public static int fib2(int n){
           if(n<=0){return 0;}
           if(n<2){return 1;}
           else{ return fib2(n-1)+fib2(n-2);}
    }

That would probably not be the exact code but something very similar. Hope that was helpful!