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]);
Written by Béla Varga
Related protips
2 Responses
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
·
Have a fresh tip? Share with Coderwall community!
Post
Post a tip
Best
#Javascript
Authors
Related Tags
#javascript
Sponsored by #native_company# — Learn More
#native_title#
#native_desc#