<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">
<div>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.</div><div>But it theta(1) (no loops and no recursion)</div><div><br class="webkit-block-placeholder"></div><div>def fib(n):</div><div> f5=math.sqrt(5)</div><div> a,b=(1.0+f5)/2,(1-f5)/2</div><div> epsilon=0.5 # takes care of rounding errors</div><div> return int((a**n-b**n)/f5+epsilon)</div><div><br class="webkit-block-placeholder"></div><div>Massimo</div><div><br class="webkit-block-placeholder"></div><div><div>On Jan 6, 2008, at 6:01 PM, Andrew Harrington wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">Short and sweet in theory, but awful exponential run time!<br>Andy<br><br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> Message: 8<br>Date: Sun, 06 Jan 2008 02:33:43 -0600<br>From: "Kenneth P. Stox" <<a href="mailto:ken@stox.org">ken@stox.org</a>><br>Subject: Re: [Chicago] Python Tutorial 4.6 function fib()<br>To: The Chicago Python Users Group < <a href="mailto:chicago@python.org">chicago@python.org</a>><br>Message-ID: <<a href="mailto:1199608423.9450.24.camel@stox.dyndns.org">1199608423.9450.24.camel@stox.dyndns.org</a>><br>Content-Type: text/plain<br><br> Welcome to the wonderful world of recursion:<br><br>def fib(n):<br> if n<2:<br> return n<br> else:<br> return fib(n-2)+fib(n-1)<br><br><br><br><br>------------------------------<br><br>_______________________________________________ <br>Chicago mailing list<br><a href="mailto:Chicago@python.org">Chicago@python.org</a><br><a href="http://mail.python.org/mailman/listinfo/chicago" target="_blank">http://mail.python.org/mailman/listinfo/chicago</a><br><br> <br>End of Chicago Digest, Vol 29, Issue 6<br>**************************************<br></blockquote></div><br><br clear="all"><br>-- <br>Andrew N. Harrington<br> Director of Academic Programs<br> Computer Science Department <br> Loyola University Chicago <br> 512B Lewis Towers (office) <br> Snail mail to Lewis Towers 416<br> 820 North Michigan Avenue<br> Chicago, Illinois 60611<br><br><a href="http://www.cs.luc.edu/~anh">http://www.cs.luc.edu/~anh </a><br>Phone: 312-915-7999<br>Fax: 312-915-7998<br><a href="mailto:gdp@cs.luc.edu">gdp@cs.luc.edu</a> for graduate administration<br><a href="mailto:upd@cs.luc.edu">upd@cs.luc.edu</a> for undergrad administration<br><a href="mailto:aharrin@luc.edu"> aharrin@luc.edu</a> as professor<span><ATT00001.txt></span></blockquote></div><br></body></html>