On 17 Mai, 20:56, geremy condra <debat...@gmail.com> wrote:
> On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen
>
> <jpiit...@ling.helsinki.fi> wrote:
> > geremy condra writes:
>
> >> or O(1):
>
> >> ö = (1 + sqrt(5)) / 2
> >> def fib(n):
> >> numerator = (ö**n) - (1 - ö)**n
> >> denominator = sqrt(5)
> >> return round(numerator/denominator)
>
> >> Testing indicates that it's faster somewhere around 7 or so.
>
> > And increasingly inaccurate from 71 on.
>
> Yup. That's floating point for you. For larger values you could just
> add a linear search at the bottom using the 5f**2 +/- 4 rule, which
> would still be quite fast out to about 10 times that. The decimal
> module gets you a tiny bit further, and after that it's time to just
> use Dijkstra's, like rusi suggested. In any event, I still think this
> formulation is the most fun ;).
I think you can write it even more funny
def fib(n):
return round(((.5 + .5 * 5 ** .5) ** n - (.5 - .5 * 5 ** .5) **
n) * 5 ** -.5)
;-)
--
http://mail.python.org/mailman/listinfo/python-list
