9 ways to generate Fibonacci numbers in C++

Question

This is C++ code that consists of 9 different functions that generate Fibonacci numbers. Although all functions display same result, the emphasis is on practice to use different methods or ways.

I would like to know better ways / technique to improve the existing code (especially, the fibo_9 function which uses Fibonacci matrix identity, and a matrix_mul is defined first, which multiplies two square (array) matrix and save result as vector. But also fibo_3 which uses recursive method).

Project on Github: nWays

// Author : anbarief@live.com
// Since 10 March 2018

#include <iostream>
#include <string>
#include <vector>
#include <cmath>


void fibo_1(int n){

    int f[n];

    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];

    }

}

void fibo_2(int n){

    int f[n]; int index=2;

    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    while (index < n) {

        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];
        index = index + 1;

    }

}

int fibo_3(int n, int a = 0, int b = 1){

    std::cout << a << "-";

    if (n == 2){

    std::cout << b;

    return 0;

    }

    return fibo_3(n-1, b, a+b);

}

void fibo_4(int n){

    std::vector<int> f(n, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];

    }

}

void fibo_5(int n){

    std::vector<int> f(2, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        int val = f[index-1] + f[index-2];

        f.push_back(val);
        std::cout << "-" << val;

    }

}

void fibo_6(int n){

    std::vector<int> f(2, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        int val = f[index-1] + f[index-2];

        f.push_back(val);
        std::cout << "-" << f.back();

    }

}

void fibo_7(int n){

    float f[n];
    float sqr5 = std::sqrt(5);
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        f[index] = (1/sqr5)*(pow(0.5,index))*(pow(1+sqr5,index) - pow(1-sqr5,index));

        std::cout << "-" << f[index];

    }


}

void fibo_8(int n){

    float f[n];
    float sqr5 = std::sqrt(5);
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

    if (index%2==0){
        f[index] = (1/sqr5)*(pow(0.5,index))*(pow(1+sqr5,index) - pow(1-sqr5,index));
    }
    else{
        f[index] = f[index-1] + f[index-2];
    };
        std::cout << "-" << f[index];

    }

}

std::vector<int> matrix_mul(int A[2][2], int B[2][2]){
    std::vector<int> res(4,  0);

    res[0] = A[0][0]*B[0][0] + A[0][1]*B[1][0];
    res[1] = A[0][0]*B[0][1] + A[0][1]*B[1][1];
    res[2] = A[1][0]*B[0][0] + A[1][1]*B[1][0];
    res[3] = A[1][0]*B[0][1] + A[1][1]*B[1][1];

    return res;
}

void fibo_9(int n){

    float f[n];
    int A[2][2], B[2][2];
    std::vector<int> M(4,0);

    f[0] = 0; f[1] = 1; f[2] = 1;

    A[0][0] = 1; A[0][1] = 1;
    A[1][0] = 1; A[1][1] = 0;

    B[0][0] = 1; B[0][1] = 1;
    B[1][0] = 1; B[1][1] = 0;


    std::cout << f[0] << "-" << f[1] << "-" << f[2];

    for (int index = 1; index < n-2; index++){
    // 2x2 Matrix multiplication 
        M = matrix_mul(B, A);
        B[0][0] = M[0]; B[0][1] = M[1];
        B[1][0] = M[2]; B[1][1] = M[3];

        f[3] = M[0];
        std::cout << "-" << f[3]; 
    }

}


int main(){

    int n = 20;

    std::string ex_1 = "fibo_1 : Using simple for-loop and fn = fn-1 + fn-2.";
    std::cout << '\n' << ex_1 << '\n';
    fibo_1(n);

    std::string ex_2 = "fibo_2 : Similar as fibo_1, but with while-loop.";
    std::cout << '\n' << ex_2 << '\n';
    fibo_2(n);

    std::string ex_3 = "fibo_3 : Using recursive method, with backward n.";
    std::cout << '\n' << ex_3 << '\n';
    fibo_3(n);

    std::string ex_4 = "fibo_4 : Similar as fibo_1, but using vector as container.";
    std::cout << '\n' << ex_4 << '\n';
    fibo_4(n);

    std::string ex_5 = "fibo_5 : Similar as fibo_4, using f.push_back method to add new Fibo number.";
    std::cout << '\n' << ex_5 << '\n';
    fibo_5(n);

    std::string ex_6 = "fibo_6 : Similar as fibo_5, but using f.back() to show the element.";
    std::cout << '\n' << ex_6 << '\n';
    fibo_6(n);

    std::string ex_7 = "fibo_7 : Using the analytical Fibo formula.";
    std::cout << '\n' << ex_7 << '\n';
    fibo_7(n);

    std::string ex_8 = "fibo_8 : Using combination of both Analytical formula, and the ususal fn = fn-1 + fn-2.";
    std::cout << '\n' << ex_8 << '\n';
    fibo_8(n);

    std::string ex_9 = "fibo_9 : Using Matrix identity of Fibonacci numbers, Fn = A^(n) F_init.";
    std::cout << '\n' << ex_9 << '\n';
    fibo_9(n);


    return 0;
}

