Java Fibonacci Sequence fast method

Question

I need a task about finding Fibonacci Sequence for my independent project in Java. Here are methods for find.

private static long getFibonacci(int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return (getFibonacci(n-1)+getFibonacci(n-2));
    }
}

private static long getFibonacciSum(int n) {
    long result = 0;

    while(n >= 0) {
        result += getFibonacci(n);
        n--;
    }
    return result;
}

private static boolean isInFibonacci(long n) {
    long a = 0, b = 1, c = 0;

    while (c < n) {
        c = a + b;
        a = b;
        b = c;
    }

    return c == n;
}

Here is main method:

    long key = getFibonacciSum(n);
    System.out.println("Sum of all Fibonacci Numbers until Fibonacci[n]: "+key);

    System.out.println(getFibonacci(n)+" is Fibonacci[n]");

    System.out.println("Is n2 in Fibonacci Sequence ?: "+isInFibonacci(n2));

Codes are completely done and working. But if the n or n2 will be more than normal (50th numbers in Fib. Seq.) ? Codes will be runout. Are there any suggestions ?

Answer 1

There is a way to calculate Fibonacci numbers instantaneously by using Binet's Formula

Algorithm:

function fib(n):
   root5 = squareroot(5)
   gr = (1 + root5) / 2
   igr = 1 - gr
   value = (power(gr, n) - power(igr, n)) / root5

   // round it to the closest integer since floating 
   // point arithmetic cannot be trusted to give
   // perfect integer answers. 
   return floor(value + 0.5) 

Once you do this, you need to be aware of the programming language you're using and how it behaves. This will probably return a floating point decimal type, whereas integers are probably desired.

The complexity of this solution is O(1).