3 ms·
Can't you do it in O(1) if you limit yourself to floats? Arbitrary n but not arbitrary precision?
by carlob 14y ago
Can't you do it in O(1) if you limit yourself to floats? Arbitrary n but not arbitrary precision?
- mikeash 14y agoI 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 14y agoNo 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_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...