float("nan") in set or as key

[Steven D'Aprano]

On Wed, 01 Jun 2011 13:41:15 -0700, Carl Banks wrote:

> On Wednesday, June 1, 2011 11:10:33 AM UTC-7, Ethan Furman wrote:
>> 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.)
>> 
>> Okay, will this thing ever stop?  It's been running for 90 minutes now.
>>   Is it just incredibly slow?
>> 
>> Any enlightenment appreciated!
> 
> Fraction needs to find the LCD of the denominators when adding; but LCD
> calculation becomes very expensive as the denominators get large (which
> they will since you're dividing by an intermediate result in a loop).  I
> suspect the time needed grows exponentially (at least) with the value of
> the denominators.
> 
> The LCD calculation should slow the calculation down to an astronomical
> crawl well before you encounter memory issues.
> 
> This is why representation simply cannot be left as an implementation
> detail; rationals and floating-points behave too differently.

True. Any rational implementation that has any hope of remaining fast has 
to limit the denominator to not exceed some fixed value.

Which makes it roughly equivalent to a float, only done in software with 
little hardware support.

(In case it's not obvious: floats are equivalent to implicit rationals 
with a scaling factor and denominator equal to some power of two.)

-- 
Steven