/*
* File: FibSequence2.java
* Name: Renee
* Section Leader: Me!
* -----------------
* THE USMAN VERSION
*/
import acm.program.*;
public class FibSequence2 extends ConsoleProgram {
public void run() {
//Getting the first two in the sequence started...this is a bit inelegant.
int n0 = 0;
int n1 = 1;
println(n0);
println(n1);
//Now kicking off the fun part.
for (int i = 2; i < END; i++) {
n1=n1+n0;
println(n1);
n0=n1;
}
}
//Private constant; "End" is the the nth number in the Fib sequence displayed.
private static final double END = 15;
* File: FibSequence2.java
* Name: Renee
* Section Leader: Me!
* -----------------
* THE USMAN VERSION
*/
import acm.program.*;
public class FibSequence2 extends ConsoleProgram {
public void run() {
//Getting the first two in the sequence started...this is a bit inelegant.
int n0 = 0;
int n1 = 1;
println(n0);
println(n1);
//Now kicking off the fun part.
for (int i = 2; i < END; i++) {
n1=n1+n0;
println(n1);
n0=n1;
}
}
//Private constant; "End" is the the nth number in the Fib sequence displayed.
private static final double END = 15;
OK, here it is, and it works. For the record, this is decidedly LESS elegant than the 3-variable version. My math self is exploding in her cranium.
ReplyDelete/*
* File: FibSequence2.java
* Name: Renee
* Section Leader: Me!
* -----------------
* THE USMAN VERSION
*/
import acm.program.*;
public class FibSequence2 extends ConsoleProgram {
public void run() {
//Getting the first two in the sequence started...this is a bit inelegant.
int n0 = 0;
int n1 = 1;
println(n0);
//Now kicking off the fun part.
for (int i = 1; i < END; i++) {
n1=n1+n0;
n0=n0+n1;
println(n1);
println(n0);
}
}
/*Private constant. If you want the N first numbers of the Fib sequence displayed,
set END to N/2, plus 1 if N is odd. Ew.*/
private static final double END = 8;
Notice how you're updating n1 then updating n0? That throws your updated n0 value off. So instead of n0 = n1, you should either use a temp variable or do n0 = n1 - n0 (to account for the difference added to n1.
ReplyDelete--Sarah
ps- Glad to hear you're enjoying your programming course! :D
Variations on fixing the inner loop of the first version:
ReplyDelete// Using a temp variable
int tmp = n1;
n1 = n1 + n0;
n0 = tmp;
println(n1);
// Subtracting instead of using a temp variable
n1 = n0 + n1;
n0 = n1 - n0; // Equals previous value of n1
println(n1);
// Combining the add and the print for less lines
println(n1 = n0 + n1);
n0 = n1 - n0;
// Swapping whether to update n0 or n1
println((i & 1) ? n1 = n1 + n0 : n0 = n0 + n1);
None of these seem really elegant to me. I've also seen it done using an array:
int fib[15];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i < END; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
for (int j = 0; j < END; j++) {
println(fib[j]);
}
This is less efficient (uses lots more memory and does two loops), but to me it's easier to read.
I wonder if the requirement to print out all of the fibonacci numbers is to keep you from doing the recursive version?
private int fib(int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
The recursive version is much less efficient than all the other versions--do you see why?
println(n0 > n1 ? (n1 = n0 + n1) : (n0 = n0 + n1));
ReplyDeleteHmm, Annie, now you're the third person who said I should do it using an array. I haven't studied that yet. It looks like an array is a function (ie, "f OF something")? I think that's how you demo'ed it when you came over- I looked at your notes, but couldn't figure it out how to solve it that way with the tools we have now! That should be coming soon...
ReplyDeleteUsman, we haven't started methods yet, but I think that's in the next Ch :]
This comment has been removed by the author.
ReplyDeleteHaha, good effort, Renee! I kind of expected you to take it as a challenge, despite my warning. :]
ReplyDeleteAs you might be able to tell, one moral is that there are lots of ways to do it with only two variables. With what you've already been taught, though, I think these might be the most straightforward and easiest for you to digest & understand:
n1 += n0;
println(n1);
n0 = n1 - n0;
or:
if (n0 < n1) {
println(n0 += n1);
} else {
println(n1 += n1);
}
Both solutions have already been suggested in some form in previous comments, and neither requires any modification to the code outside of the for loop nor the introduction of new concepts. Can you see the differences between the two? Understanding exactly what each version of the solution is doing might also help you with some of the tricky concepts you mentioned having trouble with in a previous post.
And as I said before, these are only slightly more elegant, depending upon your definition of "elegant".. though, if I had to choose, Annie's
println((i & 1) ? n1 += n0 : n0 += n1);
would be the winner in terms of code density, efficiency, and trickiness, hands-down. Renee, please don't try this at home just yet -- your coding self will explode in her cranium, and then where would this blog be? ;]
In any case, none of these elegance-enhanced modifications are really necessary, all require more mental effort for a human to figure out, and this alone makes them not recommended in general. You will eventually learn this, but (and here's the other moral) code clarity and correctness are much more important than any notion of "elegant" code, which can translate to anything from "clever, efficient, and aesthetically pleasing" to "tricky, obscure, and unreadable" code. Still, it's a fun exercise. :D
+10 extra credit points! Keep up the good work, and enjoy the rest.
(I keep clicking post instead of preview! Sorry!)
ReplyDeleteIf I saw code like:
ReplyDeleteprintln((i & 1) ? n1 += n0 : n0 += n1);
either from a student or in production, I would flip my shit :) It's worse in most every metric:
Readability - on the floor.
Efficiency - I suspect it's faster to do two assignments (=) than it is to do a test (if) and an assignment (=). And the & trick buys you nothing. This is what we call "premature optimization", where you make your code ugly to make it faster with no evidence that it will actually run faster.
Trickiness - this is never a metric you want to optimize for.
Lines of code - this is the only place it wins, and it's not worth it.
I think the three-variable answer was the best. My only problem with it was the names of the variables. How are you supposed to keep straight which one is 0/1/2?
LiteratePrograms.org gives an excellent answer:
http://en.literateprograms.org/Fibonacci_numbers_%28Java%29
int prev1=0, prev2=1;
for(int i=0; i < n; i++) {
int savePrev1 = prev1;
prev1 = prev2;
prev2 = savePrev1 + prev2;
}
That is, in my opinion, the most elegant want to do the fibonacci function in such an inelegant language as Java :)
p.s. this is a great idea for a blog! do keep posting.
Yeah, I wasn't actually suggesting you switch to any of those versions! (Except maybe the one with the temp variable declared inside the loop.)
ReplyDeleteI was more trying to say that I don't understand how reducing the number of lines/number of variables in this case makes the code more elegant. To me, elegance is the intersection of less code/more readability. There are lots of ways to reduce the amount of code, but they all seem to reduce the readability, too.
About arrays, here's a link that explains them a little: http://java.sun.com/docs/books/tutorial/java/nutsandbolts/arrays.html
I think the code that uses the array is clear because in the inner loop, all that's there is the calculation of the next fibonnaci number; there's no twiddling to update the previous numbers. If you didn't know what the code was supposed to do, you could understand pretty clearly from reading it. But it stores ALL of the previous fibonacci numbers in the array, not just the last one or two. On the other hand, what Jason said about premature optimization is pretty important. If you know you're only going to be calculating 15 numbers, you're not using much memory at all. Each int is 4 bytes, so 4x15 = 60 bytes. By contrast, if I type "about:memory" into the urlbar in Chrome right now, I can see that it's using 50 megabytes. A megabyte is a million bytes, so we're talking about your program using about one millionth of the memory that a web browser uses. Not a huge deal, in my opinion. But it's good to know that as it's written now, the memory usage is constant, and in the array version, the memory usage grows with the number of fibonacci numbers you're calculating.
Now I feel lost as to what exactly means to have an elegant code. I used to think that elegant solutions are the ones that reduce use of resources and has less line codes, but then, I would pick
ReplyDeleteif (i%2!=0 ) n1+=n0;
else n0+=n1;
over
println((i & 1) ? n1 += n0 : n0 += n1);
any day. Sometimes, obscurity leads to smarter code (which is one of the reasons why people leave comments after using a trick) but is it really necessary to use a i&1 instead of i%2!=0 when the compiler is going to take care of that?
So is elegancy a balance between compactness and readability? Maybe this is a quality akin to beauty. There is always that je ne sais quois about a elegant solution that makes us say 'this is an elegant solution'.
Personally I like more Renee's original solution (with a fix on the END variable that is indeed ugly) or Annie's solution with subtractions better just because it doesn't use conditionals. Why use 'if' when it's not needed?
That's an interesting comment about "a elegant solution that makes us say 'this is an elegant solution'." I'd always thought the opposite--an elegant solution is one that you don't notice at all, or if you do, it makes you say, "well of course, how else would you do it?". One that garners far less attention or discussion than my "printf((i & 1)...)" hack because it's simple, clear, and concise.
ReplyDeleteThis is good discussion! I think the notion of "elegance" in code isn't very well-defined, at least not in any universally accepted way. Many attempts at a definition have been made and discussed/debated in the past, though, which probably means it's an important concept. :]
ReplyDeleteAt the risk of causing you information overload (which I fear this thread may have already done), I found a couple links that present some well-thought-out interpretations that may be worth consideration.
The below links to the intro of a chapter in an online book on Unix programming. No need to read the chapter itself, and it's fine to ignore the unfamiliar terms, but that page presents a compelling take on the issue, especially the paragraph starting "Transparency is a major component...":
http://www.catb.org/~esr/writings/taoup/html/transparencychapter.html
The page at the next link does a good job of presenting the problem of defining "elegance" w.r.t. programming and then in turn poses a few well-phrased questions to the greater programming community. I like the top voted answer, but my favorite answer is actually the one by Adam Bellaire that starts with '"Elegant" is a good word choice...' (4th one down as of right now):
http://stackoverflow.com/questions/563036/what-is-elegant-code
Hokay! All that said, here's a recap of the lessons I think are worth taking from this thread:
- there are many ways to solve the same problem
- correctness & readability outweigh "elegance" (especially if the definition of "elegant" doesn't already include "readable")
- learning how to do certain things, while sometimes fun and often useful, is not nearly as important as knowing *why* and *when* to do (or not do) them.
+1000000 points to everyone!
I wonder if some day we will have experts on coding style. Critics would be saying things like "This code belongs to the macaroni school", or "In this you can see that the architect had a training in Extreme Programming...". I would love to see that.
ReplyDeleteTo go along with "There's more than one way to do it", here's what the solution might look like in Common Lisp (a completely different programming language):
ReplyDeletehttp://gist.github.com/246945
In many ways, the really important thing to learn is not the actual language, but the thought process that goes into designing the program.
HI,
ReplyDeleteI'm not sure but your result displays following sequence of digits : 0,1,1,2,4,8,16... instead of 0,1,1,2,3,5,8, am I wrong?