Fibonacci numbers - dynamic array

Question

I want to write Fibonacci number program, using dynamic array in function. If I want to initialize array in the function, where I must delete this array? Here is code:

#include <iostream>

using namespace std;

int* fibo(int);

int main()
{
    int *fibonacci, n;
    cout << "Enter how many fibonacci numbers you want to print: ";
    cin >> n;
    fibonacci = fibo(n);
    for (int i = 0; i<n; i++)
        cout << fibonacci[i] << " ";

    //for (int i = 0; i < n; i++)
        //delete w_fibo[i];
    //delete[] w_fibo;

    return 0;
}

int* fibo(int n)
{
    int* w_fibo = new int[n];
    if (n >= 0)
        w_fibo[0] = 1;
    if (n >= 1)
        w_fibo[1] = 1;

    for (int i = 1; i < n; i++)
        w_fibo[i + 1] = w_fibo[i] + w_fibo[i - 1];

    return w_fibo;
}

Answer 1

You don't have to initialize the array! a better dynamic Fibonacci presentation could be like this:

int fib2 (int n) {
int i = 1, j = 0;
    for (int k = 0; k < n; k++) { // The loop begins to work real after one loop (k == 1). Sounds interesting!
    j += i;                   // Adds the produced number to the last member of the sequence and makes a new sentence.
    i = j - i;                // Produces the number that should be added to the sequence.
    }
return j;
}

and you can get the n-th fib number using this method. It's O(log(n)) so it's so efficient.`

int fib3 (int n) {

int i = 1, j = 0, k = 0, h = 1, t=0;     
while (n > 0) {

    if (n % 2) {                                        //  |
        t = j * h;                                      //  |
        j = i * h + j * k + t;
        i = i * k + t;
    }
    t = h * h;
    h = 2 * k * h + t;
    k = k * k + t;
    n /= 2;
    }
   return j;
}

Answer 2

If you allocate a std::vector<int> inside fibo() and reserve enough memory, and then return it by value, the memory allocation is taken care for you by the compiler:

#include <iostream>
#include <vector>

using namespace std;

std::vector<int> fibo(int n)
{
    std::vector<int> w_fibo;
    w_fibo.reserve(n);

    if (n >= 0)
        w_fibo[0] = 1;
    if (n >= 1)
        w_fibo[1] = 1;

    for (int i = 1; i < n; i++)
        w_fibo[i + 1] = w_fibo[i] + w_fibo[i - 1];

    return w_fibo;
}

int main()
{    
    int n = 10;
    std::vector<int> fibonacci = fibo(n);
    for (int i = 0; i<n; i++)
        cout << fibonacci[i] << " ";
}

Live Example.

NOTE: This is guaranteed to avoid needlessly copying in C++11 (move semantics) and is likely to do so in C++98 (copy-elision using the return-value-optimization).

Answer 3

This is an old question, but just in case someone happens to pass by this might be helpful.

If you need a efficient method to get the nth Fibonacci number, we have a O(1) time complexity procedure.

It is based on Binet's formula, which I think our friends over at math.se will be better at proving, so feel free to follow that link.

The formula itself is, given a=1.618 and b=-0.618 (these are approximate values)

the n-th term is (a^n - b^n)/2.236. A good way to round that off(since we are using approximate values) would be adding 0.5 and taking the floor function.

math.floor(((math.pow(1.618,n)-math.pow(-0.618,n))/2.236 + 0.5)