What is the shortest and most performative way to write Fibonnaci in Javascript?

Question

Javascript is a language that allows you to write the same thing in several different ways.

The best answer should describe the syntax resources used to reach the goal which is a shorter function possible and a very performative independent of its written size.

To measure performance use the jsperf.

The book notation shall be used Liber Abaci which starts in F₁ = 1 omitting F₀ = 0

The function does not need to get results that pass 1.7976931348623157e+308 (Number.MAX_VALUE) at the request of the user @Pauloroberto limiting itself to calculation in a variable.

Answer 1

Closed formula version (source):

function fib(n) {
  var sqrt5 = Math.sqrt(5);
  return Math.round(Math.pow(((1 + sqrt5) / 2), n) / sqrt5);
}

Pre-calculating the root and a fixed term:

function ClosedForm() {
    var sqrt5 = Math.sqrt(5);
    var term =  (1 + sqrt5) / 2
    this.impl = function (n) {
        return Math.round(Math.pow(term, n) / sqrt5);
    }
};

var fib = new ClosedForm().impl;

Obs: Algorithm becomes inaccurate due to rounding.

Exponentiation by quadrature (source):

function fib(n) {
    var i = n - 1, a = 1, b = 0, c = 0, d = 1, t;
    while (i > 0) {
        while (i % 2 === 0) {
            t = d * (2 * c + d);
            c = c * c + d * d;
            d = t;
            i = i / 2;
        }
        t = d * (b + a) + c * b;
        a = d * b + c * a;
        b = t;
        i--;
    }
    return a + b;
}

Obs: Algorithm more precise than the above variation. While the implementation of @mgibsonbr may be faster for smaller numbers, in theory this method has less complexity (log(n) vs n of the solution presented by him), so that for sure there is a value of n from which this implementation becomes the fastest.

Fast doubling (source):

function FastDoubling() {
    this.impl = function (n) {
        return aux(n - 1)[1];
    }
    function aux(n) {
        if (n <= 0) {
            return [0, 1];
        } else {
            var ab = aux(Math.floor(n / 2));
            var a = ab[0], b = ab[1];
            var c = a * (2 * b - a);
            var d = b * b + a * a;
            if (n % 2 === 0) {
                return [c, d];
            } else {
                return [d, c + d];
            }
        }
    }
}

var fib = new FastDoubling().impl;

Obs: Also has complexity log(n). How this implementation has recursive nature and creates arrays intermediate to simulate tuples, I believe the above two implementations are faster.

Example of use:

for (var i = 1; i <= 10; i++) {
    console.log("fib(" + i + ") = " + fib(i));
}
// Último valor dentro do limite estabelecido
console.log("fib(1476) = " + fib(1476));

Answer 2

A very short way of calculating

This is the shortest form I’ve found that doesn’t use recursion.

function fib(n){
    var a=1,b=1;
    while(--n)a=b+(b=a);
    return b;
}

If put in a line: function fib(n){var a=1,b=1;while(--n)a=b+(b=a);return b;}

Solving in linear time

For large numbers, this should be the fastest way to resolve. I don’t know however which is the dividing line.

var inverseSqrt5 = 0.44721359549995793928183473374626;
var phi = 1.6180339887498948482045868343656;
function fib(n)
{
    return Math.floor(Math.pow(phi, n) * inverseSqrt5 + 0.5);
}

Answer 3

Using simple recursiveness

function fib1(n) {
    if (n < 2) return n;
    return fib1(n - 1) + fib1(n - 2);
}

Using array

function fib2(n) {
    var i, f = [0, 1];
    for (i = 2; i <= n; i++) f.push(f[i - 1] + f[i - 2]);
    return f[n];
}

Using complexity of space

function fib3(n) {
    var i = 1, j = 0, t = j, k = i;
    for (; k++ <= n; j = (t = i + (i = j)));
    return j;
}

Using matrix

function fib4(n) {
    var F = [[1, 1], [1, 0]];
    if (n <= 0) return 0;
    for (var i = 2; i <= (n - 1); i++)
    F = [
        [F[0][0] + F[0][1], F[0][0]],
        [F[1][0] + F[1][1], F[1][0]]
    ]

    return F[0][0];
}

Using matrix with recursive feed

function fib5(n) {
    if (n == 0) return 0;
    var F = [[1, 1],[1, 0]];

    function exec(i) {
        if (i == 0 || i == 1) return;
        exec(parseInt(i / 2));
        F = [
            [F[0][0] * F[0][0] + F[0][1] * F[1][0], F[0][0] * F[0][1] + F[0][1] * F[1][1]],
            [F[1][0] * F[0][0] + F[1][1] * F[1][0], F[1][0] * F[0][1] + F[1][1] * F[1][1]]
        ];
        if (i % 2 != 0) F = [
            [F[0][0] + F[0][1], F[0][0]],
            [F[1][0] + F[1][1], F[1][0]]
        ]
    }
    exec(n - 1);
    return F[0][0];
}

