Javascript Fibonacci nième terme Optimisation

Question

Je me suis intéressé récemment aux algorithmes, et la séquence de fibonacci a attiré mon attention en raison de sa simplicité.

J'ai réussi à mettre quelque chose en javascript qui calcule le nième terme dans la séquence de fibonacci en moins de 15 millisecondes après avoir lu beaucoup d'informations sur le web. Il va jusqu'à 1476 ... 1477 est l'infini et 1478 est NaN (selon javascript!)

Je suis assez fier du code lui-même, sauf que c'est un monstre absolu. Voici donc ma question: A) Y a-t-il un moyen plus rapide de calculer la séquence? B) existe-t-il un moyen plus rapide/plus petit de multiplier deux matrices?

Voici le code:

//Fibonacci sequence generator in JS 
//Cobbled together by Salty 
m = [[1,0],[0,1]]; 
odd = [[1,1],[1,0]]; 
function matrix(a,b) { 
    /* 
     Matrix multiplication 
     Strassen Algorithm 
     Only works with 2x2 matrices. 
    */ 
    c=[[0,0],[0,0]]; 
    c[0][0]=(a[0][0]*b[0][0])+(a[0][1]*b[1][0]); 
    c[0][1]=(a[0][0]*b[0][1])+(a[0][1]*b[1][1]); 
    c[1][0]=(a[1][0]*b[0][0])+(a[1][1]*b[1][0]); 
    c[1][1]=(a[1][0]*b[0][1])+(a[1][1]*b[1][1]); 
    m1=(a[0][0]+a[1][1])*(b[0][0]+b[1][1]); 
    m2=(a[1][0]+a[1][1])*b[0][0]; 
    m3=a[0][0]*(b[0][1]-b[1][1]); 
    m4=a[1][1]*(b[1][0]-b[0][0]); 
    m5=(a[0][0]+a[0][1])*b[1][1]; 
    m6=(a[1][0]-a[0][0])*(b[0][0]+b[0][1]); 
    m7=(a[0][1]-a[1][1])*(b[1][0]+b[1][1]); 
    c[0][0]=m1+m4-m5+m7; 
    c[0][1]=m3+m5; 
    c[1][0]=m2+m4; 
    c[1][1]=m1-m2+m3+m6; 
    return c; 
} 
function fib(n) { 
    mat(n-1); 
    return m[0][0]; 
} 
function mat(n) { 
    if(n > 1) { 
     mat(n/2); 
     m = matrix(m,m); 
    } 
    m = (n%2<1) ? m : matrix(m,odd); 
} 
alert(fib(1476)); //Alerts 1.3069892237633993e+308 

La fonction de matrice prend deux arguments: a et b, et renvoie a * b où a et b sont des tableaux 2x2. Oh, et sur une note de côté, une chose magique s'est produite ... Je convertissais l'algorithme de Strassen en notation de tableau JS et cela a fonctionné lors de mon premier essai! Fantastique, non? : P

Merci d'avance si vous parvenez à trouver un moyen plus facile de le faire.

Answer 1

Ne pas spéculer, référence:

modifier: Je ajouté ma propre mise en œuvre de la matrice en utilisant les fonctions de multiplication optimisées mentionnées dans mon autre réponse. Cela a entraîné une accélération majeure, mais même la mise en œuvre de la multiplication matricielle avec des boucles de vanille O (n^3) était plus rapide que l'algorithme de Strassen.

<pre><script> 

var fib = {}; 

(function() { 
    var sqrt_5 = Math.sqrt(5), 
     phi  = (1 + sqrt_5)/2; 

    fib.round = function(n) { 
     return Math.floor(Math.pow(phi, n)/sqrt_5 + 0.5); 
    }; 
})(); 

(function() { 
    fib.loop = function(n) { 
     var i = 0, 
      j = 1; 

     while(n--) { 
      var tmp = i; 
      i = j; 
      j += tmp; 
     } 

     return i; 
    }; 
})(); 

(function() { 
    var cache = [0, 1]; 

    fib.loop_cached = function(n) { 
     if(n >= cache.length) { 
      for(var i = cache.length; i <= n; ++i) 
       cache[i] = cache[i - 1] + cache[i - 2]; 
     } 

     return cache[n]; 
    }; 
})(); 

