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

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 + aEPSILON)(b + bEPSILON) ==
a
b + 2abEPSILON + ab*EPSILON**2

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

ab + 2abEPSILON ==
(ab)(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 :slight_smile: But
FuzzyFloat may still have some use for sufficiently large epsilon.

···

“Austin Ziegler” Austin.Ziegler@evault.com wrote:


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

Why not do interval arithmetics? Of course, you can’t implement that in pure
ruby, only as a C addition, as you’ll have to do arithmetic in different
rounding modes.

ambrus

···

On Fri, May 14, 2004 at 07:01:23AM +0900, Jeff Mitchell wrote:

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 :slight_smile: But
FuzzyFloat may still have some use for sufficiently large epsilon.