Jsfiddle with the examples

I added in the jsfiddle the script that @Miguelangelo reported. This algorithm 'overflows' for the "maximum" number (which js accepts), we can conclude that the generated value is different (perhaps by the accuracy of the PI and this inverseSqrt5), however, for smaller numbers it works perfectly, and will probably be much faster. (I "locked" the recursive algorithm to not lock the browser).

References:
http://www.ics.uci.edu/~Eppstein/161/960109.html http://en.wikipedia.org/wiki/Fibonacci_sequence http://en.wikipedia.org/wiki/Fibonacci_number

Answer 4

Short I don’t know, but performative for sure is something like that:

function fib(n) {
    var a = 1;
    var b = 1;
    var temp;
    while ( n > 2 ) {
        temp = b;
        b = a + b;
        a = temp;
        n--;
    }
    return b;
}

Example in jsFiddle. I didn’t measure the performance, but if the entrance is to 1.000.000 (1 million) it responds instantly (Infinity:P). 1.000.000.000 (1 billion) takes a few seconds, and above that your script will stop responding for a long, long time... (but it won’t "hang" - if you have patience! ) Tested in Chrome.

Syntax resources used in

Just a loop... Given two variables a and b (initially allocated to 1 and 1 - the first two elements of the Fibonacci sequence), getting the next element is just a matter of summing a + b. As the element after that is b + (a+b), then we discard the a (that will no longer be used) and we keep the old value of b in a. A temporary variable is used to make the exchange:

a, b = b, a + b

Since it is simple, it does not use any heavy feature as the call of another function, so the performance is excellent. In the end, all calculation is done with just 4 values in memory, so everything you need is in the cache - there is no creation or destruction of objects, stack operations, or anything like that.

As for the result, I used the Number common, but if more precision is needed just use a library of "Biginteger".

---

Updating: Putting function in a more practical way (yes, I’m not sure today...):

var fib = function(classe, soma) {
    var sequencia = [new classe(1), new classe(1)];
    var serie = [new classe(1), new classe(2)];

    function atualiza(n) {
        var len = sequencia.length;
        while ( n > len ) {
            sequencia.push(soma(sequencia[len-1], sequencia[len-2]));
            serie.push(soma(serie[len-1], sequencia[len]));
            len++;
        }
    }

    return {
        n_esimo:function(n)   { atualiza(n); return sequencia[n-1];       },
        sequencia:function(n) { atualiza(n); return sequencia.slice(0,n); },
        serie:function(n)     { atualiza(n); return serie[n-1];           }
    }
};

var fibn = fib(Number, function(a,b) { return new Number(a + b); }); // Usando Number
var bigfib = fib(BigInteger, function(a,b) { ... }); // Usando uma biblioteca de BigInteger

Example using sequencia. (One could argue that this uses a lot of memory, but the limit of representation in Javascript - fib(102) - arrives much faster than excessive memory consumption)

Answer 5

The shortest ways I got were:

Recursive function:

function f(n){return n<3?1:f(n-1)+f(n-2)}

In case I am using direct return and applying a conditional operator to test if the value is less than 3 to return 1 and else it applies the recursive calculation.

This way you can eliminate the comma, variable declaration or very expressive syntax. But performance is one of the worst possible.

Function with variable cache:

function f(n,a,b){return n<3?1:!a?f(n-1)+f(n-2):!b?f(n-1)+a:a+b}

In this case I used the same conditional operator feature, but it also includes a test to see if the variables a exists and then b changing the calculation formula to use the cache if it is available.

The same function can be written as follows:

function f(n,a,b){
  if (n < 3) return 1;
  if (typeof a === 'undefined') return f(n - 1) + f(n - 2);
  if (typeof b === 'undefined') return f(n-1)+a;
  return a+b;
}

Function with Array Cache:

function f(n,c){c=c|[];return !c[n]?c[n]=n<3?1:f(n-1,c)+f(n-2,c):c[n]}

First I test using | (bitwise operator or) to see if the variable c that represents the cache exists, if it exists, I use it itself, if it does not exist it will receive a new array as value.

In the calculation, it will be checked if there is a cached value before anything, there is nothing in the cache, it will check if the value is less than 3 to return 1 or recursively try to apply the same function.

To have a better use of the cache it is possible to adapt it this way:

function f(n){return !f.c[n]?f.c[n]=n<3?1:f(n-1)+f(n-2):f.c[n]};f.c=[];

In this case the cache is being stored as property of the function and can be reused the next times the function is executed, not having to recalculate the values already added in the cache.

A way to better read this function would be:

function f(n) {
  if (typeof f.cache[n] === 'undefined') {
    if (n < 3) {
      f.cache[n] = 1;
      return f.cache[n];
    }
    f.cache[n] = f(n - 1) + f(n - 2)
    return f.cache[n];
  }
  return f.cache[n];
}
f.cache=[];