# Thread: Confused??? Is one of these codes more efficient than the others?

1. ## Confused??? Is one of these codes more efficient than the others?

The question:
In terms of the number of mathematical calculations required, is your new implementation more or less efficient that the ones you used in Chapter 4?

:confused: to my mind there does not seem to be a great deal of difference in the amount of calculations being done... Have i done this wrong?

the chapter four codes print more stuff on the screen. but aren't the calculations virtually the same. is the efficiency anything to do with whats being put on the screen? or is it like the question suggests to do with the calculations being done?

heres the code i did for chapter 4 exercise 9:
Java Code:
```import acm.program.*;
public class FibonacciSeq extends ConsoleProgram {

private static final int LAST = 15;

public void run(){
int f0 = 0;
int f1 = 1;

for(int i = 0 ; i <= LAST;  i++){
println("F"+ i +" : "+f0);
f0+=f1;
i++;
println("F"+ i +" : "+f1);
f1+=f0;
}
}
}```
and this is Exercise 10 similar but with a while loop
Java Code:
```import acm.program.*;
public class FibonacciSeqWhile extends ConsoleProgram {

private static final int LAST = 10000;
public void run(){
int f0 = 0;
int f1 = 1;
int i = 0;

while(true){
if ( f0 > LAST) break;
println ("F"+ i +" : "+f0);
f0 += f1;
i++;
if (f1 > LAST) break;
println ("F"+ i +" : "+f1);
f1 += f0;
i++;
}
}
}```
The Task for chapter 5 is:
Rewrite the fibonnacci programs from chapter 4, changing the implementation so that your program calls a method to calculate the nth Fibonacci number.
here is my code:
Java Code:
```import acm.program.*;
public class FibonacciMethod extends ConsoleProgram {

public void run(){
enterVariable();
}

private void enterVariable() {
int n = readInt(" Enter an integer value ");
println ("F"+n+" : "+ fibonacci(0, 1, n));
}

private int fibonacci(int f0, int f1, int n) {
for(int i=0; i <= n; i++){
if ( i == n ) return f1;
f0 += f1;
i++;
if ( i == n ) return f0;
f1 += f0;
}
return n;
}
}```
So which is most efficient? have i missed something or done it wrong?

EDIT:
or is the answer that neither is more efficient it is simply about style??
.. i think i need a beer :confused:
Last edited by sonny; 03-19-2010 at 04:52 AM. Reason: is the answer neither?  Reply With Quote

2. ## Seems to there no difference at all, in contrast with mathematical calculations.

And also, if you write a simple code to test the performance of for loop and while loop then there is no much difference at all. So I wonder from where your codes get efficiency.

Considering for and while loops, the difference is semantic :

In while loops, we will loop it as long as the condition is true. You might, in the loop, we modify the variables using in evaluating the while condition.

In a for loop, we will loop it N times, N can be variable, but doesn't move until the end of our loop. Normally we didn't do any changes to the condition in for loop.  Reply With Quote

3. ## Seems to there no difference at all, in contrast with mathematical calculations.

And also, if you write a simple code to test the performance of for loop and while loop then there is no much difference at all. So I wonder from where your codes get efficiency.

Considering for and while loops, the difference is semantic :

In while loops, we will loop it as long as the condition is true. You might, in the loop, we modify the variables using in evaluating the while condition.

In a for loop, we will loop it N times, N can be variable, but doesn't move until the end of our loop. Normally we didn't do any changes to the condition in for loop.  Reply With Quote

4. ## The stop criteria for those algorithms are completely different. Pencil and paper are needed here: jot the printed numbers down and see when the algorithms stop; they can't be compared.

kind regards,

Jos  Reply With Quote

5. ## So that's define the execution time, to complete the task, isn't it? I mean it not gives any clue about the efficiency of those algorithms/codes.  Reply With Quote

6. ##  Originally Posted by JosAH The stop criteria for those algorithms are completely different. Pencil and paper are needed here: jot the printed numbers down and see when the algorithms stop; they can't be compared.