Answer 1

My first comment is that I did not see the most obvious way of doing. A simple recursive algorithm (Though that way does make printing them in order harder).

fibo_1

Arrays are fixed size at compile time

Dynamically sized arrays are not technically part of the standard.

int x[n];  // Not allowed unless n is `constexpr`.

Though a lot of compilers support this as an extension, its not technically part of the standard and thus best avoided in preference of using std::vector.

Memoization

ie. storing the intermediate values.
This is not really useful or efficient unless you plan on re-using the values. If you are simply using them to calculate the next value then you could potentially just use two variables (the previous two values.

    for (int index = 2; index < n; index++){    
        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];    
    }

I would rewrite like this:

    for (int index = 2; index < n; index++, f_index_minus_2 = f_index_minus_1, f_index_minus_1 = f){    
        f = f_index_minus_1 + f_index_minus_2;
        std::cout << "-" << f;    
    }

fibo_2

This is basically fib0_1 but using a while loop. Nothing against the while loop but I prefer the for(;;) loop to get the loop initialization and increment all in the same place.

fib0_3

Here you use a very complex recursion. I don't think I could have come up with that answer. So clever.

fibo_4

This is basically the same as fibo_1 but using std::vector rather than array. As such I have one less point as vector is the better structure to use here.

fibo_5

This is fibo_4 but without creating the whole array first. I prefer this over fibo_4 but to make sure you don't hit any issues with resizing the vector along your way you should reserve space for all the values.

std::vector<int> f;
f.reserve(n);
f.push_back(0);
f.push_back(1);

fibo_6

Here you simply remove an extra local variable val and explicitly use the back of the vector.

I prefer using the value. It makes the code simpler to read (and thus more expressive). It is unlikely that the variable will last into the machine code and the compiler is very likely to optimize both 5/6 into the same code.

fibo_7

This is obviously a way to calculate the factorial of a number without having to loop through all the other factorials on the way. So using it in this context just makes the code harder to read. If you are going to loop through the code just use the simple technique. This technique is perfect if you simply want to find the factorial of n without working out the other factorials.

This value never changes and is the same every time the function is called. So you can calculate it once and store it.

    float sqr5 = std::sqrt(5);

    // Write like this.
    static const sqrt5 = = std::sqrt(5);  // const non mutable.
                                          // static calculated first time the
                                          // function is called but never again.

fibo_8

Not sure why you are doing this.

fibo_9

Don't understand this at all.

I would write like this.

// Memoization separate from function.
// This means you can re-use already calculated values without
// having to do it again.
std::vector<int>   fib = {0,1}; // You can fill in more default values.

// Separate calculating the value from printing the value.
// This allows you to calculate and access the values
// without having to print a stream of numbers.
void calcFib(int n)
{
    while(fib.size() < n) {
        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }
}

// Finally printing.
// It makes sure there are enough values to print (with may do nothing)
// Then it uses standard algorithms to loop over the array and print it
// to a provided stream. Note we don't assume a stream but will default
// to std::cout if none is provided.
void printFib(int n, std::ostream& out = std::cout)
{
    if (n < 1) {
        return;
    }
    calcFib(n);

    // Print all but the last value.
    // each value suffixed by "-"
    auto end = std::next(std::begin(fib), n - 1);
    std::copy(std::begin(fib), end,
              std::ostream_iterator<int>(out, "-"));

    // Print the last value (no suffix).
    // Note: end is guaranteed in the range as we used (n-1) above
    std::cout << *end;
}

Answer 2

Your code seems to work fine and it somehow well tested (even though one needs to compare function outputs visually). A few details can be improved anyway:

Indentation and spacing

The indentation seems to be a bit off in a few places.

Also, a few blank lines seems to be in places where it is not very relevant/helpful.

Naming

Function names such as fibo_N are not very easy to understand. It would be easy to find names more meaningful such as fibo_recursive.

Useless temp variable

Using std::string ex_X variables for printing does not add much. You could just use std::cout << your_literal_string;.

At this stage, the code looks like:

// Author : anbarief@live.com
// Since 10 March 2018

#include <iostream>
#include <string>
#include <vector>
#include <cmath>


void fibo_for(int n){
    int f[n];
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];
    }
}

