Fibonacii at its best

[Mayukh_1]

Okay this is my first post and I am quite excited that how it will be recieved by the community. I have a long experience in C++ programming but never been a part of any community hence I believe that as a tyro, my mistakes will be ignored.

This post will be about a problem statement that got in my college exams during my engineering. It was a question of an assignment. The question was as follows

Write the most efficient program to print Fibonacci series up to the value given during runtime and also store the values in a data structure to use it later..your code has to be very memory efficient and much better time complexity than normal programs. You can not use Dynamic Memory allocation!

Well to be precise there are a hell lot of solutions to find the answer. People do use it a lot of techniques to solve this question. But wait, there is a problem in this question. The probelm is the choice of language. If you are intereseted to do this in the good old C, then the problem will occur at the point of storing the values.

You see in the question, it is mentioned that not only you have to print the series upto a certain value, but you need to save the data into a data structure. In C, we have only one rudimentary data structure which can save the series of data in a contegious memory locations: an array. But the problem with the array in C is that you can not declare a array of variable size. For example the line int a[size] would cause the program to crash. Hence you can not declare the size of the array during the runtime, which is actually the objective of the program.

The next solution is to use dynamic memory allocation like this

int size;
printf("Enter the length of the series :: ");
scanf("%d", &size);
int *memPtr = (int *)malloc( (size_t)( (int)sizeof(int) * size ) );

// insert the series..

free(memPtr);

But in the program it is explicitly mentioned that you can not use dynamic memory allocation, hence this option is not valid at all.

So the fact of the matter is that you can not design it in good old C..At least not that I know of. Hence I moved to C++ and after few tweaks & improvements I finally designed something which my professor liked & he finally accepted. Hence the objective of this article is to show my design & ask to fellow community members for a better solution if there were any possible.

I created an header file called fibo.h and the definition fibo.cpp, the main.cpp & of course the Makefile. Here are my each files

fibo.h

#ifndef _fibo_h_
#define _fibo_h_
#include <vector>

class Fibonacii{
private:
    int size;
    std::vector<long> data;
public:
    Fibonacii(int);
    void create_series(void);
    void get_data(void);
};


#endif // _fibo_h_

fibo.cpp

#include "fibo.h"
#include <iostream>
#include <vector>
using namespace std;

// This creates a Fibonacii series
void Fibonacii::create_series(void){
    data.push_back(0);
    data.push_back(1);
    for (int i = 2; i < size; ++i)
    {
        /* code */
        data.push_back(data[i - 2] + data[i - 1]);
    }

}


// This is a constructor
Fibonacii::Fibonacii(int s){
    size = s;
}



// This method is used to print the series
void Fibonacii::get_data(void){
    for (long i: data)
        cout << i << endl;
}

main.cpp

#include "fibo.h"
#include <string>
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char *argv[])
{
    /* code */
    if (argc == 2) {

    int value = stoul(argv[1], nullptr, 10);
    static Fibonacii Fibo(value);
    Fibo.create_series();
    Fibo.get_data();
        return 0;
    }
}

Makefile

MAIN = main
HEADER_DEFINITIONS = fibo
CC = g++-4.9 -std=c++11
COMPILE = -c
EXE = $(MAIN)
OPTIMIZE = -Os
SHELL = /bin/bash
ARGS = 20

all: link
    @echo "Executing..........."
    @echo " > > > > > > OUTPUT < < < < < < "
    @$(SHELL) -c './$(EXE) $(ARGS)'

link: compile
    @echo -n "Linking............."
    @$(SHELL) -c '$(CC) -o $(EXE) *.o'

compile: $(MAIN).cpp $(HEADER_DEFINITIONS).cpp
    @echo -n "Compiling........."
    @$(SHELL) -c '$(CC) $(OPTIMIZE) $(COMPILE) $^'

clean:
    @echo "Cleaning............"
    @$(SHELL) -c 'rm -f *~ *.o $(EXE)'

1. [NOTE: if you don't have g++4.9 version, use only g++. But don't forget to put -std=c++11]

2. [NOTE: vector is type of data structure that as much as I know is implemented using a class template and dynamic memory allocation. Hence this program is still using dynamic memory allocation indirectly]

3. [NOTE: if you need to change the length of the series, the edit the value of ARGS = 20 into any value you like]

** To run the program, just move to the directory in your terminal and type** make all

[ddanbe]

Hi Mayukh_1, welcome at DaniWeb! :)
For fibonacci, I never use any storage.

static unsigned long long Fib(int n)
{
    double sqrt5 = sqrt(5.0);
    double phi = (sqrt5 + 1.0) / 2.0;
    double d = floor((1.0 / sqrt5) * pow(phi, n) + 0.5);
    return d;
}

[Mayukh_1]

Hello ddanbe..Thanks for your reply..Yes you are accurate.. I too don't use storage in Fibonacii but you must understand that the problem statement was designed in such a way that you have to store data into some kind of a database..:)

[ddanbe]

Yes Mayukh_1 I realized that, but with the formula of Binet, why would you even store all the numbers?
But I guess there's a gain in not have to calculate instead of only to lookup a number.
@decepticon: thanks for the rep. Are you sure it is only an approximation? OK, it returns a real number, but after rounding, the fib number seems to be correct always.

[NathanOliver]

I just want to point out that if part of the requirement is to not use any dynamic memory allocation you shouldn't be able to use a vector. A vector is just a wrapper for a dynamic array. I am being a little nit picky about that but your professor doesn't seam to care so vector FTW.