Skip to content

Instantly share code, notes, and snippets.

@pjambet
Created September 19, 2012 20:53
Show Gist options
  • Save pjambet/3752189 to your computer and use it in GitHub Desktop.
Save pjambet/3752189 to your computer and use it in GitHub Desktop.
Fibonacci with & without memoizer
var limit = 100000000
var fibonacci = function(n) {
if (typeof fibonacci.count === 'undefined') {
fibonacci.count = 0
}
fibonacci.count += 1
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2)
}
var start = new Date().getTime()
console.log("Let's go !")
var i = 0,
f = fibonacci(i),
sum = 0
while( f < limit ) {
if ( f % 2 === 0 ) sum += f
i += 1
f = fibonacci(i)
}
console.log('//', i, ':', f)
console.log('//sum:', sum)
console.log('Total computing time : ', new Date().getTime() - start, "ms")
console.log('Total call : ', fibonacci.count)
var fibonacci = function() {
var memo = [0, 1]
var fib = function(n) {
if (typeof fib.count === 'undefined') {
fib.count = 0
}
fib.count += 1
var result = memo[n]
if (typeof result !== 'number'){
result = fib(n - 1) + fib(n - 2)
memo[n] = result
}
return result
}
return fib
}()
var memoizer = function(memo, formula){
var recur = function(n) {
if (typeof recur.count === 'undefined') {
recur.count = 0
}
recur.count += 1
var result = memo[n]
if (typeof result !== 'number') {
result = formula(recur, n)
memo[n] = result
}
return result
}
return recur
}
var fibonacci = memoizer([0, 1], function(recur, n){
return recur(n - 1) + recur(n - 2)
})
var start = new Date().getTime()
console.log("Let's go !")
var i = 0,
f = fibonacci(i),
sum = 0
while( f < limit ) {
if ( f % 2 === 0 ) sum += f
i += 1
f = fibonacci(i)
}
console.log('//', i, ':', f)
console.log('//sum:', sum)
console.log('Total computing time : ', new Date().getTime() - start, "ms")
console.log('Total call : ', fibonacci.count)
// Output on my laptop
// Let's go !
// // 40 : 102334155
// //sum: 82790070
// Total computing time : 7619 ms
// Total call : 866988831
// Let's go !
// 40 : 102334155
// //sum: 82790070
// Total computing time : 0 ms
// Total call : 119
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment