Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #5871

Re: Faster Recursive Fibonacci Numbers

Show all headers | View raw

On Fri, May 20, 2011 at 10:07 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Fri, 20 May 2011 16:54:06 +1000, Chris Angelico wrote:
>
>> If someone has time to kill (as if!), it'd be awesome to get a new
>> numeric type that uses bc's code; any other numeric type (int, long,
>> float) could autopromote to it, removing the dilemma of which to promote
>> out of long and float. Hmm... Python 4.0, 'bc' is the new default
>> integer and everything else is a performance optimization? Heh.
>
> The problem is, it isn't *just* a performance optimization, there is a
> semantic difference too. Consider:
>
>>>> x = 1e-300
>>>> x*x == 0
> True
>
> But using something with more precision:
>
>>>> from fractions import Fraction
>>>> x = Fraction(10)**-300
>>>> x*x == 0
> False
>
>
> So you get different behaviour between floats and arbitrary precision
> numbers.

And this shows up in the above implementation; reimplementing it using
Fractions and a truncated continuing fraction approximation of phi and
the square root of 5 gets us up to about 500, at the cost of a very
long computation time.

Geremy Condra

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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