Re: Faster Recursive Fibonacci Numbers

From	Gregory Ewing <greg.ewing@canterbury.ac.nz>
Newsgroups	comp.lang.python
Subject	Re: Faster Recursive Fibonacci Numbers
Date	2011-05-21 20:49 +1200
Message-ID	<93pcl0Fe1nU1@mid.individual.net> (permalink)
References	(2 earlier) <mailman.1680.1305651743.9059.python-list@python.org> <4dd59e1e$0$29996$c3e8da3$5496439d@news.astraweb.com> <mailman.1806.1305848281.9059.python-list@python.org> <4dd602ec$0$29996$c3e8da3$5496439d@news.astraweb.com> <mailman.1823.1305871603.9059.python-list@python.org>

Show all headers | View raw

Chris Angelico wrote:
> It seems
> strange to smoothly slide from native integer to long integer and just
> keep on going, and yet to be unable to do the same if there's a
> fractional part on it.

The trouble is that if you always compute exact results
by default, the number of digits required can blow up
very quickly.

There's a story that ABC (the predecessor to Python)
calculated everything using rationals. People found that
sometimes a calculation would take an unexpectedly long
time, and it turned out to be because internally it was
creating fractions with huge numerators and denominators.

As a consequence, Guido decided that Python would *not*
use rationals by default.

The same problem doesn't arise with ints, because the
only time you get an int with a large number of digits
is when you genuinely need a large int. So expanding
ints automatically to however many digits is needed
doesn't do any harm.

In Python 2.6 and later, there's a fractions module for
when you need it.

-- 
Greg

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