kind regards,

Jos
So what have i learned?

Do you mean that:
exercise 9 finishes at the 15th step
execrise 10 finishes when the value reached is 10000
and the chapter 5 (final) code stops when it reaches the nth number as inputted........

Then assume that in exercise 9
private static final int LAST = 19
exercise 10 is the same, and 19 is read in to the last code.
then all the algorithms finish at the same point. don't they?

can i compare them now?

remembering that this exercise comes at the end of the chapter about methods.. I am still caught in two minds or maybe even more than 2.

either:
there is no difference in the efficiency of the calculation process, it is simply an exercise to illustrate that writing good methods makes programs more functional. and its nothing to do with efficiency. ( i.e. it is a badly worded question)

OR

I have written the final code wrong and there is a more efficient algorithm to generate the sequence...... but hang on...... what if I had used that more efficient algorithm in the previous code.......... is there a more efficient algorithm that could only be used by employing a method. Have I in fact, done it wrong and need to find another way of doing it?

call me a pessemist but I am leaning toward the latter:(  Reply With Quote

7. ## OKay the code is wrong but only slightly

the index has to start at 1 otherwise, if 1 is entered it gives a result F0 = 1 and the sequence is wrong,

edit:
scrap that actually i just reverse my return statements

i added a while loop to make it easier to test.
i now have this but still no closer to anwering the question unless there is another way.

Java Code:
```import acm.program.*;
public class FibonacciMethod extends ConsoleProgram {

public void run(){
enterVariable();
}

private void enterVariable() {
while(true){
int n = readInt(" Enter an integer value ");
println ("F"+n+" : "+ fibonacci(0, 1, n));
}

}

private int fibonacci(int f0, int f1, int n) {
for(int i=0; i <=n; i++){
[COLOR="red"]if (i==n)return f0;[/COLOR]
f0+=f1;
i++;
[COLOR="Red"]if (i==n)return f1;[/COLOR]
f1+=f0;
}
return n;
}
}```
Last edited by sonny; 03-19-2010 at 05:05 PM. Reason: correction to correction  Reply With Quote

8. Senior Member Join Date
Mar 2010
Posts
952
Rep Power
10

## The Task for chapter 5 is:
Rewrite the fibonnacci programs from chapter 4, changing the implementation so that your program calls a method to calculate the nth Fibonacci number.
...is hinting that you're supposed to write a recursive method.
Java Code:
```        public int fibonacci(int n) {
...
}```
Take a crack at writing it yourself. Remember what we learned before about recursion -- figure out what the base condition is, check if you're at that base condition, and if so, return the simple answer (Hint: fibonacci(0) = 1). If you're not at the base condition, do the easy thing, and hand off the hard thing to another version of yourself (Hint: fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)).

After you implement that, the questions about how much computation gets done will make more sense, I think.

-Gary-  Reply With Quote

9. ## This is not it then :(

