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

arm-ehjacob/cs343-translationnew-astnew-ast-unique-expr
Last change on this file since fbfd97bd was 295ed2a4, checked in by Andrew Beach <ajbeach@…>, 2 years ago

Added approximately equals operator proposal.

  • Property mode set to 100644
File size: 4.5 KB
Line 
1Approximately Equals Operator
2=============================
3
4This is a proposal for the inclusion of two new operators into Cforall.
5
6Approximate equality is a very useful concept for floating point arithmetic.
7Due to floating point error values are very rarely the same when they are
8supposed to be. Because of this it is standard practice to provide some
9wrapper function (or in C++ an entire class) when doing these operations.
10
11This proposal offers to do the same thing, but introduces a new trinary
12operator to provide an easy to read interface for this operation.
13
14For example if you have two floats `a` and `b` to see if they are equal with
15error `e` you would write `a ~== b : e`. The underlying function might look
16like the following:
17
18```
19bool ?~==?:?(float lhs, float rhs, float epsilon) {
20    return lhs <= rhs + epsilon && rhs <= lhs + epsilon
21}
22```
23
24Approximately Inequals Operator
25------------------------------
26
27Called `?~!=?:?` and usually written as `a ~!= b : e`, this is the negated
28variant of approximately equals. That's it one should always be equal to the
29negation of the other.
30
31Although this is not commonly considered a basic operation it is included to
32ease negating a condition.
33
34Default Implementation
35----------------------
36
37The provided operations do not have to example provided above. The behaviour
38should be to return true if the absolute value of the difference between the
39compared values is less than or equal to the error value. So approximate
40equality with error of zero should be the same as equality.
41
42Each implementation could be provided individually or it could be provided
43through a generic function, as in the following:
44
45```
46forall(otype T | { T ?+?(T, T); bool ?<=?(T, T); })
47bool ?~==?:?(float lhs, float rhs, float epsilon) {
48    return lhs <= rhs + epsilon && rhs <= lhs + epsilon
49}
50```
51
52This could be organized like the concurrency extensions. That is the minimal
53syntax is provided but to get full use a library include is required. If so
54the library might be called `approx.hfa`.
55
56Required Syntax
57---------------
58
59We will need `~==` and `~!=` as new operator tokens. `?~==?:?` and `?~!=?:?`
60must be recognized as two new special operator names. Then the operators
61have to be included in the grammar as a new type of expression.
62
63Because of the natural use it should bind more tightly than logical operations
64so that `b && x ~== y : e` is the same as `b && (x ~== y : e)` but not as much
65arithmetic operations so `n + x ~== y : e` is the same as `(n + x) ~== y : e`.
66Either at the same precedence as equality or in-between equality and
67comparison.
68
69Choice of Symbols
70-----------------
71
72The first operator symbols (`~==` and `~!=`) were chosen considering that the
73only two operations we are adding approximate variants for. (See end of
74section for details.) If only approximately equals was included then `~=`
75might be the better choice for consistency with `!=`, `<=` and `>=`. However
76that would make it less consistent with `~!=` and we can't use both `~` and
77`!` to replace the first symbol in that case.
78
79The `:` for the second separator was used because of symmetry with the
80conditional operator `?:`. The symmetry is not perfect, the colon on the
81conditional is a divider that separates two equivalent options while here it
82adds an extra detail to the main operation, but the additional separator for
83a third argument remains the same. In addition `:` is already a token and it
84never appears to begin something so it is unlikely to ever cause conflicts.
85
86### Why Not Add More Approximate Operators?
87To begin with very few operations have a meaningful error value in them.
88Besides some exotic recursive calculation it is limited to comparisons.
89
90With equality and inequality covered that leaves use with the ordering
91comparisons. In these cases because one side (above or below) is covered in
92its entirety adding an error simply shifts (down or up) by that amount. This
93is a less useful operation and easier to code in line. For example:
94
95`( a ~<= b : epsilon ) == ( a <= b + epsilon )`
96
97Default Epsilon
98---------------
99
100For primitive (or library) types that have approximate equality defined on
101them it may also be useful to provide a general default for the error. Some
102epsilon that is small, but large enough to catch the usual build up of error
103when someone is doing just a bit of math with these types.
104
105However it should probably not be called epsilon to avoid any confusion with
106machine epsilon, which in many cases would be much smaller than the default
107error value.
108
109Even if the default implementations are in the prelude and not a library,
110these might be useful contexts of `approx.hfa`.
Note: See TracBrowser for help on using the repository browser.