On: Julia, I love you (2012)

[carlob]

Can't you do it in O(1) if you limit yourself to floats? Arbitrary n but not arbitrary precision?

[mikeash → carlob]

I imagine the table would still be of reasonable size then. Of course, this is still technically restricting the output to 32 or 64-bit numbers.

[gamegoblin → mikeash]

No need for a table lookup. There is a closed form formula. Of course this is only as accurate as your float precision. You can get out pretty far, though, with some clever rounding.

http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...