This is not it then :(
Java Code:
```import acm.program.ConsoleProgram;

public class fibonnaciIntMethod extends ConsoleProgram{
public void run(){
enterVariable();
}

private void enterVariable() {
while(true){
int n = readInt(" Enter an integer value ");
println ("F"+n+" : "+ fibonacci(-1, 1, n));
}
}

private int fibonacci (int lastN, int nextN, int n){
for (int i = 0; i <= n; ++i){
int spareN = nextN + lastN;
lastN = nextN;
nextN = spareN;
}
return nextN;
}
}```

okay ,, actually the chapter is not about recursion
that was something i saw JosA doing in a couple of threads and thought i would just try to use with my heirarcy program as a distraction to the fact i couldnt get the Gline to work.

but since youve said it

err let me think and have a crack at recursion..

this was my next attempt but actually it is sort of just a different take on the earlier code and i dont think its any more efficient anyway even though theres only one calculation per loop -- it goes through the loop twice as many times cos the index onlt increases by one... AAAArrrggghhhh...

okay recursive method... think recursive....  Reply With Quote

10. ##  Originally Posted by sonny This is not it then :(
Java Code:
```import acm.program.ConsoleProgram;

public class fibonnaciIntMethod extends ConsoleProgram{
public void run(){
enterVariable();
}

private void enterVariable() {
while(true){
int n = readInt(" Enter an integer value ");
println ("F"+n+" : "+ fibonacci(-1, 1, n));
}
}

private int fibonacci (int lastN, int nextN, int n){
for (int i = 0; i <= n; ++i){
int spareN = nextN + lastN;
lastN = nextN;
nextN = spareN;
}
return nextN;
}
}```
(You forgot to define variable 'spareN'; an iterative solution is much more efficient than a naive recursive solution: have a look at one:

Java Code:
```int fib(int n) {
if (n <= 1) return n;
return fib(n-2)+fib(n-1);
}```
It looks nice, simple and elegant but take a closer look: if you want to calculate, say fib(5) you have to calculate the following:

Java Code:
```fib(5) ==
fib(3)+fib(4) ==
fib(1)+fib(2)+fib(4) ==
1+fib(0)+fib(1)+fib(4) ==
1+0+1+fib(2)+fib(3) ==
1+0+1+fib(0)+fib(1)+fib(3) ==
1+0+1+0+1+fib(1)+fib(2) ==
1+0+1+0+1+1+fib(0)+fib(1) ==
1+0+1+0+1+1+0+1 == 5```
Look how many times fib(4) and fib(3) and fib(2) are calculated; each calculation is one function call. For larger values of n this number becomes horribly large. Give it a try and see for yourself.

This is one of the reasons for 'memoizing', a technique that remembers function values and avoids calling the function again if its value is already known. Of course that function should be 'referential transparent'.

kind regards,

Jos
Last edited by JosAH; 03-19-2010 at 06:47 PM.  Reply With Quote

11. ## TA DA! even though i see Jos beat me to it :-)

TA DA! even though i see Jos beat me to it :-)

i must admit i found this really tough, i had to go and read about fibbonacci sequence and recurrence relation on wikipedia and math sites and stuff,,
and my brain hurts. all that reading to work out just a few lines!! AND ITS NOT EVEN MORE EFFICIENT

edit:
but some times recursion is more efficient see this http://www.java-forums.org/new-java/...recursion.html

Java Code:
```	private void enterVariable() {
while(true){
int n = readInt (" Enter an integer value ");
println ("F"+n+" : "+ fibbonaci ( n ));
}
}

private int fibbonaci (int n){
if (n == 1 || n == 0)
return n;
else
return (fibbonaci (n - 1) + fibbonaci (n - 2));
}

}```
it kind of does it backwards meaning its not very efficient at all for large numbers.. jos explains it better...

but the point here is iteration (either for or while) is usually better.
and taking Erangas point from earlier the choice depends on whether you know how many iterations or untill a condition is met.

You forgot to define variable 'spareN';
:confused::confused:
Java Code:
```private int fibonacci (int lastN, int nextN, int n){
for (int i = 0; i <= n; ++i){
[COLOR="Red"] int spareN = nextN + lastN;[/COLOR]
lastN = nextN;
nextN = spareN;
}
return nextN;
}
}```
do you mean define or initialise?
Last edited by sonny; 03-22-2010 at 04:17 AM.  Reply With Quote

12. ##  Originally Posted by sonny :confused::confused:
Java Code:
```private int fibonacci (int lastN, int nextN, int n){
for (int i = 0; i <= n; ++i){
[COLOR="Red"] int spareN = nextN + lastN;[/COLOR]
lastN = nextN;
nextN = spareN;
}
return nextN;
}
}```
do you mean define or initialise?
Nothing; I'm blind and forgot to take my pills so I'm not responsible for what I wrote; nothing to see here, please walk on.

kind regards,

Jos ;-)  Reply With Quote

efficiency, methods 