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 ?

one word: [memoization](https://en.wikipedia.org/wiki/Memoization) (actually a second word would be [golden ratio](https://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence)) — njzk2, Oct 03 '16 at 20:14
Your answer is in the following question: [Nth Fibonacci Number](http://stackoverflow.com/questions/1525521/nth-fibonacci-number-in-sublinear-time) — TimeToCode, Oct 03 '16 at 20:16

score 8 · Answer 1 · answered Oct 03 '16 at 20:26

8

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

answered Oct 03 '16 at 20:26

Zain Zafar

1,607
4
14
23

Actually the complexity is `O(log(s))` where `s` is the result. This is because larger results need more computation to calculate. `s` is `c^n` so the time complexity is actually `O(n)` to evaluate this exactly. – Peter Lawrey Oct 03 '16 at 20:38
The calculation will with floating point derail, at around 70, so one can nicely use it to arrive the last two good fibs and continue from there. – Joop Eggen Oct 03 '16 at 21:08
This is brilliant, but the java version is: public static int nthFibonacciTerm(int n) { double squareRootOf5 = Math.sqrt(5); double phi = (1 + squareRootOf5)/2; int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5); return nthTerm; } Reference: https://www.baeldung.com/java-fibonacci – ajl Aug 20 '22 at 21:16

Nir Alfasi · Answer 2 · 2022-10-13T19:04:03.877

3

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

edited Oct 13 '22 at 19:04

answered Oct 03 '16 at 20:21

Nir Alfasi

53,191
11
86
129

Incorrect return type. – Zon Sep 27 '22 at 07:03
@Zon you're right thanks! (corrected) – Nir Alfasi Sep 27 '22 at 13:10

Stefan Tataru · Answer 3 · 2022-12-01T00:18:26.400

Well, here goes my solution using a Map and some math formulas. (source:https://www.nayuki.io/page/fast-fibonacci-algorithms)

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

It is also possible implement it using lists instead of a map but it is just reinventing the wheel.

When using Iteration solution, we don't worry about running out of memory, but it takes a lot of time to get fib(1000000), for example. In this solution we may be running out of memory for very very very very big inputs (like 10000 billion, idk) but it is much much much faster.

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

score 1 · Accepted Answer · answered Oct 03 '16 at 20:19

This method of solution is called dynamic programming

In this method we are remembering the previous results

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

score 0 · Answer 5 · answered Apr 27 '20 at 21:56

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

score 0 · Answer 6 · answered Nov 30 '21 at 21:18

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

mohsenmadi · Answer 7 · 2016-10-04T13:12:04.260

-1

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.

edited Oct 04 '16 at 13:12

answered Oct 03 '16 at 20:17

mohsenmadi

2,277
1
23
34

My goodness! Some touchy members have their finger on the demote arrow faster than lightening! Any way, true iterative solutions cannot suffer from exhaustion unless the computed number cannot be stored in an integer/long field. The link I provided still gives good educational ideas for this post. – mohsenmadi Oct 03 '16 at 20:22
"The link I provided still gives good educational ideas for this post." Please include the relevant details from the link in your answer. If the link dies, this answer becomes useless. – Andy Turner Oct 03 '16 at 20:31
Fine. Any more writing and now we are just a fat Deitel & Deitel textbook. – mohsenmadi Oct 03 '16 at 20:42

Java Fibonacci Sequence fast method

7 Answers7