[Chicago] Chicago Digest, Vol 29, Issue 6

[Jeff Hinrichs - DM&T]

Ok, I couldn't resist.

def fib_nr(n):
    """non-recursive version of fibonacci"""
    prev = -1
    result = 1
    for i in xrange(n+1):
        sum = result + prev
        prev = result
        result = sum
    return result

On Jan 6, 2008 6:21 PM, Massimo Di Pierro <mdipierro at cs.depaul.edu> wrote:
>
> This gets all of them right up to n=75 (with python double precision
> arithmetic) then you start have a small discrepancy on the last digit.
> But it theta(1) (no loops and no recursion)
>
> def fib(n):
>      f5=math.sqrt(5)
>      a,b=(1.0+f5)/2,(1-f5)/2
>      epsilon=0.5 # takes care of rounding errors
>      return int((a**n-b**n)/f5+epsilon)
>
> Massimo
>
>
>
> On Jan 6, 2008, at 6:01 PM, Andrew Harrington wrote:
>
>
> Short and sweet in theory, but awful exponential run time!
> Andy
>
>
> > Message: 8
> > Date: Sun, 06 Jan 2008 02:33:43 -0600
> > From: "Kenneth P. Stox" <ken at stox.org>
> > Subject: Re: [Chicago] Python Tutorial 4.6 function fib()
> > To: The Chicago Python Users Group < chicago at python.org>
> > Message-ID: <1199608423.9450.24.camel at stox.dyndns.org>
> > Content-Type: text/plain
> >
> > Welcome to the wonderful world of recursion:
> >
> > def fib(n):
> >  if n<2:
> >    return n
> >  else:
> >    return fib(n-2)+fib(n-1)
> >
> >
> >
> >
> > ------------------------------
> >
> > _______________________________________________
> > Chicago mailing list
> > Chicago at python.org
> > http://mail.python.org/mailman/listinfo/chicago
> >
> >
> > End of Chicago Digest, Vol 29, Issue 6
> > **************************************
> >
>
>
>
> --
> Andrew N. Harrington
>   Director of Academic Programs
>   Computer Science Department
>   Loyola University Chicago
>   512B Lewis Towers (office)
>   Snail mail to Lewis Towers 416
>   820 North Michigan Avenue
>   Chicago, Illinois 60611
>
> http://www.cs.luc.edu/~anh
> Phone: 312-915-7999
> Fax:    312-915-7998
> gdp at cs.luc.edu for graduate administration
> upd at cs.luc.edu for undergrad administration
>  aharrin at luc.edu as professor<ATT00001.txt>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org
> http://mail.python.org/mailman/listinfo/chicago
>
>



-- 
Jeff Hinrichs
Dundee Media & Technology, Inc
jeffh at dundeemt.com
402.218.1473