void fibo_while(int n){
    int f[n]; int index=2;
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    while (index < n) {
        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];
        index = index + 1;
    }
}

int fibo_recursive(int n, int a = 0, int b = 1){
    std::cout << a << "-";

    if (n == 2){
        std::cout << b;
        return 0;
    }

    return fibo_recursive(n-1, b, a+b);
}

void fibo_vector(int n){
    std::vector<int> f(n, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        f[index] = f[index-1] + f[index-2];
        std::cout << "-" << f[index];
    }
}

void fibo_push_back(int n){
    std::vector<int> f(2, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        int val = f[index-1] + f[index-2];
        f.push_back(val);
        std::cout << "-" << val;
    }
}

void fibo_push_back_then_back(int n){
    std::vector<int> f(2, 0);
    f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        int val = f[index-1] + f[index-2];
        f.push_back(val);
        std::cout << "-" << f.back();
    }
}

void fibo_analytical(int n){
    float f[n];
    float sqr5 = std::sqrt(5);
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){
        f[index] = (1/sqr5)*(pow(0.5,index))*(pow(1+sqr5,index) - pow(1-sqr5,index));
        std::cout << "-" << f[index];
    }
}

void fibo_combi_of_analytical_and_something(int n){
    float f[n];
    float sqr5 = std::sqrt(5);
    f[0] = 0; f[1] = 1;

    std::cout << f[0] << "-" << f[1];

    for (int index = 2; index < n; index++){

        if (index%2==0){
            f[index] = (1/sqr5)*(pow(0.5,index))*(pow(1+sqr5,index) - pow(1-sqr5,index));
        }
        else{
            f[index] = f[index-1] + f[index-2];
        };
        std::cout << "-" << f[index];
    }
}

std::vector<int> matrix_mul(int A[2][2], int B[2][2]){
    std::vector<int> res(4,  0);

    res[0] = A[0][0]*B[0][0] + A[0][1]*B[1][0];
    res[1] = A[0][0]*B[0][1] + A[0][1]*B[1][1];
    res[2] = A[1][0]*B[0][0] + A[1][1]*B[1][0];
    res[3] = A[1][0]*B[0][1] + A[1][1]*B[1][1];

    return res;
}

void fibo_matrix(int n){
    float f[n];
    int A[2][2], B[2][2];
    std::vector<int> M(4,0);

    f[0] = 0; f[1] = 1; f[2] = 1;

    A[0][0] = 1; A[0][1] = 1;
    A[1][0] = 1; A[1][1] = 0;

    B[0][0] = 1; B[0][1] = 1;
    B[1][0] = 1; B[1][1] = 0;


    std::cout << f[0] << "-" << f[1] << "-" << f[2];

    for (int index = 1; index < n-2; index++){
        // 2x2 Matrix multiplication 
        M = matrix_mul(B, A);
        B[0][0] = M[0]; B[0][1] = M[1];
        B[1][0] = M[2]; B[1][1] = M[3];

        f[3] = M[0];
        std::cout << "-" << f[3]; 
    }
}


int main(){
    int n = 20;

    std::cout << "\nfibo_for : Using simple for-loop and fn = fn-1 + fn-2.\n";
    fibo_for(n);

    std::cout << "\nfibo_while : Similar as fibo_for, but with while-loop.\n";
    fibo_while(n);

    std::cout << "\nfibo_recursive : Using recursive method, with backward n.\n";
    fibo_recursive(n);

    std::cout << "\nfibo_vector : Similar as fibo_for, but using vector as container.\n";
    fibo_vector(n);

    std::cout << "\nfibo_push_back : Similar as fibo_vector, using f.push_back method to add new Fibo number.\n";
    fibo_push_back(n);

    std::cout << "\nfibo_push_back_then_back : Similar as fibo_push_back, but using f.back() to show the element.\n";
    fibo_push_back_then_back(n);

    std::cout << "\nfibo_analytical : Using the analytical Fibo formula.\n";
    fibo_analytical(n);

    std::cout << "\nfibo_combi_of_analytical_and_something : Using combination of both Analytical formula, and the ususal fn = fn-1 + fn-2.\n";
    fibo_combi_of_analytical_and_something(n);

    std::cout << "\nfibo_matrix : Using Matrix identity of Fibonacci numbers, Fn = A^(n) F_init.\n";
    fibo_matrix(n);

    return 0;
}

You don't need an array

You do not need to keep track of all the computed values, only the last 2. You could write something like:

void fibo_for(int n){ 
    int prev = 0; int curr = 1; 
    std::cout << prev << "-" << curr;

    for (int index = 2; index < n; index++){
        int tmp = curr; curr+= prev; prev = tmp;
        std::cout << "-" << curr;
    }
}

This is to be completed