[Chicago] Chicago Digest, Vol 29, Issue 6

[Massimo Di Pierro]

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>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/chicago/attachments/20080106/40017fbc/attachment.htm