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:

F₀	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅	F₁₆	F₁₇	F₁₈	F₁₉	F₂₀
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 F₁ is being calculated more than once, we store it temporarily and reuse it instead of calculating it. The F₁ 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 (F₁ 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.

with binary recursion
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!

Ellion

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

Tagged Fibonacci

0 0 votes

Article Rating