Dynamic Fibonacci program

Edit:
After some more time spent on the topic and the discovery (at least for me) of some of the beauty behind the Fibonacci sequence and its associated algorithm, I published my "definitive" guide at this address.

My initial answer, below, is still valid but what the library I posted in the same repository brings is:

• The code is cleaner and easier to understand, with an actual matrix type.
• Performance was improved: all Fibonacci numbers between index 50000 an index 55000 are calculated in 20-25ms (printing of numbers excluded as I had not measured that back then).
• The matrix exponantiation algorithm no longer needs to start at Fibonacci(1): if you give the algorithm 2 consecutive Fibonacci numbers (or n consecutive numbers for generalized sequences), it can calculate any subsequent number (for instance, you could save some numbers into a file/database as text so that the next time you run your program, you can restart from there).
  I think that last point truly removes all the benefits from implementing a cache.

There are several options to optimize the calculation of the fibonacci sequence:

1. Reuse known values.
2. During the calculation of fibonacci(n), avoid a recursion where 2^n branches extend to fibonacci(1).
3. Return ranges of values instead of individual values.

Memoization lets you achieve point 1 and because it does, it also lets you achieve point 2. This comes at a cost though, and I will detail what I mean by that later in my answer.

What I would like to explore for now is a solution that achieves points 2 and 3.

Step 0: Some prerequisites

You can only store up to fibonacci(93) using 64-bit integers. To overcome that limitation, I have used the bigint library provided at this address. Likely not the best thing out there but easy enough to use; I am sure other bigint libraries would work too.

For ease of use later, we will use 2 constants, which are going to be the bounds of the range we want to calculate:

#define MININDEX 1000 #define MAXINDEX 1500 

Step 1: calculate fibonacci values in linear complexity

What is important to understand with the fibonacci sequence is that you only need to remember the last 2 terms to calculate the next one. Put a different way, every term is useful immediately after being calculated and then only once more.
Whe can use that fact to create a simplified non-recursive function.

bigint fibonacci(unsigned int n) { if (n == 0) return 0; bigint a = 1, b = 0; for (int i = 1; i < n; ++i) { bigint c = a; a = a + b; b = c; } return a; } 

For the record, I did not consider returning several values in my original answer so this function was what I submitted.