(function() { 
    //Fibonacci sequence generator in JS 
    //Cobbled together by Salty 
    var m; 
    var odd = [[1,1],[1,0]]; 

    function matrix(a,b) { 
     /* 
      Matrix multiplication 
      Strassen Algorithm 
      Only works with 2x2 matrices. 
     */ 
     var c=[[0,0],[0,0]]; 
     var m1=(a[0][0]+a[1][1])*(b[0][0]+b[1][1]); 
     var m2=(a[1][0]+a[1][1])*b[0][0]; 
     var m3=a[0][0]*(b[0][1]-b[1][1]); 
     var m4=a[1][1]*(b[1][0]-b[0][0]); 
     var m5=(a[0][0]+a[0][1])*b[1][1]; 
     var m6=(a[1][0]-a[0][0])*(b[0][0]+b[0][1]); 
     var m7=(a[0][1]-a[1][1])*(b[1][0]+b[1][1]); 
     c[0][0]=m1+m4-m5+m7; 
     c[0][1]=m3+m5; 
     c[1][0]=m2+m4; 
     c[1][1]=m1-m2+m3+m6; 
     return c; 
    } 

    function mat(n) { 
     if(n > 1) { 
      mat(n/2); 
      m = matrix(m,m); 
     } 
     m = (n%2<1) ? m : matrix(m,odd); 
    } 

    fib.matrix = function(n) { 
     m = [[1,0],[0,1]]; 
     mat(n-1); 
     return m[0][0]; 
    }; 
})(); 

(function() { 
    var a; 

    function square() { 
     var a00 = a[0][0], 
      a01 = a[0][1], 
      a10 = a[1][0], 
      a11 = a[1][1]; 

     var a10_x_a01 = a10 * a01, 
      a00_p_a11 = a00 + a11; 

     a[0][0] = a10_x_a01 + a00 * a00; 
     a[0][1] = a00_p_a11 * a01; 
     a[1][0] = a00_p_a11 * a10; 
     a[1][1] = a10_x_a01 + a11 * a11; 
    } 

    function powPlusPlus() { 
     var a01 = a[0][1], 
      a11 = a[1][1]; 

     a[0][1] = a[0][0]; 
     a[1][1] = a[1][0]; 
     a[0][0] += a01; 
     a[1][0] += a11; 
    } 

    function compute(n) { 
     if(n > 1) { 
      compute(n >> 1); 
      square(); 
      if(n & 1) 
       powPlusPlus(); 
     } 
    } 

    fib.matrix_optimised = function(n) { 
     if(n == 0) 
      return 0; 

     a = [[1, 1], [1, 0]]; 
     compute(n - 1); 

     return a[0][0]; 
    }; 
})(); 

(function() { 
    var cache = {}; 
    cache[0] = [[1, 0], [0, 1]]; 
    cache[1] = [[1, 1], [1, 0]]; 

    function mult(a, b) { 
     return [ 
      [a[0][0] * b[0][0] + a[0][1] * b[1][0], 
       a[0][0] * b[0][1] + a[0][1] * b[1][1]], 
      [a[1][0] * b[0][0] + a[1][1] * b[1][0], 
       a[1][0] * b[0][1] + a[1][1] * b[1][1]] 
     ]; 
    } 

    function compute(n) { 
     if(!cache[n]) { 
      var n_2 = n >> 1; 
      compute(n_2); 
      cache[n] = mult(cache[n_2], cache[n_2]); 
      if(n & 1) 
       cache[n] = mult(cache[1], cache[n]); 
     } 
    } 

    fib.matrix_cached = function(n) { 
     if(n == 0) 
      return 0; 

     compute(--n); 

     return cache[n][0][0]; 
    }; 
})(); 

function test(name, func, n, count) { 
    var value; 

    var start = Number(new Date); 
    while(count--) 
     value = func(n); 
    var end = Number(new Date); 

    return 'fib.' + name + '(' + n + ') = ' + value + ' [' + 
     (end - start) + 'ms]'; 
} 

for(var func in fib) 
    document.writeln(test(func, fib[func], 1450, 10000)); 

</script></pre> 

cède

fib.round(1450) = 4.8149675025003456e+302 [20ms] 
fib.loop(1450) = 4.81496750250011e+302 [4035ms] 
fib.loop_cached(1450) = 4.81496750250011e+302 [8ms] 
fib.matrix(1450) = 4.814967502500118e+302 [2201ms] 
fib.matrix_optimised(1450) = 4.814967502500113e+302 [585ms] 
fib.matrix_cached(1450) = 4.814967502500113e+302 [12ms] 

Votre algorithme est presque aussi mauvais que looping uncached. La mise en cache est votre meilleur pari, suivie de près par l'algorithme d'arrondi - qui donne des résultats incorrects pour les gros n (tout comme votre algorithme de matrice).

Pour les plus petits n, votre algorithme effectue encore pire que tout le reste:

