 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / November 2006Fabonicseries Program required
Please send me the code for Fabonicseries program in java > Please send me the code for Fabonicseries program in java Fibonacci? > > Please send me the code for Fabonicseries program in java > Fibonacci? Yes > > > Please send me the code for Fabonicseries program in java > > Fibonacci? > > Yes Fibonacci series is: 1 2 3 5 8 13 21 34 55 ...... (N(n) = N(n-1)+N(n-2)) You could write Java code yourself. Ask help from your kindergarten brother. Sirusha, I have written the following method to generate the first 100 numbers in the fibonacci series. As Hiwa says, writing a Fibonacci program should be fairly simple and request you to try your own approach. void printFibonacciSeries() { int x=0, y =0, z=0; for (int i = 0; i < 100; i++) { z=x+y; System.out.print(z+" "); y=x; x=z; if(x==0) { x=1; } } } > > > > Please send me the code for Fabonicseries program in java > > > Fibonacci? [quoted text clipped - 4 lines] > You could write Java code yourself. > Ask help from your kindergarten brother. > Sirusha, > > I have written the following method to generate the first 100 numbers > in the fibonacci series. As Hiwa says, writing a Fibonacci program > should be fairly simple and request you to try your own approach. Don't give code to people demanding we do their work. its better they try to understand it themselves. Its coursework, so he should learn it himself. tom > > > Please send me the code for Fabonicseries program in java > > Fibonacci? No problem. fibonacci ( ) { while(true) { System.out.println("I am a brainless twit."); } } > Yes >>>> Please send me the code for Fabonicseries program in java >>> Fibonacci? [quoted text clipped - 10 lines] > >> Yes Come now. Everyone knows that the best way is: static int fibonacci (int i) { if (i <= 1) return 1; else return fibonacci (i - 1) + fibonacci (i - 2); }  SignatureJohn W. Kennedy "The blind rulers of Logres Nourished the land on a fallacy of rational virtue." -- Charles Williams. "Taliessin through Logres: Prelude" > >>>> Please send me the code for Fabonicseries program in java > >>> Fibonacci? [quoted text clipped - 19 lines] > return fibonacci (i - 1) + fibonacci (i - 2); > } The OP didn't. Now you have deprived him/her of the pleasure of doing his/her own homework. > -- > John W. Kennedy > "The blind rulers of Logres > Nourished the land on a fallacy of rational virtue." > -- Charles Williams. "Taliessin through Logres: Prelude" >>>>>> Please send me the code for Fabonicseries program in java >>>>> Fibonacci? [quoted text clipped - 20 lines] > The OP didn't. Now you have deprived him/her of the pleasure of doing > his/her own homework. I'd like to see the teacher's face when he hands it in. SignatureJohn W. Kennedy "The blind rulers of Logres Nourished the land on a fallacy of rational virtue." -- Charles Williams. "Taliessin through Logres: Prelude" > >>>>>> Please send me the code for Fabonicseries program in java > >>>>> Fibonacci? [quoted text clipped - 22 lines] > > I'd like to see the teacher's face when he hands it in. I see you are a vicious and cruel bastard. It is doubtless you torture puppies in your spare time. You gave the OP a program that was so close to being correct that even I did not see the error at first. You expected the OP to blindly copy your program and lose all face and all marks when the teacher exposes the OP's stupidity. You are fiendishly clever. Your program gives the correct fibonacci sequence for the first 44 numbers and then starting with the 45th number it produces nothing but incorrect results. Obviously, you anticipated that the OP would not check much beyond the 10th number. Hint to OP: To save face, figure out why this heartless bastard's program fails for numbers larger than 44. > -- > John W. Kennedy > "The blind rulers of Logres > Nourished the land on a fallacy of rational virtue." > -- Charles Williams. "Taliessin through Logres: Prelude" >>>>>>>> Please send me the code for Fabonicseries program in java >>>>>>> Fibonacci? [quoted text clipped - 36 lines] > Hint to OP: To save face, figure out why this heartless bastard's > program fails for numbers larger than 44. That's not the only problem. Have you actually tried running it? SignatureJohn W. Kennedy "The blind rulers of Logres Nourished the land on a fallacy of rational virtue." -- Charles Williams. "Taliessin through Logres: Prelude" > >>>>>>>> Please send me the code for Fabonicseries program in java > >>>>>>> Fibonacci? [quoted text clipped - 38 lines] > > That's not the only problem. Have you actually tried running it? Yes, I did. I was very disappointed with my compiler. I would have thought it would have transformed it into an iterative algorithm (at the byte code level). Is this a reasonable expectation? If it is reasonable, then your program (using BigInteger) would be perfectly acceptable for any situation. Regardless of the compiler, your program would probably be perfectly acceptable as is, for an introductory programming class. Have you taught one? Most students will submit buggy programs that do not produce the correct sequence. Correctness is the most important thing, efficiency can be learned later on. > -- > John W. Kennedy > "The blind rulers of Logres > Nourished the land on a fallacy of rational virtue." > -- Charles Williams. "Taliessin through Logres: Prelude" >>>>>>>>>> Please send me the code for Fabonicseries program in java >>>>>>>>> Fibonacci? [quoted text clipped - 40 lines] > thought it would have transformed it into an iterative algorithm (at > the byte code level). Is this a reasonable expectation? A /double/ recursion? I doubt it. > If it is reasonable, then your program (using BigInteger) would be > perfectly acceptable for any situation. [quoted text clipped - 4 lines] > produce the correct sequence. Correctness is the most important thing, > efficiency can be learned later on. There's "efficiency" and there's "running to completion within a human lifetime". This algorithm is O 2^N. SignatureJohn W. Kennedy "The blind rulers of Logres Nourished the land on a fallacy of rational virtue." -- Charles Williams. "Taliessin through Logres: Prelude" > This algorithm is O 2^N. More precisely, it's O(fib(N)). And o(fib(n)). /L SignatureLasse Reichstein Nielsen - lrn@hotpop.com DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html> 'Faith without judgement merely degrades the spirit divine.' >> >>>> Come now. Everyone knows that the best way is: >> >>>> [quoted text clipped - 29 lines] > thought it would have transformed it into an iterative algorithm (at > the byte code level). Is this a reasonable expectation? No, not for the algorithm as posted. It's not tail recursive (it is, in fact, doubly recursive). I posted another algorithm (in LISP, so as not to do the OP's homework) which while technically still recursive /is/ tail recursive and so /can/ have the recursion optimised out. Signaturesimon@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/ ;; "If I were a Microsoft Public Relations person, I would probably ;; be sobbing on a desk right now" -- Rob Miller, editor, /. > >> >>>> Come now. Everyone knows that the best way is: > >> >>>> [quoted text clipped - 34 lines] > do the OP's homework) which while technically still recursive /is/ tail > recursive and so /can/ have the recursion optimised out. Now, I am curious. If I understand correctly, it is unreasonable to expect my compiler to iron out the doubly recursive O(2^n) algorithm, but it is reasonable to expect my compiler to iron out the tail recursive O(n) algorithm. I would like to examine whether my compiler does in fact iron out the tail recursive algorithm. It was easy for me to verify that the compiler was not ironing out the doubly recursive algorithm (because it is so painfully slow compared to the iterative O(n) algorithm). But how would I verify that the compiler is ironing out the tail recursive algorithm. I am not clever enough to examine the byte code. > -- > simon@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/ > ;; "If I were a Microsoft Public Relations person, I would probably > ;; be sobbing on a desk right now" -- Rob Miller, editor, /. >> No, not for the algorithm as posted. It's not tail recursive (it is, in >> fact, doubly recursive). I posted another algorithm (in LISP, so as not to [quoted text clipped - 12 lines] > compiler is ironing out the tail recursive algorithm. I am not clever > enough to examine the byte code. I'm suspicious of the claim that a Java compiler could, in principle, convert a tail recursion into a loop. (That is, a Java compiler specificically. I'm aware of things like the Scheme standard requires compilers to do this.) The problem I'm thinking of is with exceptions. Consider the following class (which I'm not going to bother to test, or even compile; I trust you to deal with it): class SmallNumber { private int i; public SmallNumber(Integer i) { if ((i > 1000) || (i < 0)) { throw new RuntimeException("Out of bounds"); } this.i = i; } public SmallNumber add(SmallNumber n) { return tailAdd(n, this); } private SmallNumber addHelper(SmallNumber n, SmallNumber accumulator) { if (n.i == 0) { return accumulator; } return tailAdd(new SmallNumber(n.i - 1), new SmallNumber(accumulator.i + 1)); } } So, add() -- or, at least, addHelper() -- seems to be as tail recursive as they come. But what's the stack trace supposed to be when you trigger an Exception calling n.add(500,501)? If you object that add() isn't really tail recursive because it may have to change the call stack on an exceptional return (and so it doesn't meet the basic requirement that a tail recursive doesn't have to do anything but return a value), it to me that you've made the whole discussion nearly pointless; you've defined away the possibility of a tail call appearing anywhere. I can conceive of a situation where the compiler (maybe the JIT compiler) can prove that there's no possibility of throwing an Exception in a block of code, but that seems like quite a lot to ask to optimize a technique that would only occur to a very small percentage of Java programmers. SignatureMark Jeffcoat Austin, TX >>> No, not for the algorithm as posted. It's not tail recursive (it is, in >>> fact, doubly recursive). I posted another algorithm (in LISP, so as not [quoted text clipped - 18 lines] > (That is, a Java compiler specificically. I'm aware of things > like the Scheme standard requires compilers to do this.) The following article covers this in detail: http://www-128.ibm.com/developerworks/java/library/j-diag8.html Signaturesimon@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/ 'You cannot put "The Internet" into the Recycle Bin.' >> I'm suspicious of the claim that a Java compiler could, >> in principle, convert a tail recursion into a loop. [quoted text clipped - 4 lines] > The following article covers this in detail: > http://www-128.ibm.com/developerworks/java/library/j-diag8.html That article does try to address the subject; thanks for the pointer. Unfortunately, it just restates the problem, experiments on a few JVMs, and notes that IBM's JIT makes an optimization that may or may not be related to tail recursion. SignatureMark Jeffcoat Austin, TX > Now, I am curious. If I understand correctly, it is unreasonable to > expect my compiler to iron out the doubly recursive O(2^n) algorithm, > but it is reasonable to expect my compiler to iron out the tail > recursive O(n) algorithm. I would like to examine whether my compiler > does in fact iron out the tail recursive algorithm. No, it is not reasonable to /expect/ it to do that. That optimisation is at the option of the JIT implementation, and even if the JVM you are using is able to do tail-call elimination at all, there is nothing to guarantee that it will happen to do so in any particular case (it might, at least in theory, vary from run to run of the same program in the same JVM). So if your program depends on tail-call elimination for correctness (which usually includes completing in a reasonable time), then you have to do it yourself. > It was easy for me to verify that the compiler was not ironing out the > doubly recursive algorithm (because it is so painfully slow compared to > the iterative O(n) algorithm). But how would I verify that the > compiler is ironing out the tail recursive algorithm. Very difficult to do. The java->bytecode translator (javac) is unlikely to do that (even in the rare cases where it would be legal for it to do so), so reading bytecode is not going to help much. But getting details of what the JIT has done to generate (say) IA32 instructions from the bytecode is difficult (as far as I know the only way is to use JVMTA and a suitable disassembler). -- chris > Very difficult to do. The java->bytecode translator (javac) is unlikely to do > that (even in the rare cases where it would be legal for it to do so), so > reading bytecode is not going to help much. But getting details of what the > JIT has done to generate (say) IA32 instructions from the bytecode is difficult > (as far as I know the only way is to use JVMTA and a suitable disassembler). I'm interested in whether the Hotspot JIT compiler ever actually does this. As an added snafu, note that the compiler would need to check that no code inside the recursion ever tries to access the current runtime stack (e.g., by creating an exception object, performing a security check, etc.) before it performs that particular optimization. SignatureChris Smith > I'm interested in whether the Hotspot JIT compiler ever actually does > [tail recursion elimination] As far as I can tell from limited research, it does not. First off, I can't find any mention of the term "tail recursion" in the platform source (1.5 through 1.7). And "tail call" only seems to occur in irrelevant contexts. I didn't check all variations of that phrase, though. Secondly, even with as trivial a case as I can concoct without letting the optimiser remove the method altogether, it is possible blow the stack at runtime. I'll attach my test code. Presumably the JVM doesn't consider itself under a responsibility to simulate the effects of running out of stack space, so I assume that it didn't actually remove the tail-call. Lastly, I had a play with the JVMTI stuff to monitor the generated IA32 code. I'll attatch the result of disassembling that too in case anyone fancies trying to make sense of it. My assembler skills are weak, but as far as I can tell from some rather stange code, the JIT has inlined one layer of recusive calls, but done no other recursion elmination. There are no backward jumps, so no looping has been introduced. I'm guessing that the call to _resolve_static_call_Java is checking code initially, and that it and the preceeding no-ops will be overwritten with a direct recursive call to recurse() after the checks have passed (but that is /only/ a guess !) -- chris =============================== public class Test { private static class BoolHolder { boolean value; } public static void main(String[] args) { BoolHolder bottom; System.out.println("warming JIT..."); bottom = new BoolHolder(); for (int i = 0; i < 10000; i++) recurse(1000, bottom); System.out.println("running..."); bottom = new BoolHolder(); recurse(1000 * 1000 * 1000, bottom); System.out.println(bottom.value); } private static void recurse(int n, BoolHolder bottom) { if (n <= 0) { bottom.value = true; return; } recurse(n-1, bottom); } } =========================================== Disassembled IA32 code for recurse() 0xB05FE0 mov [dword esp+0xFFFFD000],eax 0xB05FE7 sub esp,0xC 0xB05FED test ecx,ecx 0xB05FEF jle short 0xB0601A ; recurse+0x3A 0xB05FF1 mov eax,ecx 0xB05FF3 dec eax 0xB05FF4 test eax,eax 0xB05FF6 jle short 0xB06014 ; recurse+0x34 0xB05FF8 mov ebx,ecx 0xB05FFA add ebx,0xFFFFFFFE 0xB05FFD test ebx,ebx 0xB05FFF jle short 0xB0600E ; recurse+0x2E 0xB06001 add ecx,0xFFFFFFFD 0xB06004 nop 0xB06005 nop 0xB06006 nop 0xB06007 call _resolve_static_call_Java 0xB0600C jmp short 0xB0601E ; recurse+0x3E 0xB0600E mov [byte edx+0x8],0x1 0xB06012 jmp short 0xB0601E ; recurse+0x3E 0xB06014 mov [byte edx+0x8],0x1 0xB06018 jmp short 0xB0601E ; recurse+0x3E 0xB0601A mov [byte edx+0x8],0x1 0xB0601E add esp,0xC 0xB06021 test [dword 0x390000],eax 0xB06027 retn > Lastly, I had a play with the JVMTI stuff to monitor the generated IA32 code. > I'll attatch the result of disassembling that too in case anyone fancies trying [quoted text clipped - 5 lines] > preceeding no-ops will be overwritten with a direct recursive call to recurse() > after the checks have passed (but that is /only/ a guess !) Yes, very nice. Looks like you are right about everything. _resolve_static_call_Java makes perfect sense for handling static initialization requirements without a long-term performance penalty. (In this case, though, one could imagine the compiler being smart enough to recognize that static initialization can never be triggered by a static method calling itself; or indeed anything in the same class.) Definitely no tail call elimination. Plenty of other places, as well, where optimizations are obvious. Is this code before your warm-up loop, or after? I'm assuming before, since the static call would be resolved by then if it were after. It would be interesting to see what else happens; maybe I'll poke around. SignatureChris Smith > (In this case, though, one could imagine the compiler being smart enough > to recognize that static initialization can never be triggered by a > static method calling itself; or indeed anything in the same class.) Probably just not worth the effort. It won't make any real difference unless the method is executed a lot, but if it's executed a lot then it won't make any real difference ;-) > Is this code before your warm-up loop, or after? I'm assuming before, > since the static call would be resolved by then if it were after. It > would be interesting to see what else happens; maybe I'll poke around. JVMTI seems to be telling me about this code sometime around first call to recurse() (I say "sometime" because I don't know how often it has been executed in the interpreter before that). I'm assuming that JVMTI only tells me about whole-method generation, not about "simple" runtime patching. In this case it doesn't tell me about any subsequent patches to recurse(). I /have/ seen it generate several different versions of a method during a run, but not in this case. -- chris To understand recusrion, you must first understand recursion > Come now. Everyone knows that the best way is: > [quoted text clipped - 10 lines] > Nourished the land on a fallacy of rational virtue." > -- Charles Williams. "Taliessin through Logres: Prelude" > To understand recusrion, you must first understand recursion >> Come now. Everyone knows that the best way is: [quoted text clipped - 11 lines] >> Nourished the land on a fallacy of rational virtue." >> -- Charles Williams. "Taliessin through Logres: Prelude" Teachers throughout the whole world use this one to explain recursion :D >> To understand recusrion, you must first understand recursion >> [quoted text clipped - 8 lines] > > Teachers throughout the whole world use this one to explain recursion :D That has always puzzled me, because (as John Kennedy's code above shows) the problem is poorly suited to a recursive solution. The other common example is computing factorials, and recursion is a poor choice of method for that one, too. Is it any wonder that understanding of recursion proves difficult, when the teachers offer such bad examples? SignatureEric Sosman esosman@acm-dot-org.invalid One of the better examples given to me in school were the recursive solutions to the various sort methods bubble sort, breadth first, etc. The mathematical ones were just to get us started I supposed. But it works. > >> To understand recusrion, you must first understand recursion > [quoted text clipped - 23 lines] > Eric Sosman > esos...@acm-dot-org.invalid >>> To understand recusrion, you must first understand recursion >>> [quoted text clipped - 15 lines] > understanding of recursion proves difficult, when the teachers > offer such bad examples? On the contrary, it is a beautifully simple piece of recursion. In a proper grown up language (defun fibonacci (n) (assert (integerp n) nil "N must be an integer") (cond ((<= n 1) 1) (t (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))) You cannot come up with a non-recursive definition of the Fibonacci series which is simpler or more expressive than that. Computational efficiency? Pah! Signaturesimon@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/ my other car is #<Subr-Car: #5d480> ;; This joke is not funny in emacs. >> That has always puzzled me, because (as John Kennedy's code >> above shows) the problem is poorly suited to a recursive solution. [quoted text clipped - 17 lines] > which is simpler or more expressive than that. Computational efficiency? > Pah! I prefer the Haskell/Miranda formulation (not non-recursive though): fib 0 = 0 fib 1 = 1 fib (n + 2) = fib (n) + fib (n + 1) I found this page of benchmarks for Fibonacci numbers in different languages using different algorithms: http://www.cubbi.org/serious/fibonacci.html It seems that all the links to source code are broken, so the OP is still going to have to write their own code. Dan. SignatureDaniel Dyer http://www.uncommons.org > I prefer the Haskell/Miranda formulation (not non-recursive though): > > fib 0 = 0 > fib 1 = 1 > fib (n + 2) = fib (n) + fib (n + 1) The recursive method is not necessarily slow. It depends upon quality of implementation of the language system. For example, I found something like this on the web: #include <ostream> template<unsigned long i> struct Fibonacci { static const unsigned long result = Fibonacci<i-1>::result+Fibonacci<i-2>::result; }; template<> struct Fibonacci<0> { static const unsigned long result = 0; }; template<> struct Fibonacci<1> { static const unsigned long result = 1; }; template<unsigned long i> struct Loop { static void run() { Loop<i-1>::run(); std::cout<<Fibonacci<i>::result<<std::endl; } }; template<> struct Loop<0> { static void run() { } }; int main() { Loop<100>::run(); } In fact ISO C++ only allows seven levels of template nesting, IIRC. My compiler bottles after Loop<64>. The evaluation is done at compile time, so the run time performance should be excellent. However, the compile time performance is non too shabby either. You would expect template instantiations to be memoised (might indeed be mandated). So we have good compile time performance, excellend run time performance and only need to use the naive algorithm. Pity the syntax, the error messages, the lack of bounds checking and the rest of the language suck. :) Tom Hawtin >The evaluation is done at compile time, The evaluation might be done at compile time, even when templates are not used: Some C++-compilers can evaluate function calls and loops at compile time (for gcc the options are »-O3« and »-funroll_loops«). By the rule that a program only needs to behave as-if the language semantics would be applied, a compiler also is free to transform a recursive wording of a programmer into an iterative implementation (tail-call optimization is a step into this direction), although this is not always possible. However, I regard source code as a design and specification artefact and expect the compiler to do the actual implementation. Thus, recursive notation in the source code does not need to mean actual recursive execution to me. >> The evaluation is done at compile time, > > The evaluation might be done at compile time, even when > templates are not used: Some C++-compilers can evaluate > function calls and loops at compile time (for gcc the options > are »-O3« and »-funroll_loops«). I don't think loop unrolling quite fit with the compile time evaluation described here. Arne >I don't think loop unrolling quite fit with the compile time >evaluation described here. public class Main { static int alpha( final int m ) { int i = 3; for( int j = 0; j < m; ++j )i <<= j; return i; } public static void main ( final java.lang.String[] args ) { java.lang.System.out.println( alpha( 3 )); }} gcj -O3 -funroll-loops -S Main.java (...) movl __ZN4java4lang6System3outE, %eax movl $24, %ecx movl (%eax), %edx movl %ecx, 4(%esp) movl %eax, (%esp) call *100(%edx) (...) This is equivalent to: public class Main { public static void main ( final java.lang.String[] args ) { java.lang.System.out.println( 24 ); }} >> I don't think loop unrolling quite fit with the compile time >> evaluation described here. > > public class Main ... > gcj -O3 -funroll-loops -S Main.java ... > This is equivalent to: > > public class Main ... And ? Interesting example of compiler optimization. Still completely unrelated to the compile time evaluation dons via templates that started this subthread. Arne >Still completely unrelated to the compile time >evaluation dons via templates that started this >subthread. The relation already has been explained to you. The example was given in order to show that »The evaluation might be done at compile time, even when templates are not used« >> Still completely unrelated to the compile time >> evaluation dons via templates that started this >> subthread. > > The relation already has been explained to you. No - actually it was not. > The example was given in order to show that > > »The evaluation might be done at compile time, > even when templates are not used« Your example shows that compilers can do code optimization. Which is something rather well known. The example starting this subthread was about implementing a recursive algorithm using C++ templates. The only common I can see is that a compiler does something. Which is not enough to make it relevant in any way. Arne > On the contrary, it is a beautifully simple piece of recursion. In a > proper grown up language If one is to ignore minor details of syntax, then I don't think the recursive expression in Java is one whit less elegant than the Lisp version. If we /are/ to take such details into account then they both suck (IMO). Worse, they both hide the underlying recurrence relation. Daniel's formulation shows how a real functional programming language can expose the stucture transparently. But the OP might prefer a formulation less taxing to the beginner's brain -- so I'll append one. BTW; for anyone interested. I should probably have used a table lookup -- even though that means that there has to be code to populate the table. Javac converts the switch statement into the obvious tableswitch bytecode. But then, using JSK 1.5.0 on this 32-bit Intel box, the java -client JITer compiles that into a sequence of 92 cmp/je instuction pairs, comparing n against 1..92 in order ! Java -server is doing something much weirder, and I haven't yet figured it out (my IA32 assember skillz are sub-embrionic). It produces an almost equally long sequence of test-and-jump pairs, plus some arithmetic, but the values are less than obvious -- I'm guessing it's some sort of hashing scheme. Neither of them use a jump table, which I would consider to the be obvious technique for a big switch like this. I know that the unguessable indirection involved in an indirect jump is very pipeline unfriendly, but compared with 50-odd compare-and-branches, which is likely to include an unpredicted jump anyway ?!? -- chris ========= Fibonacci.java ========= public class Fibonacci { public static long value(int n) { // <shrug/> switch (n) { case 1: return 1L; case 2: return 1L; case 3: return 2L; case 4: return 3L; case 5: return 5L; case 6: return 8L; case 7: return 13L; case 8: return 21L; case 9: return 34L; case 10: return 55L; case 11: return 89L; case 12: return 144L; case 13: return 233L; case 14: return 377L; case 15: return 610L; case 16: return 987L; case 17: return 1597L; case 18: return 2584L; case 19: return 4181L; case 20: return 6765L; case 21: return 10946L; case 22: return 17711L; case 23: return 28657L; case 24: return 46368L; case 25: return 75025L; case 26: return 121393L; case 27: return 196418L; case 28: return 317811L; case 29: return 514229L; case 30: return 832040L; case 31: return 1346269L; case 32: return 2178309L; case 33: return 3524578L; case 34: return 5702887L; case 35: return 9227465L; case 36: return 14930352L; case 37: return 24157817L; case 38: return 39088169L; case 39: return 63245986L; case 40: return 102334155L; case 41: return 165580141L; case 42: return 267914296L; case 43: return 433494437L; case 44: return 701408733L; case 45: return 1134903170L; case 46: return 1836311903L; case 47: return 2971215073L; case 48: return 4807526976L; case 49: return 7778742049L; case 50: return 12586269025L; case 51: return 20365011074L; case 52: return 32951280099L; case 53: return 53316291173L; case 54: return 86267571272L; case 55: return 139583862445L; case 56: return 225851433717L; case 57: return 365435296162L; case 58: return 591286729879L; case 59: return 956722026041L; case 60: return 1548008755920L; case 61: return 2504730781961L; case 62: return 4052739537881L; case 63: return 6557470319842L; case 64: return 10610209857723L; case 65: return 17167680177565L; case 66: return 27777890035288L; case 67: return 44945570212853L; case 68: return 72723460248141L; case 69: return 117669030460994L; case 70: return 190392490709135L; case 71: return 308061521170129L; case 72: return 498454011879264L; case 73: return 806515533049393L; case 74: return 1304969544928657L; case 75: return 2111485077978050L; case 76: return 3416454622906707L; case 77: return 5527939700884757L; case 78: return 8944394323791464L; case 79: return 14472334024676221L; case 80: return 23416728348467685L; case 81: return 37889062373143906L; case 82: return 61305790721611591L; case 83: return 99194853094755497L; case 84: return 160500643816367088L; case 85: return 259695496911122585L; case 86: return 420196140727489673L; case 87: return 679891637638612258L; case 88: return 1100087778366101931L; case 89: return 1779979416004714189L; case 90: return 2880067194370816120L; case 91: return 4660046610375530309L; case 92: return 7540113804746346429L; } if (n < 1) throw new IllegalArgumentException("N must be >= 1"); else throw new IllegalArgumentException("answer cannot be expressed as a long"); } } ================== Hey Furious George, Your mail was really hilarious. Thanks man. I had knowingly coded the program like that - so that Sirusha puts some original effort. HINT to OP: Using a BigDecimal would solve the issue. Cheers, Jan The King > > To understand recusrion, you must first understand recursion > >> Come now. Everyone knows that the best way is: [quoted text clipped - 11 lines] > >> Nourished the land on a fallacy of rational virtue." > >> -- Charles Williams. "Taliessin through Logres: Prelude"Teachers throughout the whole world use this one to explain recursion :D > Hey Furious George, > [quoted text clipped - 4 lines] > > HINT to OP: Using a BigDecimal would solve the issue. And if you want to compute f(100) in less than 5 minutes, consider how you might use a Map to improve efficiency. > > Hey Furious George, > > [quoted text clipped - 7 lines] > And if you want to compute f(100) in less than 5 minutes, consider how you > might use a Map to improve efficiency. Don't you think memoization is too advanced a topic for the OP? >>Hey Furious George, >> [quoted text clipped - 7 lines] > And if you want to compute f(100) in less than 5 minutes, consider how you > might use a Map to improve efficiency. "Five minutes?" You must have a Really Fast Machine! Just for fun I tried the recursive solution using BigInteger on my 3GHz Pentium IV, which took not quite one minute to compute f(42). At that rate, f(100) would take about two and a quarter million years. The obvious iterative solution, again using BigInteger, computed f(100) in less than one millisecond. I didn't test the closed-form non-iterative solution, because BigInteger doesn't mix well with powers of irrational numbers. SignatureEric Sosman esosman@acm-dot-org.invalid Hi Karl, When using a iterative solution (referring to code posted by me earlier) I am wondering as to how a map will improve efficiency? > > Hey Furious George, > > [quoted text clipped - 7 lines] > And if you want to compute f(100) in less than 5 minutes, consider how you > might use a Map to improve efficiency. > Hi Karl, > > When using a iterative solution (referring to code posted by me > earlier) I am wondering as to how a map will improve efficiency? My apologies to everyone for posting a solution to a homework assignment. I assume by now the OP has either submitted his solution or received zero credit. I adapted this implementation from an example written in Python, which I Googled using the query string "fibonacci algorithm". Just basic Internet research. This implementation can generate the first 1000 fibonacci numbers in less than 5 seconds. The recursion stops as soon as a map lookup yields a result. I verified the first 20 numbers were correct, and then spot checked f(n)/f(n - 1) = 1.618 (approx) at a couple of places within the dynamic range of Windows Calculator, with expected results. This might not be the optimum implementation, but I think it is a decent one. package fibonacci; import java.math.BigInteger; import java.util.HashMap; import java.util.Map; public class Main { static Map<Integer, BigInteger> map = new HashMap<Integer, BigInteger>(); static { map.put(0, BigInteger.ZERO); map.put(1, BigInteger.ONE); } public static void main(String[] args) { for(int nn = 0; nn <= 1000; nn++) { System.out.println("F(" + nn + ") = " + fibonacci(nn)); } } static BigInteger fibonacci(int nn) { BigInteger fn = map.get(nn); if (fn == null) { fn = fibonacci(nn - 1).add(fibonacci(nn - 2)); map.put(nn, fn); } return fn; } } > > Hi Karl, > > [quoted text clipped - 9 lines] > This implementation can generate the first 1000 fibonacci numbers in less > than 5 seconds. Really? > This might not be the > optimum implementation, but I think it is a decent one. Way too fat, as most java programs. How about the following algorithm? (You may want to convert it to real Java) bigint fib(bigint n) { if (n<2) then return 1; bigint f1 = 1, f2 = 1, i = 2, f3; while (i < n) { i++; f3 = f1; f1 = f2; f2 += f3; } return f1+f2; } This function should compute the first 1000 numbers in no time. Even the first 100000. >> > Hi Karl, >> > [quoted text clipped - 12 lines] > > Really? Yes. including all of the console I/O, four seconds and change on my rather old laptop. >> This might not be the >> optimum implementation, but I think it is a decent one. > > Way too fat, as most java programs. Depending on what your features and reqirements are. I was adapting the original algorithm, which is modeled after the actual mathematical definition, as classically written, but with the enhancement not to have to recurse to down to zero every time a new value is needed. One could use an array of big integers, but an array does not grow dynamically (as a map can) if someone suddenly requires a larger F(n). > How about the following algorithm? (You may want to convert it to real > Java) [quoted text clipped - 10 lines] > This function should compute the first 1000 numbers in no time. Even > the first 100000. No time? That *is* impressive. Still, it needs to loop n times for any arbitrary value of n, which is approximately what the algorithm I presented has to do if it has never seen n that large before. I agree there is the issue with storage of all n values in a map with my approach, however, once calculated, the value never need be calculated again, just looked up. In an application where the algorithm is used more than once, there is no iteration at all unless n > any previous n. All engineering involves compromise, isn't it? BTW, Isn't F(0) = 0? >>>Hi Karl, >>> [quoted text clipped - 22 lines] > bigint fib(bigint n) { > if (n<2) then return 1; if (n < 2) return n <= 0 ? 0 : 1; > bigint f1 = 1, f2 = 1, i = 2, f3; > while (i < n) { > i++; f3 = f1; f1 = f2; f2 += f3; > } > return f1+f2; I believe you're off by one here: fib(2) should return 1, not 2, and fib(3) should return 2, not 3, and so on. > } > > This function should compute the first 1000 numbers in no time. Even > the first 100000. fib(100000) is a 69424-bit number, and adding numbers of that size is likely to take more than "no time." Still, the iterative solution beats the pants off recursion. SignatureEric Sosman esosman@acm-dot-org.invalid > fib(100000) is a 69424-bit number, and adding numbers of > that size is likely to take more than "no time." > > Still, the iterative solution beats the pants off recursion. On my machine the iterative form takes ~ 0.024 seconds for fib(10,000). The memoised recursive form takes around 0.09 seconds. Not really a trouser-ripping difference in speed. What matters more is that the recursive form blows the default stack at around fib(8,000), and the default heap somewhere before fib(40,000). I assume that the increased GC load of the memoised version explains the difference in speeds -- which otherwise seems implausibly great (the BigInteger adds should /swamp/ the array accesses and null-tests). -- chris I wrote: > On my machine the iterative form takes ~ 0.024 seconds for fib(10,000). > The memoised recursive form takes around 0.09 seconds. Forgot to mention that the iterative form does fib(100,000) in about 2 seconds. I think the memoised recursive version would require more heap space (~500MB) than I can give it on this machine. -- chris Chris Uppal wrote On 11/07/06 10:47,: > I wrote: > [quoted text clipped - 4 lines] > I think the memoised recursive version would require more heap space (~500MB) > than I can give it on this machine. By "memoized" I guess you mean caching the result of an already-computed fib(), and caching ~100000 BigInteger results (many of them rather large) would indeed chew up a lot of RAM. So we don our thinking caps, and we note that a cached value will be used at most twice (in any one fib(n) computation), and never again: the cache entries for greater argument values will "intercept" the recursion before it gets down to low numbers for a third time. That is, only a small part of the cache is active, and the rest can be discarded after just a few references. So we decide to implement a cache that discards entries when they're no longer needed. A little thought convinces us that the cache never needs more than two entries: one for fib(k-1) and one for fib(k-2); once fib(k) is known, fib(k-2) won't be needed again and fib(k) can supplant it in the cache. The next thing we notice (we're very observant, we are) is that the searches in this two-element cache are very simple. They are always successful except for the very first time, and in fact we always know what the search key will be: k-1 for one term and k-2 for the other. Since those are the only two entries in the cache, we can actually eliminate the keys and do no searching at all. So: What's the simplest data structure you can think of that caches exactly two values and retrieves them in a purely mechanical pattern without searching? BigInteger fSubKMinus1; BigInteger fSubKMinus2; ... and lo! "Memoization" transforms to iteration! SignatureEric.Sosman@sun.com > ... and lo! "Memoization" transforms to iteration! That's a nice line of reasoning. "And for my next trick..." <drum roll/> "Ackermann's !" ;-) -- chris [...] >> bigint fib(bigint n) { >> if (n<2) then return 1; > > if (n < 2) > return n <= 0 ? 0 : 1; if (n < 2) return n >= 0 ? n : n % 2 == 0 ? -fib(-n) : fin(-n); >> bigint f1 = 1, f2 = 1, i = 2, f3; >> while (i < n) { [quoted text clipped - 4 lines] > I believe you're off by one here: fib(2) should return 1, > not 2, and fib(3) should return 2, not 3, and so on. return f2; >> } >> [quoted text clipped - 3 lines] > fib(100000) is a 69424-bit number, and adding numbers of > that size is likely to take more than "no time." My PM 1,8G needs 1,448 sec. to compute that. > Still, the iterative solution beats the pants off recursion. Yup. So then, in comparison with definitely more than "two and a quarter million years" iterative result could be seen as "no time", couldn't it? :) piotr > Yup. So then, in comparison with definitely more than "two and a > quarter million years" iterative result could be seen as "no time", > couldn't it? :) <grin/> -- chris P.S. Piotr, I've tried to reply to your email, but my replies have bounced. Do you have a different email address I could use ? (Send it privately if you don't want to mention it here). Or if you can translate this rejection message from the bounced response: 550 Brak rekordu SPF/MX nadawcy lub bledna autoryzacja SMTP! then maybe I could get my ISP's support dept to look at it. -- c > P.S. Piotr, I've tried to reply to your email, but my replies have bounced. Hmmm... Strange... > Do you have a different email address I could use ? (Send it privately if you > don't want to mention it here). Try this one: pikob (at) op (dot) pl > Or if you can translate this rejection > message from the bounced response: > 550 Brak rekordu SPF/MX nadawcy lub bledna autoryzacja SMTP! 550 Missing SPF/MX record of the sender or invalid SMTP authorization! > then maybe I could get my ISP's support dept to look at it. If you could, it would be nice. I'll send it also to my e-mail account SP's support. Thank you. > -- c piotr > I believe you're off by one here: fib(2) should return 1, > not 2, and fib(3) should return 2, not 3, and so on. Ok, just initialize f1 to the desired result of fib(0), then. > fib(100000) is a 69424-bit number, and adding numbers of > that size is likely to take more than "no time." O(n) is nothing compared to O(n?) :) > > I believe you're off by one here: fib(2) should return 1, > > not 2, and fib(3) should return 2, not 3, and so on. [quoted text clipped - 5 lines] > > O(n) is nothing compared to O(n²) :) There is an O(logn) solution, which is even less than O(n) > O(n) is nothing compared to O(n²) :) But the algorithm that was being discussed was not O(n²) either... :-P I think this is better static long[][] getMatrix(long n){ long [][]r={{1,0},{0,1}}; long [][]y={{0,1},{1,1}}; long a,b,c,d; while(n>0){ if(n%2==1) { a=r[0][0]*y[0][0]+r[0][1]*y[1][0]; b=r[0][0]*y[0][1]+r[0][1]*y[1][1]; c=r[1][0]*y[0][0]+r[1][1]*y[1][0]; d=r[1][0]*y[0][1]+r[1][1]*y[1][1]; r[0][0]=a; r[0][1]=b; r[1][0]=c; r[1][1]=d; } a=y[0][0]*y[0][0]+y[0][1]*y[1][0]; b=y[0][0]*y[0][1]+y[0][1]*y[1][1]; c=y[1][0]*y[0][0]+y[1][1]*y[1][0]; d=y[1][0]*y[0][1]+y[1][1]*y[1][1]; y[0][0]=a; y[0][1]=b; y[1][0]=c; y[1][1]=d; n>>>=1; } return r; } static long fibo(long i){ if(i<1)throw new IllegalArgumentException("Error Input"); if(i==1L)return 1; if(i==2L)return 1; long[][] temp=getMatrix(i-2); return temp[1][0]+temp[1][1]; } > > > Hi Karl, > [quoted text clipped - 26 lines] > }This function should compute the first 1000 numbers in no time. Even > the first 100000.- Hide quoted text -- Show quoted text - ÈÊÕßÎ޵Рwrote: > a=y[0][0]*y[0][0]+y[0][1]*y[1][0]; > b=y[0][0]*y[0][1]+y[0][1]*y[1][1]; > c=y[1][0]*y[0][0]+y[1][1]*y[1][0]; > d=y[1][0]*y[0][1]+y[1][1]*y[1][1]; Very pretty ! Not entirely sane, perhaps, but certainly pretty ;-) -- chris > When using a iterative solution (referring to code posted by me > earlier) I am wondering as to how a map will improve efficiency? It won't. What the map (or use an array instead) does is allow you to use the same kind of elegant code as in the recursive formulation, but with an efficiency which approaches that of the iterative one. -- chris >> When using a iterative solution (referring to code posted by me >> earlier) I am wondering as to how a map will improve efficiency? > > It won't. What the map (or use an array instead) does is allow you to > use the same kind of elegant code as in the recursive formulation, but > with an efficiency which approaches that of the iterative one. It will on second and subsequent invocations of the computation, if you cache partial results. Iterating up you can start with the last partial results posted, even if they are lower than the value you're looking for; recursing down, obviously, they help even more. Signaturesimon@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/ ;; not so much a refugee from reality, more a bogus ;; asylum seeker > > > When using a iterative solution (referring to code posted by me > > > earlier) I am wondering as to how a map will improve efficiency? [quoted text clipped - 4 lines] > > It will on second and subsequent invocations of the computation, Yes, it will if you use a long lived cache. I was (unconsciously) only thinking of the case where the cache is allocated and used only for one top-level computation, and then discarded. "Transient memoisation" as it were... -- chris Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.