Hacker News Reader

Comment by khebbie | Hacker News Reader

The rigth way to do fibonacci would probably be to add memoization...

Or turn it into a simple iterative process, instead of a recursive process. They explain how quite simply in SICP:

http://sarabander.github.io/sicp/html/1_002e2.xhtml (Ctrl-F "We can also formulate an iterative process for computing the Fibonacci numbers.")

Here's a Python implementation:

    def fib(n):
        a = 1
        b = 0
        i = 0
        while i < n:
            temp = a
            a += b
            b = temp
            i += 1
        return a

With that, fib(100000) takes half a second to compute on my machine.

The "right" way to do Fibonacci is to use matrix multiplication to get the nth Fibonacci number in logarithmic time (google Fibonacci log n matrix).

A matrix implementatiom in JavaScript:

http://raganwald.com/2015/12/20/an-es6-program-to-compute-fi...

It is based on a Ruby implementation:

http://raganwald.com/2008/12/12/fibonacci.html

Why not calculate it in constant time ?

https://artofproblemsolving.com/wiki/index.php?title=Binet%2...

You can't really compute it in constant time since the number of bits in the nth Fibonacci number is O(n), so you need to take at least that long just to write the result out.

Computing with Binet's formula is also rather tricky. You just need to round φ^n/√5, but how many bits of √5 do you need to use?

true: adding 2 64 bit numbers is constant time for me, but adding 2 4096 bit numbers is not. Eventually, even the simplest operation becomes O(ln n)

As mentioned in other comments, working with floating point numbers in practice is trickier than it looks in theory:

http://raganwald.com/2013/03/26/the-interview.html

But I suppose not adding memoization will reveal the real performance of the language

Just not idiomatic code

Reply on news.ycombinator.com