Results 1 to 12 of 12
 03192010, 04:39 AM #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; } } }
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++; } } }
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; } }
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; 03192010 at 04:52 AM. Reason: is the answer neither?
:p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts
 03192010, 09:04 AM #2
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 22
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.
 03192010, 09:04 AM #3
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 22
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.
 03192010, 09:05 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,320
 Blog Entries
 7
 Rep Power
 25
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
 03192010, 09:13 AM #5
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 22
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.
 03192010, 03:20 PM #6
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:(:p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts
 03192010, 04:54 PM #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; 03192010 at 05:05 PM. Reason: correction to correction
:p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts
 03192010, 05:08 PM #8Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 7
Isn't your current chapter about recursion? I think this:
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.
Java Code:public int fibonacci(int n) { ... }
After you implement that, the questions about how much computation gets done will make more sense, I think.
Gary
 03192010, 05:36 PM #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....:p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts
 03192010, 06:45 PM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,320
 Blog Entries
 7
 Rep Power
 25
(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(n2)+fib(n1); }
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
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,
JosLast edited by JosAH; 03192010 at 06:47 PM.
 03192010, 07:24 PM #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 more fun... with recursion
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)); } }
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';
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; } }
Last edited by sonny; 03222010 at 04:17 AM.
:p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts
 03192010, 07:32 PM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,320
 Blog Entries
 7
 Rep Power
 25
Similar Threads

What is the easiest and most efficient vision library...
By jakx12 in forum Advanced JavaReplies: 1Last Post: 08132009, 08:10 PM 
A more efficient Game of Life
By unreal4evr in forum New To JavaReplies: 3Last Post: 03272009, 04:08 AM 
Need a simple and efficient solution.
By Samgetsmoney in forum New To JavaReplies: 9Last Post: 02202009, 02:18 AM 
Efficient Perfect Number
By Lite3864 in forum New To JavaReplies: 4Last Post: 11232008, 02:07 AM
Bookmarks