Re: Faster Recursive Fibonacci Numbers

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From	Gregory Ewing <greg.ewing@canterbury.ac.nz>
Newsgroups	comp.lang.python
Subject	Re: Faster Recursive Fibonacci Numbers
Date	Sat, 21 May 2011 20:49:33 +1200
Lines	30
Message-ID	<93pcl0Fe1nU1@mid.individual.net> (permalink)
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> <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>
Mime-Version	1.0
Content-Type	text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding	7bit
X-Trace	individual.net ftTNBJaST9z6ByVXCdXJegB/VemF45xnNyX+8NN9DBYkeykWbd
Cancel-Lock	sha1:7OBN+IpO0FFmz/TGueSmbECgDCQ=
User-Agent	Mozilla Thunderbird 1.0.5 (Macintosh/20050711)
X-Accept-Language	en-us, en
In-Reply-To	<mailman.1823.1305871603.9059.python-list@python.org>
Xref	x330-a1.tempe.blueboxinc.net comp.lang.python:5908

Show key headers only | 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