# [Chicago] Chicago Digest, Vol 29, Issue 6

Massimo Di Pierro mdipierro at cs.depaul.edu
Mon Jan 7 01:21:02 CET 2008

```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
>  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