11

Javascript é uma linguagem que permite você escrever a mesma coisa de diversas maneiras diferentes.

A melhor resposta deve descrever os recursos de sintaxe utilizados para chegar no objetivo que é uma função mais curta possível e uma muito performática independente do seu tamanho escrito.

Para fazer medição de performance utilize o jsperf.

Deve ser utilizada a notação do livro Liber Abaci que começa em F1 = 1 omitindo F0 = 0

A função não precisa obter resultados que passem 1.7976931348623157e+308 (Number.MAX_VALUE) a pedido do usuário @PauloRoberto limitando-se a calculo em uma variável.

1
  • Por favor evitem longas discussões nos comentários; a conversa de vocês foi movida para o chat
    – Maniero
    24/02/2017 às 19:42

5 Respostas 5

7

Versão de fórmula fechada (fonte):

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

Pré-calculando a raiz e um termo fixo:

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: Algoritmo se torna impreciso devido ao arredondamento.

Exponenciação por quadratura (fonte):

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: Algoritmo mais preciso que a variação acima. Enquanto a implementação do @mgibsonbr pode ser mais rápida para números menores, na teoria esse método tem complexidade menor (log(n) vs n da solução apresentada por ele), de forma que com certeza existe um valor de n a partir do qual essa implementação se torna a mais rápida.

Duplicação rápida (fonte):

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: Também possui complexidade log(n). Como essa implementação possui natureza recursiva e cria arrays intermediários para simular tuplas, acredito que as duas implementações acima sejam mais rápidas.

Exemplo de uso:

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));
6

Usando recursividade simples

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

Usando 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];
}

Usando complexidade de espaço

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

Usando matriz

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];
}

Usando matriz com alimentação recursiva

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 com os exemplos

Adicionei no jsfiddle o script que o @MiguelAngelo informou. Esse algorítimo 'estoura' para o número "máximo" (que o js aceita), podemos concluir que o valor gerado é diferente (talvez pela precisão do PI e desse inverseSqrt5), porém, para números menores ele funciona perfeitamente, e provavelmente será muito mais rápido. ("travei" o algoritmo recursivo para não travar o browser).

Referências:
http://www.ics.uci.edu/~eppstein/161/960109.html http://pt.wikipedia.org/wiki/Sequ%C3%AAncia_de_Fibonacci http://en.wikipedia.org/wiki/Fibonacci_number

5

Uma forma bem curtinha de calcular

Essa é a forma mais curta que eu achei, que não usa recursão.

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

Se colocar em uma linha: function fib(n){var a=1,b=1;while(--n)a=b+(b=a);return b;}

Resolvendo em tempo linear

Para números grandes, essa deve ser a forma mais rápida de se resolver. Não sei entretanto qual é a linha divisória.

var inverseSqrt5 = 0.44721359549995793928183473374626;
var phi = 1.6180339887498948482045868343656;
function fib(n)
{
    return Math.floor(Math.pow(phi, n) * inverseSqrt5 + 0.5);
}
6
  • Tempo linear? Você não quer dizer tempo logarítmico? Sua primeira função é O(n) (o número de iterações do loop varia linearmente com o tamanho da entrada), a segunda é O(log n) (não há loops, mas o Math.pow - se bem implementado - vai depender do logaritmo do expoente).
    – mgibsonbr
    21/03/2014 às 0:02
  • A segunda forma é O(1), tempo constante, creio eu
    – epx
    21/03/2014 às 2:47
  • @epx Depende da interpretação. Se você considera Math.pow [e Math.floor] como operações "atômicas", então é mesmo O(1) - pois o número de operações é o mesmo não importa qual o tamanho da entrada (1 soma, 1 multiplicação e 2 chamadas de função). Mas se você considera o que essas funções estão fazendo por baixo dos panos, então elas contam pra análise. Um Math.pow ineficiente (ex.: que implemente a^b como a*a*a*...*a) faria com que a função tivesse O(n). Mas um eficiente poderia fazer a mesma operação em O(log n)
    – mgibsonbr
    21/03/2014 às 9:36
  • 1
    @mgibsonbr: esse algoritmo de pow da Sun é bem conhecido... não tem nenhum loop, então acho que poderiamos dizer que o tempo pode ser linear, dependendo da implementação da função pow. 21/03/2014 às 12:51
  • @Miguel a principal limitação aqui é o hardware, sem hardware especializado realmente as implementações mais rápidas para Math.pow são de complexidade log(n). A principal vantagem da fórmula fechada é que é bem óbvio para o motor de JavaScript que essa é uma operação que dada a mesma entrada retorna o mesmo resultado, de maneira que é possível "roubar" cacheando os resultados (assim como as implementações com memoização estão fazendo explicitamente). 21/03/2014 às 14:13
