Javascript Fibonacci第n項優化

Question

我近來對算法很感興趣，斐波那契數列由於其簡單性而引起了我的注意。

我已經設法把一些東西放在一起，在閱讀了大量網絡信息後，它在不到15毫秒的時間內計算斐波那契數列中的第n項。它高達1476 ... 1477是無限的，1478是NaN（根據javascript！）

我爲代碼本身感到非常自豪，除了它是一個完全的怪物。

所以這裏是我的問題： A）有更快的方法來計算序列？ B）有兩種矩陣乘法的更快/更小的方法嗎？

下面的代碼：

//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 

矩陣函數有兩個參數：a和b，並返回一個* b，其中a和b是2×2陣列。 哦，並在一個側面說明，發生了一件神奇的事情......我正在將Strassen算法轉換成JS數組符號，它在我的第一次嘗試中就起作用了！太棒了，對吧？ ：P

如果您設法找到更簡單的方法來提前致謝。

Answer 1

不要猜測，風向標：

編輯：我說我自己的矩陣實現使用我的其他答案中提到的優化乘法函數。這導致了一個主要的加速，但即使是循環矩陣乘法的vanilla O（n^3）實現也比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> 

產生

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] 

你的算法是幾乎未緩存循環的那樣糟糕。高速緩存是您的最佳選擇，緊隨其後的是舍入算法 - 對於大型的n（與您的矩陣算法一樣）會產生不正確的結果。

對於較小的n，你的算法的性能比一切更糟糕：

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

對於第n個斐波那契數有一個封閉形式（無環）解。

See Wikipedia.

Answer 3

如何memoizing的結果，其中已計算，像這樣的：

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

或者，如果你想要一個更通用的記憶化功能，延長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(); 

需要注意的一點是，由於技術（瀏覽器安全）的限制，的論點對於memoized函數只能是數組或標量值。沒有物體。

參考：http://talideon.com/weblog/2005/07/javascript-memoization.cfm

Answer 4

有可能是計算值，更快的方式，但我不認爲這是必要的。

一次計算它們，並在你的程序，輸出結果如下fibdata行：

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

那麼，這就是你運送到客戶端的代碼。這是一個O（1）解決方案。

人們經常忽視'緩存'解決方案。我曾經爲嵌入式系統寫過三角函數，而不是使用無限級數來快速計算它們，我只是有幾個查找表，每個輸入的每個度數有360個條目。

不用說，它只需要大約1K的RAM就可以尖叫起來。這些值被存儲爲1字節的條目，[實際值（0-1）* 16]，所以我們可以做一個查找，乘法和位移來獲得所需的值。

Answer 5

要擴大Dreas的回答有點：

1）cache應該開始爲[0, 1]
2）你怎麼用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) 

---

如果你不喜歡沉默的錯誤：

// 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

我以前的答案有一點擁擠，所以我會發佈一個新問題：

可以加快你的算法採用2×2香草矩陣乘法 - 即本替換你matrix()功能：

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

如果你關心ACCU活潑和速度，使用緩存解決方案。如果精度不是問題，但內存消耗是使用舍入解決方案。矩陣解決方案只有在你想要快速的結果時纔有意義，不需要關心精度，也不想重複調用函數。

編輯：，你甚至可以進一步加快計算，如果你使用專門的乘法功能，消除公共子和現有的陣列中替換的值，而不是創建一個新的數組：

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

注意： a是全局矩陣變量的名稱。

Answer 7

這裏是計算斐波那契序列中的JavaScript

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

閉合解的一個非常快的解決方案：

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

誠然，甚至乘法開始與龐大的數字打交道時採取的費用，但是這會給你答案。據我所知，由於JavaScript對值進行四捨五入，因此只有n = 75時纔是準確的。過去，你會得到一個很好的估計，但它不會是完全準確的，除非你想要做一些棘手的事情，比如存儲作爲字符串的值然後將它們解析爲BigIntegers。

Answer 9

我剛剛寫了一個使用Object的小實現來存儲已計算結果。我（根據我的定時器）在Node.js的，這需要2ms的寫它來計算1476

斐波納契這裏的剝離下來純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) 

編輯：我做了不要嘗試在瀏覽器中運行此操作！

再次編輯：現在我做了。嘗試的jsfiddle：jsfiddle fibonacci時間變化介於0和2ms的

Answer 10

快得多的算法：

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