Fibonacci above 100000

Question

I searched a lot of examples of fibonacci progarms. All of them dont't calculate large numbers. My program calculte Fibonacci(10000). My task is Fibonacci(100000) and Fibonacci(200000). Have you any idea, maybe it can be thread?

    import java.math.*;
    import java.io.*;
    public class FastFibonacci
    {
    private static BigInteger[] answers; 

        private static BigInteger one;
    private static BigInteger zero;

    private static BufferedReader stdin = new BufferedReader( new InputStreamReader( System.in ) );

    public static BigInteger fastFibonacci(int n)
    {
        if((n == 1) || (n == 2))
                        return answers[0];

                if(answers[n-1].compareTo(zero) != 0)
                        return answers[n-1];

        if(answers[n-2].compareTo(zero) == 0)
                    answers[n-2] = fastFibonacci(n-1);

        if(answers[n-3].compareTo(zero) == 0)
                    answers[n-3] = fastFibonacci(n-2);

                return answers[n-2].add(answers[n-3]);
    }

        public static void main(String[] args)
        {

                int n;
        long time, newTime;
        BigInteger answer;

                System.out.println("Type a positive integer." );
                try{
                       String input = stdin.readLine();
                        n = Integer.parseInt( input );

            zero = new BigInteger("0");
            one = new BigInteger("1");

            answers = new BigInteger[n];
            answers[0] = new BigInteger("1");
            answers[1] = new BigInteger("1");
            for(int i = 2; i < n; i++)
                answers[i] = new BigInteger("0");

                        time = System.currentTimeMillis();
                        answer = fastFibonacci(n);
                        newTime = System.currentTimeMillis();

                        System.out.println("The "+n+"th Fibonacci number is "+ answer);
                        System.out.println("It took " + (newTime-time) + " milliseconds to compute it.");

                }
                catch(java.io.IOException e)
                {
                        System.out.println(e);
                }



    }

}

Thanks for all answers.

What prevents you from calling this function with a larger number? What is the actual problem? — David, Dec 02 '15 at 20:24
I have an error Exception in thread "main" java.lang.StackOverflowError when put 100000 — vika, Dec 02 '15 at 20:25
Are you sure you're hitting your base case when calling fastFibonacci recursively? — lintmouse, Dec 02 '15 at 20:26
Whenever I see a function/method named `fastSomething()` I shudder :p But anyway, in your situation, it looks like you want memoization... Or a better way to compute results from the Fibonacci suite — fge, Dec 02 '15 at 20:28
try the iterative method instead of the recursive one which is the cause of your stack overflow error — Laabidi Raissi, Dec 02 '15 at 20:29

score 3 · Answer 1 · answered Dec 02 '15 at 20:29

With so many recursive calls, the call stack will overflow (not to mention it would be awfully slow). Use an iterative algorithm instead, for example:

private BigInteger fib(int n) {
    BigInteger prev = BigInteger.ONE;
    BigInteger prevprev = BigInteger.ONE;
    BigInteger num = BigInteger.ONE;
    for (int i = 2; i < n; ++i) {
        num = prev.add(prevprev);
        prevprev = prev;
        prev = num;
    }
    return num;
}

Fibonacci above 100000

1 Answers1