Results 1 to 12 of 12
  1. #1
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Question 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?
    :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

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

    Default

    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.


  3. #3
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

    Default

    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.


  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    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

  5. #5
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

    Default

    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.

  6. #6
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    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:(
    :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

  7. #7
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Red face 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
    :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

  8. #8
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    952
    Rep Power
    5

    Default

    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.
    ...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-

  9. #9
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Default 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

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by sonny View Post
    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.

  11. #11
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Talking 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));
        }
    
    }
    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.
    :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

  12. #12
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by sonny View Post
    :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 ;-)

Similar Threads

  1. Replies: 1
    Last Post: 08-13-2009, 09:10 PM
  2. A more efficient Game of Life
    By unreal4evr in forum New To Java
    Replies: 3
    Last Post: 03-27-2009, 04:08 AM
  3. Need a simple and efficient solution.
    By Samgetsmoney in forum New To Java
    Replies: 9
    Last Post: 02-20-2009, 02:18 AM
  4. Efficient Perfect Number
    By Lite3864 in forum New To Java
    Replies: 4
    Last Post: 11-23-2008, 02:07 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •