Generate Fibonacci number in Java using dynamic programming

problem

This post is a follow up of the previous example that was calculating a Fibonacci number using binary recursion. In this post we will see how to (almost dramatically) speed up the execution time of the algorithm using a technique called dynamic programming.

Recap:
Given a number n, calculate the nth element in the Fibonacci sequence. We chose the sequence to start from 0 and 1 and below you can see the first 20 elements:
F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

problem with binary recursion

The problem is that if we want to calculate the 40th and beyond, the current machine is getting slower and slower to calculate. That is because of the binary recursion and also if we analyze the algorithm further, we will quickly spot that some numbers are being repeatedly calculated. That leads to extra cost without any special benefit. Dynamic programming to the rescue.

DYNAMIC PROGRAMMING

Simply cache/ store the results instead of repeatedly calculating them. More specific, if we assume that F1 is being calculated more than once, we store it temporarily and reuse it instead of calculating it. The F1 is 1. Our approach would be to use a dictionary data structure, in Java that would be a Map (e.g. a HashMap) that has a key and a value. The key will be the argument (F1 in this case) and the value will be 1. Simply, the algorithm will be enhanced with this extra functionality of utilizing a Map. Every time a number is given, instead of calculating it, check if exists in the Map first. If it does exist, return its corresponding value. Otherwise, calculate and put it in the Map.

It is more clear in the code below:

Fibonacci.java
				
					package com.programmerabroad;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    private final Map<BigInteger, BigInteger> results = new HashMap<>();

    public BigInteger calculate(BigInteger n) {
        if (results.containsKey(n)) { //check if already calculated and stored
            return results.get(n);
        } else {
            if (n.compareTo(BigInteger.ZERO)==0) {
                results.put(BigInteger.ZERO,BigInteger.ZERO); //store the result
                return results.get(BigInteger.ZERO);
            } else if (n.compareTo(BigInteger.ONE)==0) {
                results.put(BigInteger.ONE,BigInteger.ONE); //store the result
                return results.get(BigInteger.ONE);
            } else {
                results.put(n, calculate(n.subtract(BigInteger.ONE)).add(calculate(n.subtract(BigInteger.valueOf(2))))); //store the result
                return results.get(n);
            }
        }
    }
}

				
			

Moreover, the BigInteger data type is used instead of the Long data type to be less limited.

running

Below we can compare the 2 solutions.

  1. with binary recursion
  2. with dynamic programming

In both cases, calculating the first 45 elements.

The output of the previous solution is shown below:

output

With Dynamic Programming, the repeated calculations are cached therefore much faster:

Calculating even more, the first 100 elements

Super fast in comparison with the binary recursion. We could have dug even deeper to analyze the exact time taken to run the above two algorithms and compare them as shown in one of the previous posts on using time to compare solutions.

conclusion

This is a better approach to calculate an element in Fibonacci’s sequence. Turns out to be way much faster than the classic binary recursion. It does take more space in memory though but still faster.

Share it!

Facebook
Twitter
LinkedIn
Reddit
Picture of Ellion

Ellion

Professional IT consultant, writer, programmer enthusiast interested in all sorts of coding.
Eats all cookies 🍪

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x