Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #5595
| References | <108ce447-10fa-4cf7-84ef-440ee18dbfd4@22g2000prx.googlegroups.com> <9d9c163b-14fd-4131-81bb-105c3b97c432@h36g2000pro.googlegroups.com> <mailman.1680.1305651743.9059.python-list@python.org> <qotmxilp7na.fsf@ruuvi.it.helsinki.fi> |
|---|---|
| Date | 2011-05-17 11:56 -0700 |
| Subject | Re: Faster Recursive Fibonacci Numbers |
| From | geremy condra <debatem1@gmail.com> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.1695.1305658596.9059.python-list@python.org> (permalink) |
On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen <jpiitula@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 ;). Geremy Condra
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Faster Recursive Fibonacci Numbers RJB <rbotting@csusb.edu> - 2011-05-17 08:50 -0700
Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-17 10:23 -0600
Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 09:25 -0700
Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 09:36 -0700
Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 10:02 -0700
Re: Faster Recursive Fibonacci Numbers Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2011-05-17 20:19 +0300
Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 11:56 -0700
Re: Faster Recursive Fibonacci Numbers Wolfram Hinderer <wolfram.hinderer@googlemail.com> - 2011-05-17 14:04 -0700
Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 14:59 -0700
Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 21:43 -0700
Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-19 22:47 +0000
Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 09:37 +1000
Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 05:58 +0000
Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 16:06 +1000
Re: Faster Recursive Fibonacci Numbers harrismh777 <harrismh777@charter.net> - 2011-05-20 01:26 -0500
Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 16:54 +1000
Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 17:07 +0000
Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-20 11:43 -0700
Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-21 10:44 +1000
Re: Faster Recursive Fibonacci Numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-05-21 20:49 +1200
Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 01:26 -0600
Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 01:32 -0600
Re: Faster Recursive Fibonacci Numbers SigmundV <sigmundv@gmail.com> - 2011-05-20 03:53 -0700
Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-19 17:03 -0700
Re: Faster Recursive Fibonacci Numbers Raymond Hettinger <python@rcn.com> - 2011-05-24 16:44 -0700
csiph-web