# HashMaps and Fibonacci

This time, we do the simplest of all algorithms i.e. Fibonacci series. This is a simple algorithm but depends heavily on the implementation. We all know the loop approach so we skip it and instead do a recursive implementation in c++. And we use hashmaps to store the intermediate results so we don’t end up with O(2^n) time complexity and keep it at around O(n). Of course the space complexity, in this case, would be O(n) as well since we are storing the intermediate results.

So without further ado, below is the code is as below.

#include <map> #include <stdexcept> // std::out_of_range #include <ctime> #include <iostream> namespace Fibonacci { class Fibonacci { public: Fibonacci(); virtual ~Fibonacci(); unsigned long long calcFibonacci(unsigned int number); private: std::map<int, unsigned long long> *m_FibMap; }; Fibonacci::Fibonacci() { m_FibMap = new std::map<int, unsigned long long>(); } Fibonacci::~Fibonacci() { delete m_FibMap; } unsigned long long Fibonacci::calcFibonacci(unsigned int number) { unsigned long long result{}; if(number == 0 || number == 1) { (*m_FibMap)[0] = 0; (*m_FibMap)[1] = 1; m_FibMap->at(number); } if(m_FibMap->find(number) != m_FibMap->end()) { result = m_FibMap->at(number); } else { (*m_FibMap)[number] = calcFibonacci(number - 1) + calcFibonacci(number - 2); result = m_FibMap->at(number); } return result; } } int main() { int number{1000}; Fibonacci::Fibonacci fib; int ticks=clock(); std::cout << std::endl << "Fibonacci for " << number << " is " << fib.calcFibonacci(number) << std::endl; ticks=clock() - ticks; std::cout << std::endl << "Execution time for Fib Calculation for " << number << " is " << ticks << " ticks i.e. " << (((float)ticks)/CLOCKS_PER_SEC) << "seconds" << std::endl; }

The code is very easy to understand. Basically, we are storing the results of already calculated values in a map which are reused for further calculations. Hence we get less runtime complexity with a bit more space complexity. I have also added code to calculate the number of clock ticks it takes to run the code. Also, a number of seconds elapsed can be seen.

The code will start showing its awesomeness once you start using the same instant of the class for multiple Fibonacci calculations. The tick count will go down drastically since all the numbers (present in the lower range than the previous one) will already be mapped in the hashmap. Then it would be a simple lookup in the hashmap. Newer numbers if larger than the previous calculations will be calculated but that will still happen quickly.

### Points to keep in mind

Also we have a limit on ulonglong so don’t forget about it. If you really want to get larger digits, I suggest BigInt libraries but I don’t want to put them all in ideone. That is a side project for your local machines. I will soon open source a repository of all these code samples on gitlab.com which can be accessed and contributed too as needed.

Visit me at: https://www.naresh.se/

Follow me on Twitter: @wolverine2k