Optimization of terms in Fibonacci language

My previous answer is a bit overkill, so I'll post a new one:

You can speed up your algorithm using 2x2 vanilla matrix multiplication i.e. replace your function matrix()

like 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 want accuracy and speed, use a caching solution. If precision is not a concern but memory consumption, use a rounding solution. A matrix solution only makes sense if you want results for large ones to n

be fast, don't care about precision, and don't want to call the function many times.

edit: You can speed up the computation even further if you use specialized multiplication functions, eliminate common subexpressions, and replace values ​​in an 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.

How about reminders for results that have already been calculated, for example:

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 need a more general memoization function, extend the 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();

      

        
        
        
      

    

Note that due to technical browser security restrictions, arguments to memoized functions can only be arrays or scalar values . No objects.

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

To expand a bit on Dreas answer :

1) cache

should you start with [0, 1]


2) what are you doing 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 + ')');

      

        
        
        
      

    

Here is a very quick solution for calculating the Fibonacci sequence

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)

      

        
        
        
      

    

Closed form solution in 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;
}

      

        
        
        
      

    

Sure, even multiplication starts to take on costs when dealing with huge numbers, but that will give you the answer. As far as I know, due to JavaScript rounding values, it is only accurate to n = 75. In the past, you will get a good grade, but it won't be entirely accurate unless you want to do something complicated like store the value in as a string, then parse them as BigIntegers.

I just wrote my little implementation using an object to store the results already computed. I wrote it in Node.JS which took 2ms (on my timer) to calculate fibonacci for 1476.

Here's the code split in pure 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: I haven't tried to run this in a browser!

EDIT again: I have now done this. try the jsfiddle: jsfiddle fibonacci Time changes from 0 to 2ms