2011/5/20 Ian Kelly <ian.g.ke...@gmail.com>: > def fib_decimal(n): > with localcontext() as ctx: > ctx.prec = n // 4 + 1 > sqrt_5 = Decimal('5').sqrt() > phi = (1 + sqrt_5) / 2 > numerator = (phi ** n) - (1 - phi) ** n > return int((numerator / sqrt_5).to_integral_value())
Note that I believe this is O(n) since the necessary precision grows linearly with n. -- http://mail.python.org/mailman/listinfo/python-list