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

Using a traditional Recursion solution: memory is not a concern, but it takes a significant amount of time to obtain fib(1000000), for instance.

With the following solution: we may be running out of memory for very big inputs, such as fib(99999*(10^999999)), but it is much faster than the traditional solution. The solution is based on the use of a map and some mathematical formulas (source: https://www.nayuki.io/page/fast-fibonacci-algorithms).

Math formulas:

F(2k) = F(k)[2F(k+1)−F(k)]

F(2k+1) = F(k+1)^2+F(k)^2

Solution:

public BigInteger fib(BigInteger n) {
    if (n.equals(BigInteger.ZERO))
        return BigInteger.ZERO;
    if (n.equals(BigInteger.ONE) || n.equals(BigInteger.valueOf(2)))
        return BigInteger.ONE;
    
    BigInteger index = n;
    
    //we could have 2 Lists instead of a map
    Map<BigInteger,BigInteger> termsToCalculate = new TreeMap<BigInteger,BigInteger>();
    
    //add every index needed to calculate  index n
    populateMapWhitTerms(termsToCalculate, index);
    
    termsToCalculate.put(n,null); //finally add n to map
    
    Iterator<Map.Entry<BigInteger, BigInteger>> it = termsToCalculate.entrySet().iterator();//it 
    it.next(); //it = key number 1, contains fib(1);
    it.next(); //it = key number 2, contains fib(2);
    
    //map is ordered
    while (it.hasNext()) {
        Map.Entry<BigInteger, BigInteger> pair = (Entry<BigInteger, BigInteger>)it.next();//first it = key number 3
        index = (BigInteger) pair.getKey();
        
        if(index.remainder(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            //index is divisible by 2
            //F(2k) = F(k)[2F(k+1)−F(k)]
            pair.setValue(termsToCalculate.get(index.divide(BigInteger.valueOf(2))).multiply(
                    (((BigInteger.valueOf(2)).multiply(
                            termsToCalculate.get(index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE)))).subtract(
                                    termsToCalculate.get(index.divide(BigInteger.valueOf(2)))))));
        }
        else {
            //index is odd
            //F(2k+1) = F(k+1)^2+F(k)^2
            pair.setValue((termsToCalculate.get(index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE)).multiply(
                    termsToCalculate.get(index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE)))).add(
                            (termsToCalculate.get(index.divide(BigInteger.valueOf(2))).multiply(
                            termsToCalculate.get(index.divide(BigInteger.valueOf(2))))))
                    );
        }
    }
    
    // fib(n) was calculated in the while loop
    return termsToCalculate.get(n);
}

private void populateMapWhitTerms(Map<BigInteger, BigInteger> termsToCalculate, BigInteger index) {
    if (index.equals(BigInteger.ONE)) { //stop
        termsToCalculate.put(BigInteger.ONE, BigInteger.ONE);
        return;
        
    } else if(index.equals(BigInteger.valueOf(2))){
        termsToCalculate.put(BigInteger.valueOf(2), BigInteger.ONE);
        return;
        
    } else if(index.remainder(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
        // index is divisible by 2
        // FORMUMA: F(2k) = F(k)[2F(k+1)−F(k)]
                    
        // add F(k) key to termsToCalculate (the key is replaced if it is already there, we are working with a map here)
        termsToCalculate.put(index.divide(BigInteger.valueOf(2)), null);
        populateMapWhitTerms(termsToCalculate, index.divide(BigInteger.valueOf(2)));

        // add F(k+1) to termsToCalculate
        termsToCalculate.put(index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE), null);
        populateMapWhitTerms(termsToCalculate, index.divide(BigInteger.valueOf(2)).add(BigInteger.ONE));
        
    } else {
        // index is odd
        // FORMULA: F(2k+1) = F(k+1)^2+F(k)^2

        // add F(k+1) to termsToCalculate
        termsToCalculate.put(((index.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)).add(BigInteger.ONE)),null);
        populateMapWhitTerms(termsToCalculate,((index.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)).add(BigInteger.ONE)));

        // add F(k) to termsToCalculate
        termsToCalculate.put((index.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)), null);
        populateMapWhitTerms(termsToCalculate, (index.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)));
    }
    
}

Answer 2

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 int getFibonacciSum(int n) {
    int a = 0, b = 1, c = 0, sum = 0;

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

Answer 3

I have checked all solutions and for me, the quickest one is to use streams and this code could be easily modified to collect all Fibonacci numbers.

 public static Long fibonaciN(long n){
    return Stream.iterate(new long[]{0, 1}, a -> new long[]{a[1], a[0] + a[1]})
            .limit(n)
            .map(a->a[0])
            .max(Long::compareTo)
            .orElseThrow();
}

Answer 4

public static long getFib(final int index) {
        long a=0,b=0,total=0;
        for(int i=0;i<= index;i++) {
                if(i==0) {
                     a=0;
                     total=a+b;
                 }else if(i==1) {
                     b=1;
                     total=a+b;
                 }

            else if(i%2==0) {
                total = a+b;
                a=total;                
            }else {
                total = a+b;
                b=total;
            }

        }
        return total;
    }

Answer 5

50 or just below 50 is as far as you can go with straight recursive implementation. You can switch to iterative or dynamic programming (DP) approaches if you want to go much higher than that. I suggest learning about those from this: https://www.javacodegeeks.com/2014/02/dynamic-programming-introduction.html. And don't forget to look the a solution in the comment by David therein, real efficient. The links shows how even n = 500000 can be computed instantaneously using the DP method. The link also explains the concept of "memoization" to speed up computation by storing intermediate (but later on re-callable) results.

Answer 6

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).

Answer 7

This method of solution is called dynamic programming

1. In this method we are remembering the previous results

2. so when recursion happens then the cpu doesn't have to do any work to recompute the same value again and again

   class fibonacci
   {
   static int fib(int n)
    {
   /* Declare an array to store Fibonacci numbers. */
      int f[] = new int[n+1];
      int i;
   
      /* 0th and 1st number of the series are 0 and 1*/
      f[0] = 0;
      f[1] = 1;
   
      for (i = 2; i <= n; i++)
      {
          /* Add the previous 2 numbers in the series
           and store it */
          f[i] = f[i-1] + f[i-2];
       }
   
       return f[n];
     }
   
   public static void main (String args[])
       {
          int n = 9;
          System.out.println(fib(n));
       }
   }