What is the shortest and most performative way of writing fibonnaci in Javascript?

10

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

The best answer should describe the syntax features used to arrive at the goal which is a shortest possible function and a very performative one regardless of its written size.

To make performance measurement use jsperf .

The book's rating should be used Liber Abaci starting at F 1 = 1 omitting F 0 = 0

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

    
asked by anonymous 20.03.2014 / 17:27

5 answers

5
A very short way to calculate

This is the shortest way I found, which does not use recursion.

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

If you 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 quickest way to resolve. I do not know what the dividing line is.

var inverseSqrt5 = 0.44721359549995793928183473374626;
var phi = 1.6180339887498948482045868343656;
function fib(n)
{
    return Math.floor(Math.pow(phi, n) * inverseSqrt5 + 0.5);
}
    
20.03.2014 / 21:26
5

Using simple recursion

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 space complexity

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

Using array

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 examples

  

I added the jsfiddle script that @MiguelAngelo reported. This algorithm 'burst out' to the 'maximum' number (which js accepts), we can conclude that the generated value is different (perhaps by the precision of the PI and that of inverseSqrt5), but for smaller numbers it works perfectly, faster. ("travei" the recursive algorithm to not stop the browser).

References:
link link link

    
20.03.2014 / 22:48
5

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;

Note: 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 accurate than the above variation. While the @mgibsonbr implementation may be faster for smaller numbers, in theory this method has less complexity (% with% vs% with% of solution presented by it), so there is certainly a value of log(n) from of which this implementation becomes the fastest.

Rapid duplication ( 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;

Note: Also has n complexity. Since this implementation is recursive in nature and creates n intermediates to simulate tuples, I believe the two implementations above are faster.

Example usage:

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));
    
21.03.2014 / 01:30
4

Short I do not know, but performatica certainly is something like this:

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 did not measure the performance, but if the input is up 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 will not "hang" - if you have patience!) Tested on Chrome.

Syntax Features Used

Only one loop ... Given two variables a and b (initially assigned to 1 and 1 - the first two elements of the fibonacci sequence), getting the next element is just a matter of add a + b . Since the element after that is b + (a+b) , then we discard a (which will no longer be used) and save the old value from b to a . A temporary variable is used to make the change:

a, b = b, a + b

Since it's simple, it does not use any heavy features like calling another function, so the performance is great. In the end, all computation is done with only 4 values in memory, so everything that is needed is in the cache - there is no creation or destruction of objects, operations on the heap, or anything like that.

When using the result, I have used the Number pendent%, but if greater precision is needed, just use a "BigInteger" library.

Update: Placing the function in a more practical way (yes, I'm at it 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 the JavaScript representation - fib(102) - arrives much faster than excessive memory consumption)

    
20.03.2014 / 18:22
2

The shortest forms I came up with were:

Recursive function:

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

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

This way you can eliminate the comma, declaration of variables or very expressive syntaxes. But performance is one of the worst.

Cached function in variables:

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 resource, but also includes a test to see if a exists and then b by 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;
}

Array Cache Function:

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 c variable that represents the cache exists, if it exists, I use it myself, if it does not, it receives 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 try to recursively apply the same function.

To get a better use of the cache you can adapt it in 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 a property of the function, and can be reused in the next few times when the function is executed, not having to re-calculate the values already added in the cache.

One 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=[];
    
20.03.2014 / 21:59