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)

About this method is usually told at one of the first lectures on dynamic programming.

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[0][1];
}

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)