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.
| 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:
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 🍪