Last Updated: December 26, 2018
·
1.144K
· netzzwerg

Fibonacci

brute force

var maxNumbers = 1400;
var numbers = [0, 1];

var fib_basic = function() {
    while (numbers.length < maxNumbers) {
        var newNumber = numbers[numbers.length - 1] + numbers[numbers.length - 2]
        numbers.push(newNumber);
    }
}

console.time("-");
fib_basic();
console.timeEnd("-");
console.log(numbers[numbers.length - 1]);

optimized

var maxNumbers = 1400;
var numbers = [0, 1];

var fib_basic_opt = function() {
    for (var i = 2; i < maxNumbers; i++) {
        var length = numbers.length;
        var newNumber = numbers[length - 1] + numbers[length - 2]
        numbers.push(newNumber);
    }
}

console.time("-");
fib_basic_opt();
console.timeEnd("-");
console.log(numbers[numbers.length - 1]);

with square root

var maxNumbers = 1400;
var numbers = [];
var r5 = Math.sqrt(5);

var fib_square = function() {
    for (var i = 0; i < maxNumbers; i++) {
        var newNumber = (Math.pow((1 + r5) / 2, i) - Math.pow((1 - r5) / 2, i)) / r5;
        numbers.push(newNumber[i]);
    }
}

console.time("-");
fib_square();
console.timeEnd("-");
console.log(numbers[numbers.length - 1]);

with caching

var maxNumbers = 1400;
var numbers = [];
var cache = [0, 1];

var fib_array = function() {
    for (var i = 0; i < maxNumbers; i++) {
        cache.push(cache[0] + cache[1]);
        numbers.push(cache[0]);
        cache.shift();
    }
}

console.time("-");
fib_array();
console.timeEnd("-");
console.log(numbers[numbers.length - 1]);

with closure

var maxNumbers = 1400;
var numbers = [];

var fib_closure = function() {
    var fib = (function() {
        var cache = [0, 1];
        return function(n) {
            if (cache[n] === undefined) {
                cache[n] = fib(n - 1) + fib(n - 2);
            }
            return cache[n];
        };
    })();

    for (var i = 0; i < maxNumbers; i++) {
        numbers.push(fib(i));
    }
}

console.time("-");
fib_closure();
console.timeEnd("-");
console.log(numbers[numbers.length - 1]);

with recursion (to slow for big numbers)

var maxNumbers = 1400;
var numbers = [];

var fib_recursive = function() {
    var fib = function(n) {
        var returnValue = n;
        if (n > 1) {
            returnValue = fib(n - 1) + fib(n - 2);
        }
        return returnValue;
    }

    for (var i = 0; i < maxNumbers; i++) {
        var newNumber = fib(i);
        numbers.push(newNumber);
    }
}

console.time("-");
fib_recursive();
console.timeEnd("-");
console.log(numbers[numbers.length-1]);

2 Responses
Add your response

Nice progressive example series!

over 1 year ago ·

In the version with square root, the second term will be so small that one could actually round the first term instead.

By the way, shouldn't it be numbers.push(newNumber); instead of numbers.push(newNumber[i]); ?

over 1 year ago ·