Short-circuit Logic

[Steven D'Aprano]

----------------------------------------

From: (e-mail address removed) Subject: Re: Short-circuit
Logic
Date: Thu, 30 May 2013 05:42:17 +0000 To: (e-mail address removed) [...]
Here's another way, mathematically equivalent (although not necessarily
equivalent using floating point computations!) which avoids the
divide-by- zero problem:

abs(a - b) < epsilon*a

That's wrong! If abs(a) < abs(a-b)/epsilon you will break the
commutative law. For example:

What makes you think that the commutative law is relevant here?

Many things break the commutative law, starting with division and
subtraction:

20 - 10 != 10 - 20

1/2 != 2/1

Most comparison operators other than equality and inequality:

(23 < 42) != (42 < 23)

String concatenation:

"Hello" + "World" != "World" + "Hello"

Many operations in the real world:

put on socks, then shoes != put on shoes, then socks.


But you are correct that approximately-equal using *relative* error is
not commutative. (Absolute error, on the other hand, is commutative.) As
I said, any form of "approximate equality" has gotchas. But this gotcha
is simple to overcome:

abs(a -b) < eps*max(abs(a), abs(b))

(Knuth's "approximately equal to" which you give.)

This discussion reminded me of TAOCP and I paid a visit and bring the
following functions:

"TAOCP"?

 

[Chris Angelico]

What makes you think that the commutative law is relevant here?

Equality should be commutative. If a == b, then b == a. Also, it's
generally understood that if a == c and b == c, then a == b, though
there are more exceptions to that (especially in loosely-typed
languages).

ChrisA

 

[Steven D'Aprano]

From: (e-mail address removed) Subject: Re: Short-circuit
Logic
Date: Fri, 31 May 2013 05:13:51 +0000 To: (e-mail address removed)

From: (e-mail address removed) Subject: Re: Short-circuit
Logic
Date: Thu, 30 May 2013 05:42:17 +0000 To: (e-mail address removed)
[...]
Here's another way, mathematically equivalent (although not
necessarily equivalent using floating point computations!) which
avoids the divide-by- zero problem:

abs(a - b) < epsilon*a

That's wrong! If abs(a) < abs(a-b)/epsilon you will break the
commutative law. For example:

What makes you think that the commutative law is relevant here?

How can't you see?

I can ask the same thing about you. How can you see that it is not
relevant?

I'll requote a previous message:

Thanks, but that's entirely irrelevant. It says nothing about the
commutative law.

[...]

Since we are considering Chris's supposition ("to compare floating point
numbers") it's totally relevant to understand how that operation can be
correctly implemented.

Of course! But what does that have to do with the commutative law?

Many things break the commutative law, starting with division and
subtraction:

20 - 10 != 10 - 20

1/2 != 2/1

Most comparison operators other than equality and inequality:

(23 < 42) != (42 < 23)

[...]
That's is totally irrelevant in this case. The commutative law is
essential to the equality operation.

That's fine, but we're not talking about equality, we're talking about
*approximately equality* or *almost equal*. Given the simple definition
of relative error under discussion, the commutative law does not hold.
The mere fact that it does not hold is no big deal. It doesn't hold for
many comparison operators.

Nor does the transitive law hold, even using absolute epsilon:

eps = 0.5
a = 1.1
b = 1.5
c = 1.9

then a ≈ b, and b ≈ c, but a ≉ c.

 

[Steven D'Aprano]

Equality should be commutative. If a == b, then b == a. Also, it's
generally understood that if a == c and b == c, then a == b, though
there are more exceptions to that (especially in loosely-typed
languages).

Who is talking about equality? Did I just pass through the Looking Glass
into Wonderland again? *wink*

We're talking about *approximate equality*, which is not the same thing,
despite the presence of the word "equality" in it. It is non-commutative,
just like other comparisons like "less than" and "greater than or equal
to". Nobody gets their knickers in a twist because the >= operator is non-
commutative.

Approximate equality is not just non-commutative, it's also intransitive.
I'm reminded of a story about Ken Iverson, the creator of APL. Iverson
was a strong proponent of what he called "tolerant equality", and APL
defined the = operator as a relative approximate equal, rather than the
more familiar exactly-equal operator most programming languages use.

In an early talk Ken was explaining the advantages of tolerant
comparison. A member of the audience asked incredulously,
“Surely you don’t mean that when A=B and B=C, A may not equal C?â€
Without skipping a beat, Ken replied, “Any carpenter knows that!â€
and went on to the next question. — Paul Berry


The intransitivity of [tolerant] equality is well known in
practical situations and can be easily demonstrated by sawing
several pieces of wood of equal length. In one case, use the
first piece to measure subsequent lengths; in the second case,
use the last piece cut to measure the next. Compare the lengths
of the two final pieces.
— Richard Lathwell, APL Comparison Tolerance, APL76, 1976


See also here:

http://www.jsoftware.com/papers/APLEvol.htm

(search for "fuzz" or "tolerance".

 

[Roy Smith]

In an early talk Ken was explaining the advantages of tolerant
comparison. A member of the audience asked incredulously,
“Surely you don’t mean that when A=B and B=C, A may not equal C?â€
Without skipping a beat, Ken replied, “Any carpenter knows that!â€
and went on to the next question. — Paul Berry

Any any good carpenter also knows it's better to copy than to measure.
Let's say I have a door frame and I need to trim a door to fit it
exactly. I can do one of two things.

First, I could take out my tape measure and measure that the frame is 29
and 11/32 inches wide. Then, carry that tape measure to the door,
measure off 29 and 11/32 inches, and make a mark.

Or, I could take a handy stick of wood which is 30-something inches
long, lay it down at the bottom of the door frame with one end up snug
against one side, and make a mark at the other side of the frame. Then
carry my stick to the door and keep trimming until it's the same width
as the marked section on the stick.

Google for "story stick".

The tape measure is like digital floating point. It introduces all
sorts of ways for errors to creep in and people who care about getting
doors to properly fit into door frames understand all that.

 

[Stefan Drees]

That is an excellent question! ...
I have a module that works with ULPs. I may clean it up and publish it.
Would there be interest in seeing it in the standard library? ...

I am definitely interested seeing this in the python standard library.
But as I continued to read the lines following your proposal and the
excellent article from Bruce pointed to by Carlos on this thread, maybe
a package on pypi first grounding somewhat the presumably massive
discussion thread on python-ideas :-?)

All the best,

Stefan.