Re: Fabonicseries Program required
"Ingo Menger" <quetzalcotl@consultant.com> wrote in message
news:1162888746.912086.100030@h54g2000cwb.googlegroups.com...
Karl Uppiano wrote:
"JanTheKing" <janesh.s@gmail.com> wrote in message
news:1162795421.365369.31640@e3g2000cwe.googlegroups.com...
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.
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)
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.
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?