burakkaanerce burakkaanerce - 2 months ago 17
Java Question

Java Fibonacci Sequence fast method

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

Yes, one improvement you can do is to getFibonacciSum(): instead of calling again and again to isInFibonacci which re-calculates everything from scratch, you can do the exact same thing that isInFibonacci is doing and get the sum in one pass, something like:

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

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