Javascript Fibonacci nth Term Optimization

Question

I've become interested in algorithms lately, and the fibonacci sequence grabbed my attention due to its simplicity.

I've managed to put something together in javascript that calculates the nth term in the fibonacci sequence in less than 15 milliseconds after reading lots of information on the web. It goes up to 1476...1477 is infinity and 1478 is NaN (according to javascript!)

I'm quite proud of the code itself, except it's an utter monster.

So here's my question: A) is there a faster way to calculate the sequence? B) is there a faster/smaller way to multiply two matrices?

Here's the 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

The matrix function takes two arguments: a and b, and returns a*b where a and b are 2x2 arrays. Oh, and on a side note, a magical thing happened...I was converting the Strassen algorithm into JS array notation and it worked on my first try! Fantastic, right? :P

Thanks in advance if you manage to find an easier way to do this.

Answer 1

There is a closed form (no loops) solution for the nth Fibonacci number.

See Wikipedia.

Answer 2

How about memoizing the results that where already calculated, like such:

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

Or if you want a more generic memoization function, extend the Function prototype:

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

One note to add is that due to technical (browser security) constraints, the arguments for memoized functions can only be arrays or scalar values. No objects.

Reference: http://talideon.com/weblog/2005/07/javascript-memoization.cfm

Answer 3

There may well be a faster way to calculate the values but I don't believe it's necessary.

Calculate them once and, in your program, output the results as the fibdata line below:

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

Then, that's the code you ship to your clients. That's an O(1) solution for you.

People often overlook the 'caching' solution. I once had to write trig routines for an embedded system and, rather than using infinite series, I just had a few lookup tables, 360 entries in each for each of the degrees of input.

Needless to say, it screamed along at the cost of only about 1K of RAM, the values were stored as 1-byte entries, [actual value (0-1) * 16] so we could just do a lookup, multiply and left bit shift to get the desired value.

Answer 4

To expand a bit on Dreas's answer:

1) cache should start as [0, 1]
2) what do you do with 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)

---

If you don't like silent errors:

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

Don't speculate, benchmark:

edit: I added my own matrix implementation using the optimized multiplication functions mentioned in my other answer. This resulted in a major speedup, but even the vanilla O(n^3) implementation of matrix multiplication with loops was faster than the Strassen algorithm.

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

yields

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]

Your algorithm is nearly as bad as uncached looping. Caching is your best bet, closely followed by the rounding algorithm - which yields incorrect results for big n (as does your matrix algorithm).

For smaller n, your algorithm performs even worse than everything else:

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 6

My previous answer got a bit crowded, so I'll post a new one:

You can speed up your algorithm by using vanilla 2x2 matrix multiplication - ie replace your matrix() function with this:

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

If you care for accuracy and speed, use the caching solution. If accuracy isn't a concern, but memory consumption is, use the rounding solution. The matrix solution only makes sense if you want results for big n fast, don't care for accuracy and don't want to call the function repeatedly.

edit: You can even further speed up the computation if you use specialised multiplication functions, eliminate common subexpressions and replace the values in the existing array instead of creating a new array:

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 is the name of the global matrix variable.

Answer 7

wow I wish I knew what you guys were talking about..