From: Jeff Mitchell <quixoticsycophant@...>
Date: 2004-05-14T07:01:23+09:00
Subject: Re: Major Addition Bug?

>> Jeff Mitchell <quixoticsycophant@yahoo.com> wrote on
>> 13 May 2004 02.59:
>>
>> Coming from a background in mathematics, I have personal 
>> affection for:
>> 
>> class Float
>>    def within?(epsilon, other)
>>       abs(self - other) < epsilon
>>    end
>> end
> 
>"Austin Ziegler" <Austin.Ziegler@evault.com> wrote:
> Mmm. I might write that as:
> 
>   class Float
>     def within?(other, epsilon = 1e-8)
>       abs(self - other) < epsilon
>     end
>   end
>
> It messes up the nice readability, but you don't have to type
> EPSILON all the time, either.

The reason I made epsilon explicit is not only for the phrasing: I did
it because you can't make epsilon implicit!

Epsilon is essential to the whole problem!  It's not something which
can be assumed in any case.

My example was misleading in its simplicity.  EPSILON is the starting
error whereas "epsilon," or the error term, is a variable which grows
alongside every calculation you do.  The actual epsilon is an
expression involving EPSILON.

Here's a quick taste in numerical analysis:

We express a real number _a_ with relative error _EPSILON_ as

a*(1 + EPSILON)

Now let's see what happens to the error when we multiply this with
real number _b_ which has the same error:

(a*(1 + EPSILON))*(b*(1 + EPSILON)) ==
(a + a*EPSILON)*(b + b*EPSILON) ==
a*b + 2*a*b*EPSILON + a*b*EPSILON**2

EPSILON**2 is overwhelmingly small compared to everything else, so we
drop it (keeping a linear approximation).

a*b + 2*a*b*EPSILON == 
(a*b)*(1 + 2*EPSILON)

And look!  The error in a*b is _twice_ EPSILON! and all we've done is
a single multiplication!

You could argue that I'm being overly analytical; that in practice we
can choose some arbitrary epsilon, say EPSILON = 1e-8.  But that fixed
epsilon will only work as far as anecdotal examples and the simplest
computations.

You'll eventually be bitten when the error propagates further than the
fixed EPSILON.  This will manifest itself as bug; #approx_eql? will
start to fail for apparently no reason.  This will happen even in
seemingly trivial calculations.  Error increases in unexpected places
(multiplication is just one place).

Always know at least a ball-park estimate of epsilon for a given
situation.  The easiest estimate is to add together errors whenever
you see multiplication.  a*b has error epsilon_a + epsilon_b.  Realize
when you use an output as an input, as you need to carry that epsilon
over.

This all suggests:

class FuzzyFloat
   def initialize(value, epsilon)
      @value = value
      @epsilon = epsilon
   end

   attr_reader :value, :epsilon

   def *(other)
      FuzzyFloat.new(@value*other.value, @epsilon + other.epsilon)
   end
   
   def ==(other)
      distance = abs(@value - other.value)
      (distance < @radius) and (distance < other.radius)
   end
   
   # ...
end

however there is a general problem of epsilon approaching the
granularity of Float itself, i.e. the error of the error.  The Float
version of Planck's constant confounds our measurements :) But
FuzzyFloat may still have some use for sufficiently large epsilon.



	
		
__________________________________
Do you Yahoo!?
Yahoo! Movies - Buy advance tickets for 'Shrek 2'
http://movies.yahoo.com/showtimes/movie?mid=1808405861