float("nan") in set or as key

[Chris Torek]

>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 at python.org>
Ethan Furman  <ethan at 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