Fibonacci memoization algorithm in C++

Question

I'm struggling a bit with dynamic programming. To be more specific, implementing an algorithm for finding Fibonacci numbers of n.

I have a naive algorithm that works:

int fib(int n) {
    if(n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

But when i try to do it with memoization the function always returns 0:

int fib_mem(int n) {
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}

I've defined the lookup_table and initially stored NIL in all elements.

Any ideas what could be wrong?

Here's the whole program as requested:

#include <iostream>

#define NIL -1
#define MAX 100

long int lookup_table[MAX];

using namespace std;

int fib(int n);
int fib_mem(int n);

void initialize() {
    for(int i = 0; i < MAX; i++) {
        lookup_table[i] == NIL;
    }
}

int main() {
    int n;
    long int fibonnaci, fibonacci_mem;
    cin >> n;

    // naive solution
    fibonnaci = fib(n);

    // memoized solution
    initialize();
    fibonacci_mem = fib_mem(n);

    cout << fibonnaci << endl << fibonacci_mem << endl;

    return 0;
}

int fib(int n) {
    if(n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

int fib_mem(int n) {
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}

Answer 1

I always advise to implement recursive memoization with this trick:

Divide the recursive implementation of the memoization implementation, and make them call each others.

This tend to produce easy-to-write & easy-to-read code:

int fib_mem(int n);
int fib(int n) { return n <= 1 ? n : fib_mem(n-1) + fib_mem(n-2); }

int fib_mem(int n)
{
    if (lookup_table[n] == NIL) {
        lookup_table[n] = fib(n);
    }
    return lookup_table[n];
}

---

This allows to define a generic memoize template function to use with all your heavy functions:

template<auto&& func, class Key>
auto memoize(Key&& key)
{
    using Value = decltype(func(std::declval<Key>()));
    static std::map<Key, Value> lookup_table;
    if (lookup_table.find(key) == end(lookup_table)) {
        lookup_table[key] = func(key);
    }
    return lookup_table[key];
}

int fib(int n) { return n <= 1 ? n : memoize<fib>(n-1) + memoize<fib>(n-2); }
double fact(int n) { return n <= 0 ? 1 : n * memoize<fact>(n-1); }

Full demo on Compiler Explorer

Obviously, in non-sparse situation (if you expect to need almost all values of your function in a range, an array of optional could be a better choice than a map.

Answer 2

In my solution, I am using a map instead of an array to store the memo.

#include <iostream>
#include <map>
using namespace std;

map<int, unsigned long long> memo;

unsigned long long fibo(int n) {
    if (memo[n]) {
        return memo[n];
    }

    if (n <= 1) {
        return n;
    }
    memo[n] = fibo(n-1) + fibo(n-2);
    return memo[n];
}

int main() {
    int n; 
    cin >> n;
    cout << "Ans: " << fibo(n);
    return 0;
}

Answer 3

Interesting concept. Speeding up by memoization.

There is a different concept. You could call it compile time memoization. But in reality it is a compile time pre calculation of all Fibonacci numbers that fit into a 64 bit value.

One important property of the Fibonacci series is that the values grow strongly exponential. So, all existing build in integer data types will overflow rather quick.

With Binet's formula you can calculate that the 93rd Fibonacci number is the last that will fit in a 64bit unsigned value.

And calculating 93 values during compilation is a really simple task.

We will first define the default approach for calculation a Fibonacci number as a constexpr function:

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

With that, Fibonacci numbers can easily be calculated at runtime. Then, we fill a std::array with all Fibonacci numbers. We use also a constexpr and make it a template with a variadic parameter pack.

We use std::integer_sequence to create a Fibonacci number for indices 0,1,2,3,4,5, ....

That is straigtforward and not complicated:

template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

This function will be fed with an integer sequence 0,1,2,3,4,... and return a std::array<unsigned long long, ...> with the corresponding Fibonacci numbers.

We know that we can store maximum 93 values. And therefore we make a next function, that will call the above with the integer sequence 1,2,3,4,...,92,93, like so:

constexpr auto generateArray() noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

And now, finally,

constexpr auto FIB = generateArray();

will give us a compile-time std::array<unsigned long long, 93> with the name FIB containing all Fibonacci numbers. And if we need the i'th Fibonacci number, then we can simply write FIB[i]. There will be no calculation at runtime.

I do not think that there is a faster way to calculate the n'th Fibonacci number.

Please see the complete program below:

#include <iostream>
#include <array>
#include <utility>
// ----------------------------------------------------------------------
// All the following will be done during compile time

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}
// We will automatically build an array of Fibonacci numberscompile time
// Generate a std::array with n elements 
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

// Max index for Fibonaccis that for in an 64bit unsigned value (Binets formula)
constexpr size_t MaxIndexFor64BitValue = 93;

// Generate the required number of elements
constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

// This is an constexpr array of all Fibonacci numbers
constexpr auto FIB = generateArray();
// ----------------------------------------------------------------------

// Test
int main() {

    // Print all possible Fibonacci numbers
    for (size_t i{}; i < MaxIndexFor64BitValue; ++i)

        std::cout << i << "\t--> " << FIB[i] << '\n';

    return 0;
}

Developed and tested with Microsoft Visual Studio Community 2019, Version 16.8.2.

Additionally compiled and tested with clang11.0 and gcc10.2

Language: C++17

Answer 4

The error is on initialize function (you've used comparison operator '==' where you want a attribution operator '='). But, on semantics, you don't need initialize look_table with -1 (NIL) because Fibonacci results never will be 0 (zero); so, you can initialize it all with zero. Look below the final solution:

#include <iostream>

#define NIL 0
#define MAX 1000

long int lookup_table[MAX] = {};

using namespace std;

long int fib(int n) {
    if(n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

long int fib_mem(int n) {
    assert(n < MAX);
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}

int main() {
    int n;
    long int fibonnaci, fibonacci_mem;
    cout << " n = "; cin >> n;

    // naive solution
    fibonnaci = fib(n);

    // memoized solution
    // initialize();
    fibonacci_mem = fib_mem(n);

    cout << fibonnaci << endl << fibonacci_mem << endl;

    return 0;
}

Answer 5

Since the issue is initialization, the C++ standard library allows you to initialize sequences without having to write for loops and thus will prevent you from making mistakes such as using == instead of =.

The std::fill_n function does this:

#include <algorithm>
//...

void initialize()
{
   std::fill_n(lookup_table, MAX, NIL);
}

Answer 6

There's a mistake in your initialize() function:

void initialize() {
    for(int i = 0; i < MAX; i++) {
        lookup_table[i] == NIL; // <- mistake
    }
}

In the line pointed you compare lookup_table[i] and NIL (and don't use the result) instead of assigning NIL to lookup_table[i].

For assignment, you should use = instead of ==.

Also, in such situations the most right thing to do is compilation of your program with all warnings enabled. For example, MS VC++ shows the following warning:

warning C4553: '==': operator has no effect; did you intend '='?

Answer 7

#include <iostream>
#define N 100

using namespace std;

const int NIL = -1;
int lookup_table[N];

void init()
{
    for(int i=0; i<N; i++)
        lookup_table[i] = NIL;
}
int fib_mem(int n) {
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}
int main()
{
    init();
    cout<<fib_mem(5);
    cout<<fib_mem(7);
}

Using the exactly same function, and this is working fine.

You have done something wrong in initialisation of lookup_table.