Fibonacci

força bruta

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

otimizado

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

com raiz quadrada

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

com cache

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

com fechamento

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

com recursão (desacelerar para grandes números)

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