Re: Fabonicseries Program required

"JanTheKing" <janesh.s@gmail.com> wrote in message
news:1162795421.365369.31640@e3g2000cwe.googlegroups.com...


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;
    }
}