A difficult java problem...(java expert please help)

[albertlee]

I have made three classes:

 

CalculateFib.class

public class CalculateFib{
  public static void main(String sad[]){
     Fib2.fib(300);
     Fib1.fib(300);
  }

}

 

Fib1.class

public class Fib1{

  public static long fib(long n){

     if(n==0)
        return 1
     if(n<0)
        return 0

     long high = fib(n-1);
     long low = fib(n-2);

     return high+low;

  }
}

 

Fib2.class

public class Fib2{

  public static long lastFibIndex = 0;
  public static long lastFibValue = 1;

  public static long fib(long n){

     if(n==0)
        return 1
     if(n<0)
        return 0
     if(n==lastFibIndex)
        return lastFibValue

     long high = fib(n-1);
     long low = fib(n-2);

     lastFibIndex = n-1;
     lastFibValue = high;

     return high+low;

  }
}

 

It is very nice of you if you guys can oblige me by giving a try on compiling these codes and try them.

 

If so, you will see how fast Fib2 is compared to Fib1.

 

Why's that??

 

I dont know why those extra lines in the Fib() method speed up the computation so much quicker, ie:

 

 if(n==lastFibIndex)
        return lastFibValue

and

lastFibIndex = n-1;
     lastFibValue = high;

 

As I said before, the only difference is the sample code (faster one) has those two ambiguous class varriables, which I dont see any much point of them in the computation of fib number, because the sample code is the same as my own shorter one, except with extra codes.

 

Any body please explain why??

 

thanks

[Dave]

The reason it runs so slowly is because of this:

 

long high = fib(n-1);
long low = fib(n-2);

 

This is highly inefficient. Consider what happens when you work out fib(3).

 

            fib(3)
             |
    +-----------------+
    |                 |
high = fib(2)    low = fib(1)
    |                 |
return 1           return 1

 

This is obviously the simplest case involving a lot of recursion. It's slightly different to yours, but the same kind of idea. (I assumed F₁ = 1, F₂ = 1 but same difference tbh). It involves 2 recurses of fib().

 

Now consider what happens when you work out fib(4). The left hand "branch" will be the one drawn above, and the right hand one will simply return 1. Fine so far.

 

However, this is where things start to get interesting. Try drawing the execution diagram for fib(5). Then draw it for fib(6). You should notice that the number of executions of fib() for larger n becomes really very big, very quickly. I believe that the number of executions of fib for fib(n) is something like 2^n-1 or something to that degree. It's certainly an exponential relation, that's for sure. So for n = 300, you can imagine it might take a long time to work out!

 

I'll look at the other code in a bit. I think it's just a nice way of limiting the number of executions for a particular branch. I'd personally say that the Fibonacci numbers don't lend themselves terribly well to a recursive algorithm (as do many things of this fashion), but it's good practice.

[Aeternus]

It's because in Fib2 you are doing far fewer calculations because when calculating the low number it has already been calculated when calculating the high number.

 

Take for instance - Fib(5)

 

It will do -

 

Fib(4) + Fib(3)

which in turn does

(Fib(3)+Fib(2)) + (Fib(2)+Fib(1))

which in turn does

((Fib(2)+Fib(1)) + (Fib(1) + Fib(0))) + ((Fib(1) + Fib(0)) + Fib(1))

Which in turn does

(((Fib(1) + Fib(0))+Fib(1)) + (Fib(1) + Fib(0))) + ((Fib(1) + Fib(0)) + Fib(1))

 

Which is where it terminates giving an answer of 1+1+1+1+1 = 5 (this has been stated by Dave).

 

Notice the amount of repetition of Fib() calls with the same value. What this second procedure is doing is storing previously called values from each recursive step in a static variable (a variable that has a defined memory for that function rather than for each function call meaning its value will be the same across function calls, meaning you can store something one function call and access it the next) and then when you make the next call if the value has already been calculated you have it there.

 

For instance take Fib(4) -

 

1st Level of Recursion -

Fib(3) -> Second Level Of Recursion -> Value returned

Fib(2) -> Answer is already in that static variable so it goes down a level and that wonderful if statement returns the value.

 

Second Level of Recursion -

Fib(2)-> Third Level

At this point it then stores the answer to Fib(2) in the static variable (high).

 

Third Level

Fib(1) -> Return (ie goes back to Second then third)

 

This happens on various levels and so it greatly reduces the order of complexity of the algorithm.

 

The way ive explained it is rather strange but it seems a hard concept to grasp unless you're face to face and I find it hard to explain myself sometimes. Feel free to ask questions or challenge anything ive said, perhaps someone could explain it further.

[Dave]

Ahha, Aeternus got the second bit, so now I don't have to bother explaining it.

 

Bonus

[albertlee]

I kinda figure that out by myself :-D

 

the real, important question is, is there way to treat algorithm as mathematics?? Designing an algorithm??