Simple code to obtain n-th number of Fibonnaci

Question

I am just trying to produce an efficient piece of code to obtain the n-th number of a Fibonacci sequence and am using the code below to do this. But, I get the error Expression: vector subscript out of range and don't know why it happens.

int Fib(int n)
{
    vector<int> output;
    output.reserve(n);
    output[0] = 1; output[1] = 2;
    for(int i = 2; i <=n; ++i)
    {
        output.push_back(output[i-1]+ output[i-2]);
    }
return output[n];
}

Answer 1

The original code returns an invalid value for Fib(0) (1 instead of 0) https://en.wikipedia.org/wiki/Fibonacci_number.

The following code fixes this issue and the vector initialization:

int fib(int n)
{
    vector<int> output;
    output.resize(n+1);
    output.clear();
    output.push_back(0);
    output.push_back(1);

    for (int i=2; i <= n; i++)
    {
        output.push_back(output[i-1] + output[i-2]);
    }

    return output[n];
}

Any way there's even a better implementation which doesn't require the use of vectors:

int fib(int n) 
{
    if ( n == 0 || n == 1 ) 
        return n;

    int fib1 = 0; 
    int fib2 = 1;
    int fib = 0;

    for ( int i = 2; i < n; i++ ) 
    {
        fib = fib1 + fib2;
        fib1 = fib2;
        fib2 = fib;
    }

    return fib;
}

Answer 2

int fib()
{
cout<<"Enter the term";
cin>>n;
int f=0,f1=1,f2=0;
for(i=1;i!=n;i++)
{
f=f1+f2;
f1=f2;
f2=f;
}
if(i==n)
cout<<n<<"'th term is"<<f;
}

Is it simple enough correct me if i'm wrong

Answer 3

std::vector::reserve is only a performance hint for the container to preallocate storage for data; it does not actually fill the vector with n elements. So, when you try to access the elements like output[0] = 1, you are accessing non-existing elements.

You can simply switch to std::vector::resize, which does what you want. Note that after thas std::vector::push_back makes the algorithm wrong, you should do

output[n] = output[n-1] + output[n-2];

By the way, this method is not very efficient, at least due to needless memory allocation. Something like this should be faster:

int Fib(int n)
{
    int a = 0, b = 1;
    for(int i = 0; i < n; ++i)
    {
        int t = a + b;
        a = b;
        b = t;
    }
    return a;
}

Answer 4

Since you reserve a space for n variables, you vector can be indexed up to n-1, whereas you return output[n], thereby resulting in the error: vector subscript out of range. To have space for the last variable you should use reserve(n+1). However, note that this will be the n+1 fibonacci number.

Also, vector.reserve() allocates memory to the vector without initialising it. So you can't access elements such as output[0]. Instead you should either push_back the values at index 0 and 1 (along with other values), or use vector.resize() and then access all elements by index instead of using push_back.

For a explanation on the difference between resize and reserve, refer to this SO thread.

Answer 5

This line

output.reserve(n);

does not add elements to the vector - it merely reserves space in memory for that amount of items. It does not populate the vector with anything - you can verify this by calling size() on the vector which will return zero. Therefore here

output[0] = 1; output[1] = 2;

you are attempting to modify values at specific indices - but there is nothing at these indices and your indices exceed the vector array bounds (as the message tells you). You should actually populate the vector before you try reading from or writing to specific indices.

In your case simply adding

output.push_back(1);
output.push_back(2);

prior to your loop will resolve this problem (alternatively use resize as other answers suggest).

Answer 6

you should do something like this:

std::vector<int> output;
        output.resize(n+1); // resize not reserv  & n+1 because the <=n
        output[0] = 1; output[1] = 2;
        for (int i = 2; i <= n; ++i)
        {
            output[i]=(output[i - 1] + output[i - 2]); // indexing not push_back
        }

BTW if you really want to use vectors which not seems a best option you should better do something like :

std::vector<unsigned long long> output;
output.resize(n+1);
output[0] = 1; output[1] = 2;
const auto end_of_output(std::end(output));
for (auto& it = std::begin(output) + 2; it < end_of_output; ++it){
    *it = *(it - 1) + *(it - 2);
}

Answer 7

Reserving != Resizing

You're not inserting default-constructed elements that you can later access with the subscript operator[], but rather hinting to allocate uninitialized memory which only affects the capacity and not the size of the container. Accessing elements that way is therefore invalid.

Even these pre-loop lines are invalid

output.reserve(n);
output[0] = 1; output[1] = 2;

You should rather use resize() and be aware that push_back will then increase the vector's dimensions (so either use push_backs all the way in your code or do resize() and use the subscript access).

int Fib(int n)
{ // Lacks error checking if n < 2
  vector<int> output;
  output.resize(n);
  output[0] = 1; output[1] = 2;
  for (int i = 2; i < n; ++i)
  {
    output[i] = output[i - 1] + output[i - 2];
  }
  return output[n-1];
}

Extra-tips:

• If you're just interested in the n-th Fibonacci number you don't need a full-fledged history with a vector, you can just cache the last two numbers in the sequence

• For large n this approach won't probably work, a smarter approach that runs in logarithmic time (although you still have to do some easy matrix multiplication) could be the following [Linear recurrence relations]

Answer 8

std::vector::reserve only increases the capacity (ie. allocated space) for the vector - it doesn't actually increase the size (ie. number of items) of the vector.

So :

output[0] = 1; output[1] = 2;

is not legal, since you're trying to access the first two items in a vector of size 0.

Instead, do :

output.push_back(1);
output.push_back(2); // this should probably push back 1 though, if you want the Fibonacci sequence

Additionally, you're trying to add one too many item into the vector, so change the loop to :

for(int i = 2; i < n; ++i)

(ie. use < instead of <=).

You'll also have to modify the return statement accordingly :

return output[n - 1];