4

Curta eu não sei, mas performática com certeza é algo desse tipo:

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

Exemplo no jsFiddle. Não medi a performance, mas se a entrda for até 1.000.000 (1 milhão) ele responde instantaneamente (Infinity:P). 1.000.000.000 (1 bilhão) leva alguns segundos, e acima disso seu script vai parar de responder por muito, muito tempo... (mas não vai "travar" - se você tiver paciência!) Testado no Chrome.

Recursos de sintaxe utilizados

Apenas um loop... Dadas duas variáveis a e b (inicialmente atribuídas para 1 e 1 - os dois primeiros elementos da sequência de fibonacci), obter o próximo elemento é só uma questão de somar a + b. Como o elemento depois desse é b + (a+b), então descartamos o a (que não será mais usado) e guardamos o valor antigo de b em a. Uma variável temporária é usada para fazer a troca:

a, b = b, a + b

Já que é simples, não usa nenhum recurso pesado como a chamada de outra função, então a performance é excelente. No fim, todo o cálculo é feito com apenas 4 valores na memória, de modo que tudo o que é preciso está na cache - não há criação nem destruição de objetos, operações na pilha, nem nada desse tipo.

Quando ao resultado, usei o Number comum, mas se for necessário maior precisão basta usar uma biblioteca de "BigInteger".


Atualização: Colocando a função numa forma mais prática (sim, estou à toa hoje...):

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

Exemplo usando sequencia. (Alguém poderia argumentar que isso usa muita memória, mas o limite da representação em JavaScript - fib(102) - chega muito mais rápido do que o consumo excessivo de memória)

2
  • P.S. Na sua pergunta não está claro se você quer a sequência de fibonacci (i.e. todos os elementos [até um limiar]), a série (i.e. a soma dos elmentos da sequência) ou o n-ésimo elemento. Respondi assumindo o n-ésimo, mas o código é facilmente adaptável para os demais casos.
    – mgibsonbr
    20/03/2014 às 18:03
  • +1 a questão de escrever ela de forma curta seria mais focada apenas na sequência, já a mais performática seria pro n-ésimo elemento conforme vc fez e está excelente. 20/03/2014 às 21:11
2

As formas mais curtas que eu cheguei foram:

Função recursiva:

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

No caso estou usando o retorno direto e aplicando um operador condicional para testar se o valor é menor que 3 para retornar 1 e senão ele aplica o calculo recursivo.

Dessa maneira da pra eliminar a virgula, declaração de variáveis ou sintaxes muito expressivas. Porém o desempenho é um dos piores possíveis.

Função com cache em variáveis:

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

Neste caso usei o mesmo recurso de operador condicional, porém inclui também um teste para ver se as variáveis a existe e depois b mudando a formula do calculo para utilizar o cache se este estiver disponível.

A mesma função pode ser escrita da seguinte maneira:

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;
}

Função com cache em Array:

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

Primeiro eu testo utilizando | (operador bitwise or) para ver se a variável c que representa o cache existe, se ela existe, utilizo ela mesmo, caso não exista ela passa receber como valor uma nova array.

No calculo, será verificado se existe um valor em cache antes de qualquer coisa, não existindo nada no cache, vai verificar se o valor é menor que 3 para retornar 1 ou tentar recursivamente aplicar a mesma função.

Para ter um melhor aproveitamento do cache é possível adapta-la desta maneira:

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

Neste caso o cache está sendo armazenado como propriedade da função, podendo ser re-aproveitada nas próximas vezes em que a função for executada, não tendo que re-calcular os valores já adicionados no cache.

Uma forma para melhor leitura desta função seria:

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=[];

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .