Fibonacci using cache

This is my simple Fibonacci implementation in CoffeeScript. What do you think? Using cache (fibResults), it's very very fast.

fibResults = []
defaultMax = 1000
nrMax = defaultMax

fibonacci = (n) ->
return fibResults[n] if fibResults[n]

if n < 2
fibResults[n] = n
else
fibResults[n] = fibonacci(n - 1) + fibonacci(n - 2)

nrMax = process.argv if process.argv

console.log("#{i}: #{fibonacci(i)}") for i in [0..nrMax]
• what is the max number that you are wanting to go to? i remember when we did this in C# and it got pretty intense, but i think we were just doing it in VIsual Studio Debug. and it was simple and quick for the low numbers.
– Malachi
Sep 30 '13 at 16:29

Something I noticed in your algorithm is that despite using memoization, you are still reassigning the Fibonnacci number into the array every time you calculate it.

You could avoid reassigning by having a function like computeIfAbsent that determines if the Fibonacci for a given n has already been calculated, and if not, use the Fibonacci function to calculate it and put it into the array, but only this time.

Also, we could avoid having to calculate the first two Fibonaccis by having them memoized from the start, and make the code fail for any index n smaller than 0.

memo = [0,1]

computeIfAbsent = (n, f) ->
fib = memo[n]
if typeof fib is 'undefined'
fib = f(n)
memo[n] = fib
fib

fibonacci = (x) ->
if x < 0
throw Error("Invalid index: " + x)
computeIfAbsent(x, (n) -> fibonacci(n-1) +  fibonacci(n-2))

console.log("#{i}: #{fibonacci(i)}") for i in [0..79]

Still, you must be aware that this code will not detect arithmetic overflows. It might look like it is calculating it right, but in fact, the calculations could be wrong due to overflow. I think your version and mine start to produce invalid results around 79.

You can check using a Fibonacci Calculator

• I'm returning the value if it's already in array here return fibResults[n] if fibResults[n] Oct 1 '13 at 6:56

Or you could do the golden ration hack ^_~ (in Javascript)

var M = Math
, pow = M.pow
, round = M.round
, phi = (M.sqrt(5)+1)/2
, phiAnd2 = phi +2
;
function fib(n){
return round(pow(phi,n)/phiAnd2)
}

Though this is only value up to n=75 when fib(75) === 2111485077978050