fib.round(100) = 354224848179263100000 [20ms] 
fib.loop(100) = 354224848179262000000 [248ms] 
fib.loop_cached(100) = 354224848179262000000 [6ms] 
fib.matrix(100) = 354224848179261900000 [1911ms] 
fib.matrix_optimised(100) = 354224848179261900000 [380ms] 
fib.matrix_cached(100) = 354224848179261900000 [12ms] 

Answer 2

Il existe une solution de forme fermée (sans boucles) pour le nième nombre de Fibonacci.

See Wikipedia.

Answer 3

Que diriez-vous memoizing les résultats que lorsque déjà calculé, comme par exemple:

var IterMemoFib = function() { 
    var cache = [1, 1]; 
    var fib = function(n) { 
     if (n >= cache.length) { 
      for (var i = cache.length; i <= n; i++) { 
       cache[i] = cache[i - 2] + cache[i - 1]; 
      } 
     } 
     return cache[n]; 
    } 

    return fib; 
}(); 

Ou si vous voulez une fonction memoization plus générique, étendez le prototype Function:

Function.prototype.memoize = function() { 
    var pad = {}; 
    var self = this; 
    var obj = arguments.length > 0 ? arguments[i] : null; 

    var memoizedFn = function() { 
     // Copy the arguments object into an array: allows it to be used as 
     // a cache key. 
     var args = []; 
     for (var i = 0; i < arguments.length; i++) { 
      args[i] = arguments[i]; 
     } 

     // Evaluate the memoized function if it hasn't been evaluated with 
     // these arguments before. 
     if (!(args in pad)) { 
      pad[args] = self.apply(obj, arguments); 
     } 

     return pad[args]; 
    } 

    memoizedFn.unmemoize = function() { 
     return self; 
    } 

    return memoizedFn; 
} 

//Now, you can apply the memoized function to a normal fibonacci function like such: 
Fib = fib.memoize(); 

Une note à ajouter est qu'en raison de contraintes techniques (sécurité du navigateur), les arguments pour les fonctions mémorisées ne peuvent être que des tableaux ou des valeurs scalaires. Aucun objet

Référence: http://talideon.com/weblog/2005/07/javascript-memoization.cfm

Answer 4

Il peut y avoir un moyen plus rapide pour calculer les valeurs, mais je ne crois pas qu'il soit nécessaire.

Calculez une fois, dans votre programme, la sortie des résultats que la ligne fibdata ci-dessous:

fibdata = [1,1,2,3,5,8,13, ... , 1.3069892237633993e+308]; // 1476 entries. 
function fib(n) { 
    if ((n < 0) || (n > 1476)) { 
     ** Do something exception-like or return INF; 
    } 
    return fibdata[n]; 
} 

Ensuite, c'est le code que vous livrez à vos clients. C'est une solution O (1) pour vous.

Les gens oublient souvent la solution de 'mise en cache'. Une fois, j'ai dû écrire des routines de trigonométrie pour un système embarqué et, plutôt que d'utiliser des séries infinies pour les calculer à la volée, j'avais juste quelques tables de recherche, 360 entrées dans chacun des degrés d'entrée. Inutile de dire, il a hurlé le long, au prix d'environ 1K de RAM seulement. Les valeurs ont été stockées sous la forme d'entrées de 1 octet, [valeur réelle (0-1) * 16], ce qui nous a permis d'effectuer une recherche, une multiplication et un décalage de bit pour obtenir la valeur souhaitée.

Answer 5

Pour développer un peu sur la réponse de Dreas:

1) cache devrait commencer [0, 1]
2) que faites-vous avec IterMemoFib(5.5)? (cache[5.5] == undefined)

fibonacci = (function() { 
    var FIB = [0, 1]; 

    return function (x) { 
    if ((typeof(x) !== 'number') || (x < 0)) return; 
    x = Math.floor(x); 

    if (x >= FIB.length) 
     for (var i = FIB.length; i <= x; i += 1) 
     FIB[i] = FIB[i-1] + FIB[i-2]; 

    return FIB[x]; 
    } 
})(); 

alert(fibonacci(17)); // 1597 (FIB => [0, 1, ..., 1597]) (length = 17) 
alert(fibonacci(400)); // 1.760236806450138e+83 (finds 18 to 400) 
alert(fibonacci(1476)); // 1.3069892237633987e+308 (length = 1476) 

---

Si vous ne l'aimez pas les erreurs silencieuses:

// replace... 
if ((typeof(x) !== 'number') || (x < 0)) return; 

// with... 
if (typeof(x) !== 'number') throw new TypeError('Not a Number.'); 
if (x < 0) throw new RangeError('Not a possible fibonacci index. (' + x + ')'); 

Answer 6

Ma réponse précédente a un peu trop de monde, donc je posterai une nouvelle:

Vous pouvez accélérer votre algorithme en utilisant la multiplication de matrices 2x2 de vanille - par exemple remplacer votre fonction matrix() avec ceci:

function matrix(a, b) { 
    return [ 
     [a[0][0] * b[0][0] + a[0][1] * b[1][0], 
      a[0][0] * b[0][1] + a[0][1] * b[1][1]], 
     [a[1][0] * b[0][0] + a[1][1] * b[1][0], 
      a[1][0] * b[0][1] + a[1][1] * b[1][1]] 
    ]; 
} 

Si vous aimez ACCU racé et la vitesse, utilisez la solution de mise en cache. Si la précision n'est pas une préoccupation, mais la consommation de mémoire est, utilisez la solution d'arrondi. La solution matricielle n'a de sens que si vous voulez des résultats rapides, ne vous souciez pas de la précision et ne voulez pas appeler la fonction à plusieurs reprises.

modifier: Vous pouvez même accélérer encore le calcul si vous utilisez des fonctions de multiplication spécialisées, éliminer les sous-expressions communes et remplacer les valeurs dans le tableau existant au lieu de créer un nouveau tableau:

function square() { 
    var a00 = a[0][0], 
     a01 = a[0][1], 
     a10 = a[1][0], 
     a11 = a[1][1]; 

    var a10_x_a01 = a10 * a01, 
     a00_p_a11 = a00 + a11; 

    a[0][0] = a10_x_a01 + a00 * a00; 
    a[0][1] = a00_p_a11 * a01; 
    a[1][0] = a00_p_a11 * a10; 
    a[1][1] = a10_x_a01 + a11 * a11; 
} 

function powPlusPlus() { 
    var a01 = a[0][1], 
     a11 = a[1][1]; 

    a[0][1] = a[0][0]; 
    a[1][1] = a[1][0]; 
    a[0][0] += a01; 
    a[1][0] += a11; 
} 

Note: a est le nom de la variable matricielle globale.

Answer 7

Voici une solution très rapide de calculer la séquence de fibonacci

function fib(n){ 
    var start = Number(new Date); 
    var field = new Array(); 
    field[0] = 0; 
    field[1] = 1; 
    for(var i=2; i<=n; i++) 
     field[i] = field[i-2] + field[i-1] 
    var end = Number(new Date); 
    return 'fib' + '(' + n + ') = ' + field[n] + ' [' + 
     (end - start) + 'ms]'; 

} 

var f = fib(1450) 
console.log(f) 

Answer 8

solution forme fermée en JavaScript:

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

Certes, même la multiplication commence à prendre ses frais lorsqu'ils traitent avec des chiffres énormes, mais cela vous donnera la réponse.Pour autant que je sache, en raison de JavaScript arrondissant les valeurs, il est seulement précis jusqu'à n = 75. Passé, vous obtiendrez une bonne estimation, mais il ne sera pas totalement précis, sauf si vous voulez faire quelque chose de difficile comme magasin les valeurs en tant que chaîne puis analysent celles-ci en tant que BigIntegers.

Answer 9

Je viens d'écrire ma propre petite implémentation en utilisant un objet pour stocker des résultats déjà calculés. Je l'ai écrit dans Node.JS, qui avait besoin de 2ms (selon mon horloge) pour calculer la fibonacci pour 1476.

Voici le code Bx_boom pur Javascript:

var nums = {}; // Object that stores already computed fibonacci results 
function fib(n) { //Function 
    var ret; //Variable that holds the return Value 
    if (n < 3) return 1; //Fib of 1 and 2 equal 1 => filtered here 
    else if (nums.hasOwnProperty(n)) ret = nums[n]; /*if the requested number is 
    already in the object nums, return it from the object, instead of computing */ 
    else ret = fib(n - 2) + fib(n - 1); /* if requested number has not 
    yet been calculated, do so here */ 
    nums[n] = ret; // add calculated number to nums objecti 
    return ret; //return the value 
} 

//and finally the function call: 
fib(1476) 

EDIT: Je l'ai pas essayer d'exécuter ceci dans un navigateur!

ÉDITER à nouveau: maintenant je l'ai fait. essayez le jsFiddle: Le temps jsfiddle fibonacci varie entre 0 et 2 ms

Answer 10

Beaucoup algorithme plus rapide:

const fib = n => fib[n] || (fib[n-1] = fib(n-1)) + fib[n-2]; 
fib[0] = 0; // Any number you like 
fib[1] = 1; // Any number you like