Fast Fibonacci Using Dynamic Programming
This program demonstrates the speed of dynamic programming. For more info on dynamic programming, check out MrEconomical's great tutorial.
Anyways, let's cut to the chase. The attached repl is somewhat of an experiment.
The repl is a simple C++ program with 2 functions:
fib, which calculates a number in the Fibonacci series using recursion, and
dynamic_fib, which calculates a number in the series using dynamic programming.
- Method (recursive or dynamic)
- Amount of time to calculate the number (in seconds)
Calculating a number in the Fibonacci series using dynamic programming will be significantly faster than using recursion.
The 40th item in the series is calculated by both functions, one after another. Each function is timed, and the function's time is displayed after it finishes. After both functions are done, the difference in time is shown.
On average, the dynamic method took about 4.5e-05 (0.000045) seconds, and the recursive method took about 1.23 seconds, confirming the hypothesis.