Javascript Fibonacci nth Term Optimization

Question

我最近对算法产生了兴趣,由于其简单性,斐波纳契序列引起了我的注意.

我已经设法将一些东西放在javascript中,在网上阅读大量信息后,在不到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,并返回a*b,其中a和b是2x2数组.哦,并且在旁注中,发生了一件神奇的事情......我正在将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个Fibonacci数,存在闭合形式(无循环)解.

见维基百科.