# Algorithms for Fibonacci numbers

Fibonacci numbers form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones.

The beginning of the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

The calculation formula for the number n: Fn = Fn - 1 + Fn - 2, for n > 1

Initially defined: F0 = 0, F1 = 1

The 4 implementations are listed below. From the slowest to the fastest. The source code in the repository alik0211/fibonacci.

## 1. Recursive implementation

Time complexity: O(n2)

The first solution that comes to mind is to write a recursive function. Recursion forms a large call tree, so the complexity of the algorithm is O(n2). Read more in the answer to stackoverflow.

Code from recursion.js:

``````function F(n) {
if (n < 2) {
return n;
}

return F(n - 1) + F(n - 2);
}``````

## 2. Sequential realization

Time complexity: O(n)

Code from sequential.js:

``````function F(n) {
const numbers = [0, 1];

for (let i = 2; i <= n; i++) {
numbers[i] = numbers[i - 1] + numbers[i - 2];
}

return numbers[n];
}``````

## 3. Exponentiation of a binary matrix

Time complexity: O(log n)

This solution is based on binary exponentiation. This is a good example to show: if there is a lot of code, it does not mean that it is slow.

Code from matrix.js:

``````function BinMatrix(a, b) {
this.matrix = [a, b];

return this;
}

BinMatrix.prototype.pow = function(n) {
const res = [[1, 0], [0, 1]];

while (n) {
if (n & 1) {
this.mul(res);
}

this.mul(this.matrix);
n >>= 1;
}

this.copy(res, this.matrix);
};

BinMatrix.prototype.mul = function(rhs) {
const res = [[0, 0], [0, 0]];

for (let i = 0; i < 2; ++i) {
for (let j = 0; j < 2; ++j) {
for (let k = 0; k < 2; ++k) {
res[i][j] += this.matrix[i][k] * rhs[k][j];
}
}
}

this.copy(res, rhs);
};

BinMatrix.prototype.copy = function(lhs, rhs) {
for (let i = 0; i < 2; ++i) {
for (let j = 0; j < 2; ++j) {
rhs[i][j] = lhs[i][j];
}
}
};

function F(n) {
const matrixInstance = new BinMatrix([0, 1], [1, 1]);

matrixInstance.pow(n);

return matrixInstance.matrix;
}``````

## 4. Formula

Time complexity: O(1)

The most amazing and most boring solution.

Fn = ((√5 + 1) / 2)n / √5

Code from formula.js:

``````function F(n) {
return Math.round(
((Math.sqrt(5) + 1) / 2) ** n / Math.sqrt(5)
);
}``````

## Literature used:

1. Concrete Mathematics: A Foundation for Computer Science (1988)