Ignoring the fact that arithmetic operations, and intialization/copy operations have non constant complexity for very big numbers, the above function executes in O(n) operations unlike the classic approach (fib(n) = fib(n-1) + fib(n-2)) or your attempt using a std::map (looking n times into a map is O(n log(n)).

It is easy to understand how O(n) is the best complexity we can hope for when calculating all the consecutive fibonacci(i) values: we cannot get n results in less than n operations.
With that said, this version of the function to get all fibonacci(i) values between n1 and n2 still is at O((n2 - n1)^2) complexity.

Step 2: Filling a vector with consecutive values

To avoid having to restart the calculation from 1 for every consecutive values, the above function can easily be changed to return a vector with all the consecutive values between 2 indices.
The vector in that version is the out parameter result:

void fibonacci_range(std::vector<bigint>& result, unsigned short from, unsigned short to) { auto [a, b] = some_magical_function(from); //We need consecutive 2 values to start the loop. result.push_back(a); for (unsigned short i = from; i < to; ++i) { bigint c = a; a += b; bigint::_big_swap(b, c); result.push_back(std::move(a)); } } 

Step 3: Calculating the values at the start of the returned sequence

As you may have noticed, the above function uses a call to some_magical_function(from), not yet defined. We could tweak the previous fibonacci function to return 2 values and call it here.

However, in the case where you need only 2 consecutive values rather than all consecutive values within a range, the O(n) algorithm is not the best one.
As was explained in another answer (and here), there exists an algorithm that can calculate fibonacci(n) while skipping most values between 1 and n along the way, thus achieving a O(log(n)) complexity.

TBH, I would have upvoted the other answer, had the code been better optimized. Rather than using it, I have written a faster version to make it more practical.

One of the trick is to store 2x2 symmetrical matrices as 3 elements in an array.

#include <array> void matrix_power(std::array<bigint, 3>& result, std::array<bigint, 3>& M, unsigned int exp) { auto multiplyWith = [] (std::array<bigint, 3>&target, const std::array<bigint, 3>& with) { bigint a = target[0] * with[0] + target[1] * with[1], b = target[0] * with[1] + target[1] * with[2], c = target[1] * with[1] + target[2] * with[2]; target[0] = std::move(a); target[1] = std::move(b); target[2] = std::move(c); }; while (exp > 1) { if ((exp & 1) == 1) multiplyWith(result, M); multiplyWith(M, M); exp = exp >> 1; } multiplyWith(result, M); } std::pair<bigint,bigint> fibonacci_matrix(unsigned int n) { if (n <= 1) return std::make_pair(0, static_cast<int>(n)); //As an optimization, 2x2 symmetric matrices are stored as 3 numbers. std::array<bigint, 3> fiboMatrix = { 1, 1, 0 }, result_matrix = { 1, 0, 1 }; matrix_power(result_matrix, fiboMatrix, n - 1); return std::make_pair(result_matrix[0], result_matrix[1]); } 

Step 4: combine both functions

In the definition of fibonacci_range(...) all you have to do is replace some_magical_function by auto [a, b] = fibonacci_matrix(from);

When calculating all the values between n1 and n2, the complexity becomes O(log(n1)) + O(n2 - n1).

You could achieve that same complexity with only a modified version of fibonacci_matrix but 2x2 matrix multiplication uses a little bit more arithmetic operations than what the fibonacci_range does for each term, hence such solution would be a little bit slower.

Complete code

I have created an example to test different versions of the fibonacci function, without a cache and with different versions of a cache (map as in your question + unordered_map as was suggested in a comment + C-style array just to see what the fastest container I can think of can do).

Every cached version runs twice. The first time, it runs from an empty cache while the second time, the cache is first initialized with the first value of the returned range, then calculates the rest from there.
For ranges beyond 20k I recommend you only keep the versions with no cache or for which the cache is initialized separately (meaning you should disable the calls that are done on an empty cache).

In the scenario I coded, the function without a cache is always faster (sometimes by a long shot), which means you are using memory (potentially a lot of it if you store many very large integers) to make your algorithm slightly slower.
It should be obvious BTW: values stored in cache are never used more than twice. Just the 2 variables of the "vanilla" algorithm are enough.
This was my initial point: having a cache does not necessarily means that you are using it and that it will save you any time. Going beyond what 64-bit integers can do, how long does it even take to copy values in and out of the cache?

The (almost) final result on my computer is all the values between fibonacci(50000) and fibonacci(55000) are returned in 10 to 12 secs, faster than any cache can give me.

Full code:

#include <bigint.h> #define MININDEX 50000 #define MAXINDEX 55000 bigint fibonacci(unsigned int n) { if (n == 0) return 0; bigint a = 1, b = 0; for (int i = 1; i < n; ++i) { bigint c = a; a = a + b; b = c; } return a; } bigint fiboArrayCache[1 + MAXINDEX] = { 0, 1 }; unsigned int fiboCalcUntil_array = 1; bigint fibonacci_array(unsigned int n) { if (n <= fiboCalcUntil_array) return fiboArrayCache[n]; bigint a = fiboArrayCache[fiboCalcUntil_array], b = fiboArrayCache[fiboCalcUntil_array - 1]; for (unsigned int i = fiboCalcUntil_array; i < n; ++i) { bigint c = a; a = a + b; b = c; fiboArrayCache[1 + i] = a; } fiboCalcUntil_array = n; return a; } #include <map> std::map<unsigned int, bigint> fiboMapCache = { {0, 0}, {1, 1} }; bigint fibonacci_map(unsigned int n) { if (auto cachedValue = fiboMapCache.find(n); cachedValue != fiboMapCache.end()) //C++17 syntax return std::get<1>(*cachedValue); auto lastItemsIter = fiboMapCache.end(); lastItemsIter--; unsigned int startPoint = std::get<0>(*lastItemsIter); bigint a = std::get<1>(*lastItemsIter); lastItemsIter--; bigint b = std::get<1>(*lastItemsIter); for (unsigned int i = startPoint; i < n; ++i) { bigint c = a; a = a + b; b = c; fiboMapCache.insert({ i, b }); } fiboMapCache.insert({ n, a }); return a; } #include <unordered_map> std::unordered_map<unsigned int, bigint> fiboUnorderedMapCache = { {0, 0}, {1, 1} }; unsigned int fiboCalcUntil_unorderedMap = 1; bigint fibonacci_unorderedMap(unsigned int n) { if (n < fiboCalcUntil_unorderedMap) return fiboUnorderedMapCache[n]; bigint a = fiboUnorderedMapCache[fiboCalcUntil_unorderedMap], b = fiboUnorderedMapCache[fiboCalcUntil_unorderedMap - 1]; for (unsigned int i = fiboCalcUntil_unorderedMap; i < n; ++i) { bigint c = a; a = a + b; b = c; fiboUnorderedMapCache.insert({ i, b }); } fiboCalcUntil_unorderedMap = n; fiboUnorderedMapCache.insert({ n, a }); return a; } #include <array> void matrix_power(std::array<bigint, 3>& result, std::array<bigint, 3>& M, unsigned int exp) { auto multiplyWith = [] (std::array<bigint, 3>&target, const std::array<bigint, 3>& with) { bigint a = target[0] * with[0] + target[1] * with[1], b = target[0] * with[1] + target[1] * with[2], c = target[1] * with[1] + target[2] * with[2]; target[0] = std::move(a); target[1] = std::move(b); target[2] = std::move(c); }; while (exp > 1) { if ((exp & 1) == 1) multiplyWith(result, M); multiplyWith(M, M); exp = exp >> 1; } multiplyWith(result, M); } std::pair<bigint,bigint> fibonacci_matrix(unsigned int n) { if (n <= 1) return std::make_pair(static_cast<int>(n), 0); //As an optimization, 2x2 symmetric matrices are stored as 3 numbers. std::array<bigint, 3> fiboMatrix = { 1, 1, 0 }, result_matrix = { 1, 0, 1 }; matrix_power(result_matrix, fiboMatrix, n - 1); return std::make_pair(result_matrix[0], result_matrix[1]); } #include <vector> void fibonacci_range(std::vector<bigint>& result, unsigned int from, unsigned int to) { auto [a, b] = fibonacci_matrix(from); result.push_back(a); for (unsigned int i = from; i < to; ++i) { bigint c = a; a += b; bigint::_big_swap(b, c); result.push_back(std::move(a)); } } #include <chrono> #include <iostream> int main(int argc, char* argv[]) { using std::chrono::steady_clock; using std::chrono::duration_cast; using std::chrono::duration; using std::chrono::milliseconds; //{ // //Vanilla // bigint fiboResults[1 + MAXINDEX - MININDEX] = { 0 }; // auto start = steady_clock::now(); // for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) // fiboResults[n - MININDEX] = fibonacci(n); // auto end = steady_clock::now(); // //for (unsigned int n = MININDEX; n < MAXINDEX; ++n) // // std::cout << fiboResults[n - MININDEX] << std::endl; // std::cout << fiboResults[0] << std::endl; // std::cout << fiboResults[MAXINDEX - MININDEX] << std::endl; // auto ms_int = std::chrono::duration_cast<std::chrono::milliseconds>(end - start); // std::cout << "fibonacci (vanilla, linear) : " // << ms_int.count() << ' ' << " ms" << std::endl << std::endl << std::endl; //} auto [f1, f2] = fibonacci_matrix(1 + MININDEX); { //Map bigint fiboResults[1 + MAXINDEX - MININDEX] = { 0 }; auto start = steady_clock::now(); static_cast<void>(fibonacci_map(MAXINDEX)); for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) fiboResults[n - MININDEX] = fibonacci_map(n); auto end = steady_clock::now(); //for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) // std::cout << fiboResults[n - MININDEX] << std::endl; std::cout << fiboResults[0] << std::endl; std::cout << fiboResults[MAXINDEX - MININDEX] << std::endl; auto ms_int = std::chrono::duration_cast<std::chrono::milliseconds>(end - start); std::cout << "fibonacci (cached in map) : " << ms_int.count() << ' ' << " ms" << std::endl << std::endl << std::endl; } fiboMapCache.clear(); { //Map bigint fiboResults[1 + MAXINDEX - MININDEX] = { 0 }; auto start = steady_clock::now(); fiboMapCache.insert({ 1 + MININDEX,f1 }); fiboMapCache.insert({ MININDEX,f2 }); for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) fiboResults[n - MININDEX] = fibonacci_map(n); auto end = steady_clock::now(); //for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) // std::cout << fiboResults[n - MININDEX] << std::endl; std::cout << fiboResults[0] << std::endl; std::cout << fiboResults[MAXINDEX - MININDEX] << std::endl; auto ms_int = std::chrono::duration_cast<std::chrono::milliseconds>(end - start); std::cout << "fibonacci (cached in map, cache is initialized separately) : " << ms_int.count() << ' ' << " ms" << std::endl << std::endl << std::endl; } { //Unordered map bigint fiboResults[1 + MAXINDEX - MININDEX] = { 0 }; auto start = steady_clock::now(); static_cast<void>(fibonacci_unorderedMap(MAXINDEX)); for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) fiboResults[n - MININDEX] = fibonacci_unorderedMap(n); auto end = steady_clock::now(); //for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) // std::cout << fiboResults[n - MININDEX] << std::endl; std::cout << fiboResults[0] << std::endl; std::cout << fiboResults[MAXINDEX - MININDEX] << std::endl; auto ms_int = std::chrono::duration_cast<std::chrono::milliseconds>(end - start); std::cout << "fibonacci (cached in unordered map) : " << ms_int.count() << ' ' << " ms" << std::endl << std::endl << std::endl; } fiboUnorderedMapCache.clear(); fiboCalcUntil_unorderedMap = 1; { //Unordered map bigint fiboResults[1 + MAXINDEX - MININDEX] = { 0 }; auto start = steady_clock::now(); fiboUnorderedMapCache.insert({ 1 + MININDEX,f1 }); fiboUnorderedMapCache.insert({ MININDEX,f2 }); for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) fiboResults[n - MININDEX] = fibonacci_unorderedMap(n); auto end = steady_clock::now(); //for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) // std::cout << fiboResults[n - MININDEX] << std::endl; std::cout << fiboResults[0] << std::endl; std::cout << fiboResults[MAXINDEX - MININDEX] << std::endl; auto ms_int = std::chrono::duration_cast<std::chrono::milliseconds>(end - start); std::cout << "fibonacci (cached in unordered map, cache is initialized separately) : " << ms_int.count() << ' ' << " ms" << std::endl << std::endl << std::endl; } { //Array bigint* fiboResults = new bigint[1 + MAXINDEX - MININDEX]; auto start = steady_clock::now(); static_cast<void>(fibonacci_array(MAXINDEX)); for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) fiboResults[n - MININDEX] = fibonacci_array(n); auto end = steady_clock::now(); // for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) // std::cout << fiboResults[n - MININDEX] << std::endl; std::cout << fiboResults[0] << std::endl; std::cout << fiboResults[MAXINDEX - MININDEX] << std::endl; auto ms_int = std::chrono::duration_cast<std::chrono::milliseconds>(end - start); std::cout << "fibonacci (cached in array) : " << ms_int.count() << ' ' << " ms" << std::endl << std::endl << std::endl; delete[] fiboResults; } fiboCalcUntil_array = 1; { //Array bigint* fiboResults = new bigint[1 + MAXINDEX - MININDEX]; auto start = steady_clock::now(); fiboArrayCache[1 + MININDEX] = f1; fiboArrayCache[MININDEX] = f2; for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) fiboResults[n - MININDEX] = fibonacci_array(n); auto end = steady_clock::now(); // for (unsigned int n = MININDEX; n <= MAXINDEX; ++n) // std::cout << fiboResults[n - MININDEX] << std::endl; std::cout << fiboResults[0] << std::endl; std::cout << fiboResults[MAXINDEX - MININDEX] << std::endl; auto ms_int = std::chrono::duration_cast<std::chrono::milliseconds>(end - start); std::cout << "fibonacci (cached in array, cache is initialized separately) : " << ms_int.count() << ' ' << " ms" << std::endl << std::endl << std::endl; delete[] fiboResults; } { //Hybrid std::vector<bigint> fiboResults; fiboResults.reserve(1 + MAXINDEX - MININDEX); auto start = steady_clock::now(); fibonacci_range(fiboResults, MININDEX, MAXINDEX); auto end = steady_clock::now(); //for (auto fiboValue : fiboResults) // std::cout << fiboValue << std::endl; std::cout << fiboResults[0] << std::endl; std::cout << fiboResults[MAXINDEX - MININDEX] << std::endl; auto ms_int = std::chrono::duration_cast<std::chrono::milliseconds>(end - start); std::cout << "fibonacci (hybrid matrix + vanilla) : " << ms_int.count() << ' ' << " ms" << std::endl << std::endl << std::endl; } return 0; } 

The last point I want to mention is that adding code to manage a cache makes it more prone to bugs. I see the following 3 issues on another answer:

1. The below snippet looks in the map cache twice.

   if (map.find(n) != map.end()) { return map[n]; } 

   It should instead do this to save half the time (C++17 and later syntax):

   if (auto iter = map.find(n); iter != map.end()) return std::get<1>(*iter); 

2. Writing into the map at indices n,n-1 and n-2 causes many values to be written in the map thrice.
3. For the same reason as point 1, caling fib(n-1) and fib(n-2) makes the function look up into the map twice when 1 time would suffice:

   auto fib_2 = fib(n - 2); // At this point, the map is guaranteed to be filled up to n - 2. // If initialized with the first 2 items, i has at least 3 items in it. auto iter_to_fib_3 = std::advance(map.end(), -2); // worst case O(log(n)). auto fib_1 = fib_2 + std::get<1>(*iter_to_fib_3); 

This is the risk when you add (unnecessary) code...

Side note:
You should consider measuring time in ms, as explained in that answer.

Memoization in your solution doesn't work as your std::map is local which can be fixed by using a static or global map as has been advised in other answers. Time complexity of the solution will be O(n).

If you really want an algorithmically faster solution, you can use matrix exponentiation.

The idea here is that by visualising two consecutive numbers of fibonacci sequence as a 2 x 1 matrix and multiplying it by a square matrix, you can obtain the next sequence of fibonacci numbers.

By continuing this multiplication, you can obtain the nth number in the sequence.

Sample code for reference:

// Define a matrix multiplication function vector<vector<long long>> multiply( const vector<vector<long long>>& A, const vector<vector<long long>>& B) { int n = A.size(); vector<vector<long long>> C(n, vector<long long>(n, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { C[i][j] += A[i][k] * B[k][j]; } } } return C; } // Define a function to calculate the matrix exponentiation vector<vector<long long>> matrix_power(const vector<vector<long long>>& M, int exp) { int n = M.size(); vector<vector<long long>> result(n, vector<long long>(n, 0)); vector<vector<long long>> base = M; // Initialize the result matrix as the identity matrix for (int i = 0; i < n; i++) { result[i][i] = 1; } while (exp > 0) { if (exp % 2 == 1) { result = multiply(result, base); } base = multiply(base, base); exp /= 2; } return result; } long long fibonacci(int n) { if (n <= 0) return 0; // Define the base matrix vector<vector<long long>> base = {{1, 1}, {1, 0}}; // Calculate the (n-1)-th power of the base matrix vector<vector<long long>> result_matrix = matrix_power(base, n - 1); return result_matrix[0][0]; } 

Time complexity of this solution: O(k^3 log n) where k is the order of the matrix. In this case, k=2.

Fun fact : If you want real speed/memoization you can memorize values at compile time using constexpr. Then at runtime getting the fibonacci number is just a lookup.

See compiler explorer : https://godbolt.org/z/daM8h83v1 and note the precompiled table .L__const._Z20get_fibonacci_numberm.fibonacci_values:

#include <array> #include <cassert> #include <cstdint> #include <iostream> template<std::size_t N> constexpr auto create_fibonacci_values() { static_assert(N>2); std::array<std::uint64_t,N> values{1ul,1ul}; for(std::size_t n{2ul}; n<N; ++n) { values[n] = (values[n-1] + values[n-2]); } return values; } constexpr auto get_fibonacci_number(std::size_t n) { constexpr auto fibonacci_values = create_fibonacci_values<50>(); assert((n>0) && (n <= fibonacci_values.size())); return fibonacci_values[n-1]; } int main() { for(std::size_t n = 1; n < 40; ++n) { std::cout << get_fibonacci_number(n) << "\n"; }; return 0; } 

In your fibNum function you're creating an empty map on each call and then doing a lookup in it. You need to use the map by looking up n in the map before resorting to the recursive calls fibNum(n - 1) and fibNum(n - 2) and you need to pass the map to the function as a reference parameter so the map can be built up and store the found numbers.

#include <map> #include <iostream> int fib(int n, std::map<int, int>& map) { if (map.find(n) != map.end()) { return map[n]; } int fib_1 = fib(n - 1, map); map[n - 1] = fib_1; int fib_2 = fib(n - 2, map); map[n - 2] = fib_2; int fib_n = fib_1 + fib_2; map[n] = fib_n; return fib_n; } int main() { std::map<int, int> map = {{0, 1}, {1, 1}}; for (int i = 0; i < 30; ++i) { std::cout << fib(i, map) << std::endl; } } 

This solves the Fibonacci problem using dynamic programming

#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int dp[n+1];//dp to store fibonachi number dp[0]=0;// base case 1 dp[1]=1;//base case 2; // ith dp number will be at (i-1)th index in the dp array for(int i=2;i<=n;i++)//time complexity O(n) { dp[i]=dp[i-1]+dp[i-2]; } cout<<dp[n-1]; return 0; }