source: doc/proposals/approx-equal.md @ b965774

Approximately Equals Operator
=============================

This is a proposal for the inclusion of two new operators into Cforall.

Approximate equality is a very useful concept for floating point arithmetic.
Due to floating point error values are very rarely the same when they are
supposed to be. Because of this it is standard practice to provide some
wrapper function (or in C++ an entire class) when doing these operations.

This proposal offers to do the same thing, but introduces a new trinary
operator to provide an easy to read interface for this operation.

For example if you have two floats `a` and `b` to see if they are equal with
error `e` you would write `a ~== b : e`. The underlying function might look
like the following:

```
bool ?~==?:?(float lhs, float rhs, float epsilon) {
    return lhs <= rhs + epsilon && rhs <= lhs + epsilon
}
```

Approximately Inequals Operator
------------------------------

Called `?~!=?:?` and usually written as `a ~!= b : e`, this is the negated
variant of approximately equals. That's it one should always be equal to the
negation of the other.

Although this is not commonly considered a basic operation it is included to
ease negating a condition.

Default Implementation
----------------------

The provided operations do not have to example provided above. The behaviour
should be to return true if the absolute value of the difference between the
compared values is less than or equal to the error value. So approximate
equality with error of zero should be the same as equality.

Each implementation could be provided individually or it could be provided
through a generic function, as in the following:

```
forall(otype T | { T ?+?(T, T); bool ?<=?(T, T); })
bool ?~==?:?(float lhs, float rhs, float epsilon) {
    return lhs <= rhs + epsilon && rhs <= lhs + epsilon
}
```

This could be organized like the concurrency extensions. That is the minimal
syntax is provided but to get full use a library include is required. If so
the library might be called `approx.hfa`.

Required Syntax
---------------

We will need `~==` and `~!=` as new operator tokens. `?~==?:?` and `?~!=?:?`
must be recognized as two new special operator names. Then the operators
have to be included in the grammar as a new type of expression.

Because of the natural use it should bind more tightly than logical operations
so that `b && x ~== y : e` is the same as `b && (x ~== y : e)` but not as much
arithmetic operations so `n + x ~== y : e` is the same as `(n + x) ~== y : e`.
Either at the same precedence as equality or in-between equality and
comparison.

Choice of Symbols
-----------------

The first operator symbols (`~==` and `~!=`) were chosen considering that the
only two operations we are adding approximate variants for. (See end of
section for details.) If only approximately equals was included then `~=`
might be the better choice for consistency with `!=`, `<=` and `>=`. However
that would make it less consistent with `~!=` and we can't use both `~` and
`!` to replace the first symbol in that case.

The `:` for the second separator was used because of symmetry with the
conditional operator `?:`. The symmetry is not perfect, the colon on the
conditional is a divider that separates two equivalent options while here it
adds an extra detail to the main operation, but the additional separator for
a third argument remains the same. In addition `:` is already a token and it
never appears to begin something so it is unlikely to ever cause conflicts.

### Why Not Add More Approximate Operators?
To begin with very few operations have a meaningful error value in them.
Besides some exotic recursive calculation it is limited to comparisons.

With equality and inequality covered that leaves use with the ordering
comparisons. In these cases because one side (above or below) is covered in
its entirety adding an error simply shifts (down or up) by that amount. This
is a less useful operation and easier to code in line. For example:

`( a ~<= b : epsilon ) == ( a <= b + epsilon )`

Default Epsilon
---------------

For primitive (or library) types that have approximate equality defined on
them it may also be useful to provide a general default for the error. Some
epsilon that is small, but large enough to catch the usual build up of error
when someone is doing just a bit of math with these types.

However it should probably not be called epsilon to avoid any confusion with
machine epsilon, which in many cases would be much smaller than the default
error value.

Even if the default implementations are in the prelude and not a library,
these might be useful contexts of `approx.hfa`.