Fibonacci number calculation method problem

[siery]

Hello.
My idea was to improve the Fibonacci number calculation method by adding a memo. I represent memo as a vector. Every time algorithm are working, it should save it result to memo so next time it can skip this step. The algorithm is really simple and speak for it self so i first show u the code:

float fib2(const float f_n)
{
    float f_f;
    if (!memo.empty()){
        if (memo.at(f_n) > 0.0f) return memo.at(f_n);
    }
    if (f_n < 2.0f) f_f = 1.0f;
    else{
        f_f = fib1(f_n - 1.0f) + fib1(f_n - 2.0f);

        // if more values then memo size, fill extended cells with 0 velue
        for (unsigned int i = f_n - memo.size(); i < f_n; i++)
            memo.push_back(0.0f);
        memo.push_back(f_f);
        return f_f;
    }
    return f_f;
}

The for statement should fill empty cells with 0 so the right value will always be at the right place. Unfortunately it does not work as i expected. Please explain where is the fail or what can i do differently.

Thanks, Daniel

[Stalker]

Can you describe the algorithm you are using? I can't seem to understand it. Is your result off by just one position?

[siery]

It's basic, maybe my notations make it harder to read.
First I check if n is already in memo. If yes just return it:

if (!memo.empty()){
        if (memo.at(f_n) > 0.0f) return memo.at(f_n);
}

Then the whole computation happens here:

if (f_n < 2.0f)
        f_f = 1.0f;
else{
         f_f = fib1(f_n - 1.0f) + fib1(f_n - 2.0f)
return f_f

Simply we can look at it in mathematical sens like:
F1 = F2 = 1
Fn = Fn-1 + Fn-2

Its the basic recursive algorithm to count Fib(n). Every element is equal to sum of two previous.

At the end i fill (or intend to) the empty cells with 0 while saving calculations results at correct place in memo array. I know i use push_back there while different values can be push, not always a bigger one, but that's a detail (I fix it when a vector successfully fills with 0 values).

for (unsigned int i = f_n - memo.size(); i < f_n; i++)
        memo.push_back(0.0f);
memo.push_back(f_f);

[JLBorges]

#include <iostream>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>

// http://www.boost.org/doc/libs/1_60_0/libs/multiprecision/doc/html/boost_multiprecision/intro.html
using big_int = boost::multiprecision::cpp_int ;

big_int fib_n( std::size_t n ) // nth fibonacci number
{
    static std::vector<big_int> memo { 0, 1 } ;

    while( memo.size() <= n ) memo.push_back( memo.back() + memo[ memo.size() - 2 ] ) ;

    return memo[n] ;
}

int main()
{
    for( std::size_t n : { 124, 55, 200, 20, 450, 8 } ) std::cout << fib_n(n) << "  (" << n << ")\n\n" ;
}

http://coliru.stacked-crooked.com/a/68b80684328a890f

[Stalker]

Is your result off by just one position?

That is what I want to understand? Not your algorithm. I just want to know by how much off is your result?

[dhayden]

The problem is line 4 of your original post. It should be if (memo.size() > f_n) {. After all, just because the memo is not empty, that doesn't mean it contains a value for f_n.

Edit: You may be doing this as an exercise for memo, but you can also compute the Fibonacci sequence efficiently without having to use recursion. The trick is to work your way up from 1 rather than down from N.

[JLBorges]

> Is your result off by just one position?

Check it out. Here's a list found on the web. http://planetmath.org/ListOfFibonacciNumbers

[siery]

Yes, u have right, one value to much. Starting values should be:
F0 = 0, F1 = 1 not F1=F2=1
I like the algorithm JLBorges show. But still, i wanna know why my idea is not working. Why the vector is not filling with zeros at empty spaces i this loop?

for (unsigned int i = f_n - memo.size(); i < f_n; i++)
        memo.push_back(0.0f);

[dhayden]

Why the vector is not filling with zeros at empty spaces i this loop?

It's filling it. Here is the code with line 4 fixed and a bunch of debugging code:

vector<float> memo;
float fib2(const float f_n)
{
    cout << "entering fib2(" << f_n << ")\n";
    float f_f;
    if (f_n < memo.size()){
        if (memo.at(f_n) > 0.0f) {
	    cout << "returning memo: " << memo.at(f_n) << '\n';
	    return memo.at(f_n);
	}
	else cout << "memo is zero\n";
    } else {
	cout << "memo is size " << memo.size() << " is too small\n";
    }
    if (f_n < 2.0f) f_f = 1.0f;
    else{
        f_f = fib2(f_n - 1.0f) + fib2(f_n - 2.0f);

        // if more values then memo size, fill extended cells with 0 velue
        for (unsigned int i = f_n - memo.size(); i < f_n; i++) {
	    cout << "pushing zero\n";
            memo.push_back(0.0f);
	}
	cout << "pushing " << f_f << " at index " << memo.size() << '\n';
        memo.push_back(f_f);
        return f_f;
    }
    return f_f;
}

And here is the output for fib2(5):
entering fib2(5)
memo is size 0 is too small
entering fib2(4)
memo is size 0 is too small
entering fib2(3)
memo is size 0 is too small
entering fib2(2)
memo is size 0 is too small
entering fib2(1)
memo is size 0 is too small
entering fib2(0)
memo is size 0 is too small
pushing 2 at index 0
entering fib2(1)
memo is size 1 is too small
pushing zero
pushing 3 at index 2
entering fib2(2)
returning memo: 3
pushing zero
pushing zero
pushing zero
pushing 6 at index 6
entering fib2(3)
memo is zero
entering fib2(2)
returning memo: 3
entering fib2(1)
memo is zero
pushing 4 at index 7
pushing 10 at index 8

Your code is fragile. What if there are already enough values in memo? Then line 14 will push the number at the wrong place. I suggest that you set the value for the right index instead.

    if (f_n < 2.0f) f_f = 1.0f;
    else{
        f_f = fib2(f_n - 1.0f) + fib2(f_n - 2.0f);

        // if more values then memo size, fill extended cells with 0 velue
	while (memo.size() <= f_n) {
	    cout << "pushing zero\n";
            memo.push_back(0.0f);
	}
        memo[f_n] = f_f;
    }
    return f_f;

[Stalker]

Try this change and tell me what happens

for (unsigned int i = f_n - memo.size() + 1; i < f_n; i++)