Re: float("nan") in set or as key

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!news.glorb.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!spln!extra.newsguy.com!newsp.newsguy.com!not-for-mail
From	Chris Torek <nospam@torek.net>
Newsgroups	comp.lang.python
Subject	Re: float("nan") in set or as key
Date	1 Jun 2011 18:29:21 GMT
Organization	None of the Above
Lines	52
Message-ID	<is60e101pr7@news4.newsguy.com> (permalink)
References	<d63a1808-e704-4538-8541-9edeadab2135@glegroupsg2000goo.googlegroups.com> <mailman.2376.1306950997.9059.python-list@python.org>
NNTP-Posting-Host	pd53bfbd94b59cf5339e5356e40be3a7104146621d5a69577.newsdawg.com
X-Newsreader	trn 4.0-test76 (Apr 2, 2001)
Originator	torek@elf.torek.net (Chris Torek)
Xref	x330-a1.tempe.blueboxinc.net comp.lang.python:6813

Show key headers only | View raw

>Carl Banks wrote:
>> For instance, say you are using an implementation that uses
> > floating point, and you define a function that uses Newton's
> > method to find a square root:
>> 
>> def square_root(N,x=None):
>>     if x is None:
>>         x = N/2
>>     for i in range(100):
>>         x = (x + N/x)/2
>>     return x
>> 
>> It works pretty well on your floating-point implementation.
> > Now try running it on an implementation that uses fractions
> > by default....
>> 
>> (Seriously, try running this function with N as a Fraction.)

In article <mailman.2376.1306950997.9059.python-list@python.org>
Ethan Furman  <ethan@stoneleaf.us> wrote:
>Okay, will this thing ever stop?  It's been running for 90 minutes now. 
>  Is it just incredibly slow?

The numerator and denominator get very big, very fast.

Try adding a bit of tracing:

        for i in range(100):
            x = (x + N/x) / 2
            print 'refinement %d: %s' % (i + 1, x)

and lo:

    >>> square_root(fractions.Fraction(5,2))
    refinement 1: 13/8
    refinement 2: 329/208
    refinement 3: 216401/136864
    refinement 4: 93658779041/59235012928
    refinement 5: 17543933782901678712641/11095757974628660884096
    refinement 6: 615579225157677613558476890352854841917537921/389326486355976942712506162834130868382115072
    refinement 7: 757875564891453502666431245010274191070178420221753088072252795554063820074969259096915201/479322593608746863553102599134385944371903608931825380820104910630730251583028097491290624
    refinement 8: 1148750743719079498041767029550032831122597958315559446437317334336105389279028846671983328007126798344663678217310478873245910031311232679502892062001786881913873645733507260643841/726533762792931259056428876869998002853417255598937481942581984634876784602422528475337271599486688624425675701640856472886826490140251395415648899156864835350466583887285148750848

In the worst case, the number of digits in numerator and denominator
could double on each pass, so if you start with 1 digit in each,
you end with 2**100 in each.  (You will run out of memory first
unless you have a machine with more than 64 bits of address space. :-) )

-- 
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W)  +1 801 277 2603
email: gmail (figure it out)      http://web.torek.net/torek/index.html

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

Thread

Re: float("nan") in set or as key Carl Banks <pavlovevidence@gmail.com> - 2011-05-31 23:09 -0700
  Re: float("nan") in set or as key "OKB (not okblacke)" <brenNOSPAMbarn@NObrenSPAMbarn.net> - 2011-06-01 17:17 +0000
  Re: float("nan") in set or as key Ethan Furman <ethan@stoneleaf.us> - 2011-06-01 11:10 -0700
    Re: float("nan") in set or as key Chris Torek <nospam@torek.net> - 2011-06-01 18:29 +0000

csiph-web