Except that the "better" solution posted isn't better in many programming languages. For example: Python. It has infinite-precision integers. As such, although

Except that the "better" solution posted isn't better in many programming languages. For example: Python. It has infinite-precision integers. As such, although his "better" formula starts to diverge from the actual answer at n=71 (308061521170130 versus 308061521170129) while only getting worse from there, the "naive" solution keeps working - albeit with O(n) behavior. def fib(n): return round((pow(0.5 + 0.5 * pow(5.0, 1/2), n) - pow(0.5 - 0.5 * pow(5.0, 1/2), n)) / pow(5.0, 1/2)) def fib(n): a, b = 0, 1 for i in range(n): a, b = b, a + b return a You can do it with the decimal library as well, but you have to adjust precision on-the-fly to get the required precision. This is a better solution if you're willing to allow the additional complexity: http://willwhim.wpengine.com/2013/04/02/a-fibonacci-a-day-fibonaccin-in-olgn-steps/ http://willwhim.wpengine.com/2013/04/02/a-fibonacci-a-day-fi...