In this post we will write a couple functions to generate Fibonacci Numbers using the C++ programming language and the Visual Studio 2022 IDE, on a Windows 11 computer.
The motivation came from the on-line course C++20 Fundamentals by Paul J. Deitel, included in the O’Reilly Learning Platform offered by the Association for Computing Machinery.
C++20 for Programmers by Paul Deitel and Harvey Deitel Format: Paperback Language: English ISBN: 0136905692 ISBN13: 9780136905691 Release Date: March 2022 Publisher: Pearson Education Length: 1008 Pages
I have preordered the new book associated with the course on Amazon. Hopefully it should arrive next month.
I believe we have covered Fibonacci Numbers in different posts i.e., Fibonacci Revisited, Fibonacci Sequence, and Reverse Fibonacci Series among others, in this blog.
#include <iostream>
#include <chrono>
using namespace std;
// **** function prototype ****
long fibonacci0(long number);
long fibonacci(long number);
// **** memoization ****
long memo[50]{ 0 };
We will cover two recursive functions that generate Fibonacci numbers. The first will follow the recursive description and will not use memoization. The second will use memoization.
/*
* Test scaffold.
*/
int main() {
// **** start timer ****
auto start = chrono::steady_clock::now();
// **** calculate the fibonacci values of 0 through 10 ****
for (int counter{ 0 }; counter <= 10; ++counter)
cout << "main <<< fibonacci0(" << counter << "): " << fibonacci0(counter) << endl;
cout << endl;
// **** display higher fibonacci values ****
cout << "main <<< fibonacci0(20): " << fibonacci0(20) << endl;
cout << "main <<< fibonacci0(25): " << fibonacci0(25) << endl;
cout << "main <<< fibonacci0(30): " << fibonacci0(30) << endl;
cout << "main <<< fibonacci0(35): " << fibonacci0(35) << endl;
cout << "main <<< fibonacci0(40): " << fibonacci0(40) << endl;
cout << "main <<< fibonacci0(45): " << fibonacci0(45) << endl;
// **** end timer ****
auto end = chrono::steady_clock::now();
// **** compute and display elapsed time in seconds ****
chrono::duration<double> elapsed = end - start;
cout << "main <<< elapsed: " << elapsed << endl << endl;
// **** initialize memoization array ****
memset(memo, 0, sizeof(memo) / sizeof(long));
// **** start timer ****
start = chrono::steady_clock::now();
// **** calculate the fibonacci values of 0 through 10 ****
for (int counter{ 0 }; counter <= 10; ++counter)
cout << "main <<< fibonacci(" << counter << "): " << fibonacci(counter) << endl;
cout << endl;
// **** display higher fibonacci values ****
cout << "main <<< fibonacci(20): " << fibonacci(20) << endl;
cout << "main <<< fibonacci(25): " << fibonacci(25) << endl;
cout << "main <<< fibonacci(30): " << fibonacci(30) << endl;
cout << "main <<< fibonacci(35): " << fibonacci(35) << endl;
cout << "main <<< fibonacci(40): " << fibonacci(40) << endl;
cout << "main <<< fibonacci(45): " << fibonacci(45) << endl;
// **** end timer ****
end = chrono::steady_clock::now();
// **** compute and display elapsed time in seconds ****
elapsed = end - start;
cout << "main <<< elapsed: " << elapsed << endl;
}
The test scaffold starts by getting the start time.
It is followed by a loop that calls the `fibonacci0` function for some small values. It is followed by the generation of larger Fibonacci numbers.
When all is done the time in seconds is displayed.
For the second part of the test we initialize the `memo` array which will be used to implement memoization on the `fibonacci` recursive function.
We get the start time and make the same set of calls we did for the `fibonacci0` function but now we use `fibonacci`.
We collect the `end` time and display the difference.
When timing functions it is not a good idea to do so over functions that display data. Such functions tend to be slow and add to the time being measured. After you run the test code or just look at the screen capture when the test code ran, time measurements illustrate the performance difference between the two calls of interest.
main <<< fibonacci0(0): 0 main <<< fibonacci0(1): 1 main <<< fibonacci0(2): 1 main <<< fibonacci0(3): 2 main <<< fibonacci0(4): 3 main <<< fibonacci0(5): 5 main <<< fibonacci0(6): 8 main <<< fibonacci0(7): 13 main <<< fibonacci0(8): 21 main <<< fibonacci0(9): 34 main <<< fibonacci0(10): 55 main <<< fibonacci0(20): 6765 main <<< fibonacci0(25): 75025 main <<< fibonacci0(30): 832040 main <<< fibonacci0(35): 9227465 main <<< fibonacci0(40): 102334155 main <<< fibonacci0(45): 1134903170 main <<< elapsed: 16.0337s main <<< fibonacci(0): 0 main <<< fibonacci(1): 1 main <<< fibonacci(2): 1 main <<< fibonacci(3): 2 main <<< fibonacci(4): 3 main <<< fibonacci(5): 5 main <<< fibonacci(6): 8 main <<< fibonacci(7): 13 main <<< fibonacci(8): 21 main <<< fibonacci(9): 34 main <<< fibonacci(10): 55 main <<< fibonacci(20): 6765 main <<< fibonacci(25): 75025 main <<< fibonacci(30): 832040 main <<< fibonacci(35): 9227465 main <<< fibonacci(40): 102334155 main <<< fibonacci(45): 1134903170 main <<< elapsed: 0.0038031s
The first set of functions took about 16 seconds. The second set, using the same data, took about 4 milliseconds.
/*
* Recursive function finonacci NOT using memoization.
*/
long fibonacci0(long number) {
// **** base case ****
if ((number == 0) || (number == 1))
return number;
// **** return fibonacci number ****
return fibonacci0(number - 2) + fibonacci0(number - 1);
}
We start by checking on the base condition. Since `number` can start at any value and Fibonacci numbers are defined as the sum of the two previous Fibonacci numbers, sooner or later we will hit 1 and 0. These two values are defined respectively to be 1 and 0.
If the base case has not been reached yet, then recursively we can compute the current fibonacci number fibonacci(n) using the two previous ones, which are defined as fibonacci(n – 1) and fibonacci(n – 2).
n Fibonacci - --------- 0 0 (defined) 1 1 (defined) 2 0 + 1 = 1 (computed) 3 1 + 1 = 2 (computed) 4 1 + 2 = 3 (computed) :::::::::::::::::::::::: n F(n - 1) + f(n - 2)
For numbers n = 0, 1, 2, 3, 4 we have Fibonacci = 0, 1, 1, 2, 3.
The previous implementation of the function of interest uses two stacks of calls that need to go back to 0. That takes a lot of space and we are computing values over and over. Perhaps we could do better.
/*
* Recursive function fibonacci using memoization.
*/
long fibonacci(long number) {
// **** base case ****
if ((number == 0) || (number == 1)) {
memo[number] = number;
return memo[number];
}
// **** initialization ****
long fib = 0;
// **** recursive step for number - 2 ****
if (memo[number - 2] != 0)
fib = memo[number - 2];
else {
memo[number - 2] = fibonacci(number - 2);
fib = memo[number - 2];
}
// **** recursive step for number - 1 ****
if (memo[number - 1] != 0)
fib += memo[number - 1];
else {
memo[number - 1] = fibonacci(number - 1);
fib += memo[number - 1];
}
// **** return fibonacci number ****
return fib;
}
We start with a base case. Note that we first populate the associated values in the `memo` array and then return the value from the `memo` array.
If we are not processing a base case, then we calculate the value for fibonacci(n – 2). If the associated value is already in the `memo` array, we just use it. The same holds for fibonacci(n – 1).
When done, we return the value in the `fib` variable.
Note that during the set of tests, we only need to compute once each value in the `memo` array.
We did not cover the obvious approach which would be to populate the `memo` array in O(n) and then serve the calls directly from the `memo` array in O(1) time. Of course, the range of `n` would have to be known in advance.
In addition, as you can see, the size of the Fibonacci numbers is growing quite fast. We would have to use `long long` and if that is not enough `BigNumber` to avoid running into overflow situations.
Hope you enjoyed this exercise as much as I did. The entire code for this project can be found in my GitHub repository named FibonacciNumbers.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge, and enhance your developer / engineering toolset.
Thanks for reading this post and feel free to connect with me John Canessa on LinkedIn.
Enjoy;
John